Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (doh. left one out) |
(julia example) |
||
Line 32: | Line 32: | ||
* [[oeis:A001422|OEIS: A001422 Numbers which are not the sum of distinct squares]] |
* [[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}}== |
=={{header|Raku}}== |