Numbers which are not the sum of distinct squares: Difference between revisions
Numbers which are not the sum of distinct squares (view source)
Revision as of 06:26, 24 November 2021
, 2 years agojulia example
Thundergnat (talk | contribs) m (doh. left one out) |
(julia example) |
||
Line 32:
* [[oeis:A001422|OEIS: A001422 Numbers which are not the sum of distinct squares]]
=={{header|Julia}}==
A true proof of the sketch below would require formal mathematical induction.
<lang julia>#=
Here we show all the 128 < numbers < 400 can be expressed as a sum of distinct squares. Now
11 * 11 < 128 < 12 * 12. It is also true that we need no square less than 144 (12 * 12) to
reduce via subtraction of squares all the numbers above 400 to a number > 128 and < 400 by
subtracting discrete squares of numbers over 12, since the interval between such squares is
well below 128: for example, 14^2 - 15^2 is 29. So, we can always find a serial subtraction
of discrete integer squares from any number > 400 that targets the interval between 129 and
400. Once we get to that interval, we already have shown in the program below that we can
use the remaining squares under 400 to complete the remaining sum.
=#
using Combinatorics
@show squares = [n * n for n in 1:20]
possibles = [n for n in 1:500 if all(combo -> sum(combo) != n,
combinations(squares))]
println(possibles)
</lang>{{out}}
<pre>
[2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128]
</pre>
=={{header|Raku}}==
| |||