Numbers which are not the sum of distinct squares: Difference between revisions
Thundergnat (talk | contribs) (New draft task and Raku entry) |
Thundergnat (talk | contribs) m (clean up white space) |
||
Line 15: | Line 15: | ||
'''90''' == 36 + 25 + 16 + 9 + 4 == 64 + 16 + 9 + 1 == 49 + 25 + 16 == 64 + 25 + 1 == 81 + 9 |
'''90''' == 36 + 25 + 16 + 9 + 4 == 64 + 16 + 9 + 1 == 49 + 25 + 16 == 64 + 25 + 1 == 81 + 9 |
||
'''130''' == 64 + 36 + 16 + 9 + 4 + 1 == 49 + 36 + 25 + 16 + 4 == 100 + 16 + 9 + 4 + 1 == 81 + 36 + 9 + 4 == 64 + 49 + 16 + 1 == 100 + 25 + 4 + 1 == 81+ 49 == 121 + 9 |
'''130''' == 64 + 36 + 16 + 9 + 4 + 1 == 49 + 36 + 25 + 16 + 4 == 100 + 16 + 9 + 4 + 1 == 81 + 36 + 9 + 4 == 64 + 49 + 16 + 1 == 100 + 25 + 4 + 1 == 81 + 49 == 121 + 9 |
||
Line 26: | Line 26: | ||
;Task |
;Task |
||
Find and show here, on this page, every positive integer than can not be generated as the sum of distinct squares. |
Find and show here, on this page, '''every''' positive integer than can not be generated as the sum of distinct squares. |
||
Do not use magic numbers or pre-determined limits. Justify your answer mathematically. |
Do not use magic numbers or pre-determined limits. Justify your answer mathematically. |
Revision as of 22:04, 23 November 2021
Integer squares are the set of integers multiplied by themselves: 1 x 1 = 1, 2 × 2 = 4, 3 × 3 = 9, etc. ( 1, 4, 9, 16 ... )
Most positive integers can be generated as the sum of 1 or more distinct integer squares.
1 == 1 5 == 4 + 1 25 == 16 + 9 77 == 36 + 25 + 16 103 == 49 + 25 + 16 + 4
Many can be generated in more than one way:
90 == 36 + 25 + 16 + 9 + 4 == 64 + 16 + 9 + 1 == 49 + 25 + 16 == 64 + 25 + 1 == 81 + 9 130 == 64 + 36 + 16 + 9 + 4 + 1 == 49 + 36 + 25 + 16 + 4 == 100 + 16 + 9 + 4 + 1 == 81 + 36 + 9 + 4 == 64 + 49 + 16 + 1 == 100 + 25 + 4 + 1 == 81 + 49 == 121 + 9
A finite number can not be generated by any combination of distinct squares:
2, 3, 6, 7, etc.
- Task
Find and show here, on this page, every positive integer than can not be generated as the sum of distinct squares.
Do not use magic numbers or pre-determined limits. Justify your answer mathematically.
- See also
Raku
Spoiler: (highlight to read)
Once the longest run of generated sums is longer the the next square, every number after can be generated by adding the next square to every number in the run. Find the new longest run, add the next square, etc.
<lang perl6>my @squares = ^∞ .map: *²; # Infinite series of squares
for 1..∞ -> $sq { # for every combination of all squares
my @sums = @squares[^$sq].combinations».sum.unique.sort; my @run; for @sums { @run.push($_) and next unless @run.elems; if $_ == @run.tail + 1 { @run.push: $_ } else { @run = () and next } last if @run.elems > @squares[$sq]; } put grep {$_ ∉ @sums}, (1..@run.tail) and last if @run.elems > @squares[$sq];
}</lang>
- Output:
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