Numbers which are not the sum of distinct squares: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Raku}}: clarify slightly)
m (→‎{{header|Raku}}: more style twiddling)
Line 35: Line 35:


=={{header|Raku}}==
=={{header|Raku}}==
[https://tio.run/##jVA7TsMwGN5zik9qhraApS4MjVKxcgZEKwN/wJLjJH4gqip7uQSHYGXrUXqRkD@maUcyWIq/t2uy@rbryi3uXBOkJYcc6@P@C6KU9RLzw3eGCe5NoYzyBEdW9ZyqwB89SYrKYiEEa25WSF2DHcZvAobpnewWz1X5pIz0qjJsILUeTZg6dAglFzh1eVj3do/iQugOP6IniWBUE0i4yvpsVNtg4g9nRq9dcmrCqKiDe5ummxmkeYGhD49gNDkXUdJUumxUqALpBnkeQS@VxhUW/brRasmEFqQd9ddaOs@isxdW5ym8JBuwfuB0hnbIiWcdPF4t1ZjjuP@M1a/5Uc/JXPgfAUnbdb8 Try it online!]
[https://tio.run/##jVA7TsMwGN5zik9qhpSHpS4MjVKxcgZEKwN/wJLjJH4gqih7uQSHYGXrUXqRYNfUZSSDpfh7uyMtb6ap2eLW9I5rMqiwPuw@wRreLXGx/yoxw52qhRKWYEgLz2lr/NKzrG41FowFzfUKuekxIH0zBJjeSG/x1DaPQnErWhUMuJTJJFCPHVwTCpy63K@93QP7IzT7b@ZJzCnRO2Km1bZMau1U/AmZ0WvITk0CyjpnXot8MwdXz1D0buGUJGMiSpIaUyaFqJFvUFURtFxIXGLh1yWrZSCMIGnIX0tubBCdvbA6TwlLyiPmBxZzjMeceHbO4kVTh8H7HXYfsfx4hcI/bEqPrf@Rko3T9AM Try it online!]


'''Spoiler:''' ''(highlight to read)''<br>
'''Spoiler:''' ''(highlight to read)''<br>
Line 48: Line 48:
if $_ == @run.tail + 1 { @run.push: $_ } else { last if @run.elems > @squares[$sq]; @run = () }
if $_ == @run.tail + 1 { @run.push: $_ } else { last if @run.elems > @squares[$sq]; @run = () }
}
}
put grep {$_ ∉ @sums}, (1..@run.tail) and last if @run.elems > @squares[$sq];
put grep * ∉ @sums, 1..@run.tail and last if @run.elems > @squares[$sq];
}</lang>
}</lang>
{{out}}
{{out}}

Revision as of 22:30, 23 November 2021

Numbers which are not the sum of distinct squares is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.


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

Try it online!

Spoiler: (highlight to read)
Once the longest run of consecutive 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 { last if @run.elems > @squares[$sq]; @run = () }
   }
   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
Retrieved from "https://rosettacode.org/wiki/Numbers_which_are_not_the_sum_of_distinct_squares?oldid=317965"