I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Numbers which are not the sum of distinct squares

Numbers which are not the sum of distinct squares
You are encouraged to solve this task according to the task description, using any language you may know.

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 + 9 + 4
```

Many can be generated in multiple ways:

```    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
```

The number of positive integers that cannot be generated by any combination of distinct squares is in fact finite:

```   2, 3, 6, 7, etc.
```

Find and show here, on this page, every positive integer than cannot be generated as the sum of distinct squares.

Do not use magic numbers or pre-determined limits. Justify your answer mathematically.

## C#

Following in the example set by the Free Pascal entry for this task, this C# code is re-purposed from Practical_numbers#C#.
It seems that finding as many (or more) contiguous numbers-that-are-the-sum-of-distinct-squares as the highest found gap demonstrates that there is no higher gap, since there is enough overlap among the permutations of the sums of possible squares (once the numbers are large enough).

`using System;using System.Collections.Generic;using System.Linq; class Program {   // recursively permutates the list of squares to seek a matching sum  static bool soms(int n, IEnumerable<int> f) {    if (n <= 0) return false;    if (f.Contains(n)) return true;    switch(n.CompareTo(f.Sum())) {      case 1: return false;      case 0: return true;      case -1:        var rf = f.Reverse().Skip(1).ToList();        return soms(n - f.Last(), rf) || soms(n, rf);    }    return false;  }   static void Main() {    var sw = System.Diagnostics.Stopwatch.StartNew();    int c = 0, r, i, g; var s = new List<int>(); var a = new List<int>();    var sf = "stopped checking after finding {0} sequential non-gaps after the final gap of {1}";    for (i = 1, g = 1; g >= (i >> 1); i++) {      if ((r = (int)Math.Sqrt(i)) * r == i) s.Add(i);      if (!soms(i, s)) a.Add(g = i);    }    sw.Stop();    Console.WriteLine("Numbers which are not the sum of distinct squares:");    Console.WriteLine(string.Join(", ", a));    Console.WriteLine(sf, i - g, g);    Console.Write("found {0} total in {1} ms",      a.Count, sw.Elapsed.TotalMilliseconds);  }}`
Output @Tio.run:
```Numbers which are not the sum of distinct squares:
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
stopped checking after finding 130 sequential non-gaps after the final gap of 128
found 31 total in 24.7904 ms```

### Alternate Version

A little quicker, seeks between squares.

`using System;using System.Collections.Generic;using System.Linq; class Program {   static List<int> y = new List<int>();   // checks permutations of squares in a binary fashion  static void soms(ref List<int> f, int d) { f.Add(f.Last() + d);    int l = 1 << f.Count, max = f.Last(), min = max - d;     var x = new List<int>();    for (int i = 1; i < l; i++) {      int j = i, k = 0, r = 0; while (j > 0) {        if ((j & 1) == 1 && (r += f[k]) >= max) break;        j >>= 1; k++; } if (r > min && r < max) x.Add(r); }    for ( ; ++min < max; ) if (!x.Contains(min)) y.Add(min); }   static void Main() {    var sw = System.Diagnostics.Stopwatch.StartNew();    var s = new List<int>{ 1 };    var sf = "stopped checking after finding {0} sequential non-gaps after the final gap of {1}";    for (int d = 1; d <= 29; ) soms(ref s, d += 2);    sw.Stop();    Console.WriteLine("Numbers which are not the sum of distinct squares:");    Console.WriteLine(string.Join (", ", y));    Console.WriteLine("found {0} total in {1} ms",      y.Count, sw.Elapsed.TotalMilliseconds);    Console.Write(sf, s.Last()-y.Last(),y.Last());  }}`
Output @Tio.run:
```Numbers which are not the sum of distinct squares:
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
found 31 total in 9.9693 ms
stopped checking after finding 128 sequential non-gaps after the final gap of 128```

## Go

Translation of: Wren
Library: Go-rcu

The quicker version and hence (indirectly) a translation of C#.

`package main import (    "fmt"    "math"    "rcu") func contains(a []int, n int) bool {    for _, e := range a {        if e == n {            return true        }    }    return false} // recursively permutates the list of squares to seek a matching sumfunc soms(n int, f []int) bool {    if n <= 0 {        return false    }    if contains(f, n) {        return true    }    sum := rcu.SumInts(f)    if n > sum {        return false    }    if n == sum {        return true    }    rf := make([]int, len(f))    copy(rf, f)    for i, j := 0, len(rf)-1; i < j; i, j = i+1, j-1 {        rf[i], rf[j] = rf[j], rf[i]    }    rf = rf[1:]    return soms(n-f[len(f)-1], rf) || soms(n, rf)} func main() {    var s, a []int    sf := "\nStopped checking after finding %d sequential non-gaps after the final gap of %d\n"    i, g := 1, 1    for g >= (i >> 1) {        r := int(math.Sqrt(float64(i)))        if r*r == i {            s = append(s, i)        }        if !soms(i, s) {            g = i            a = append(a, g)        }        i++    }    fmt.Println("Numbers which are not the sum of distinct squares:")    fmt.Println(a)    fmt.Printf(sf, i-g, g)    fmt.Printf("Found %d in total\n", len(a))} var r int`
Output:
```Numbers which are not the sum of distinct squares:
[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]

Stopped checking after finding 130 sequential non-gaps after the final gap of 128
Found 31 in total
```

## jq

Works with: jq

Works with gojq, the Go implementation of jq

The following program is directly based on the "Spoiler" observation at Raku. In effect, therefore, it computes the "magic number". It is nevertheless quite fast: on a 3GHz machine, u+s ~ 32ms using either the C or Go implementation of jq.

Since the implementation is based on generic concepts (such as runs), the helper functions are potentially independently useful.

`#def squares: range(1; infinite) | . * .; # sums of distinct squares (sods)# Output: a stream of [\$n, \$sums] where \$sums is the array of sods based on \$ndef sods:  # input: [\$n, \$sums]  def next:    . as [\$n, \$sums]    | ((\$n+1)*(\$n+1)) as \$next    | reduce \$sums[] as \$s (\$sums + [\$next];        if index(\$s + \$next) then . else . + [\$s + \$next] end)    | [\$n + 1, unique];   [1, [1]]  | recurse(next); # Input: an array# Output: the length of the run beginning at \$ndef length_of_run(\$n):  label \$out  | (range(\$n+1; length),null) as \$i  | if \$i == null then (length-\$n)    elif .[\$i] == .[\$i-1] + 1 then empty    else \$i-\$n, break \$out    end; # Input: an arraydef length_of_longest_run:  . as \$in  | first(      foreach (range(0; length),null) as \$i (0;        if \$i == null then .        else (\$in|length_of_run(\$i)) as \$n        | if \$n > . then \$n else . end        end;        if \$i == null or ((\$in|length) - \$i) < . then . else empty end) ); def sq: .*.; # Output: [\$ix, \$length]def relevant_sods:  first(    sods    | . as [\$n, \$s]    | (\$s|length_of_longest_run) as \$length    | if \$length > (\$n+1|sq) then . else empty end ); def not_sum_of_distinct_squares:  relevant_sods  | . as [\$ix, \$sods]  | [range(2; \$ix+2|sq)] - \$sods; not_sum_of_distinct_squares`
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]
```

## Julia

A true proof of the sketch below would require formal mathematical induction.

`#=Here we show all the 128 < numbers < 400 can be expressed as a sum of distinct squares. Now11 * 11 < 128 < 12 * 12. It is also true that we need no square less than 144 (12 * 12) toreduce via subtraction of squares all the numbers above 400 to a number > 128 and < 400 bysubtracting discrete squares of numbers over 12, since the interval between such squares canbe well below 128: for example, |14^2 - 15^2| is 29. So, we can always find a serial subtractionof discrete integer squares from any number > 400 that targets the interval between 129 and400. Once we get to that interval, we already have shown in the program below that we canuse the remaining squares under 400 to complete the remaining sum.=# using Combinatorics 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) `
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]
```

## Pascal

### Free Pascal

Modified Practical_numbers#Pascal.
Searching for a block of numbers that are all a possible sum of square numbers.
There is a symmetry of hasSum whether
2,3,6,..108,112,128,
are not reachably nor
SumOfSquare-2, SumOfSquare-3,SumOfSquare-6,...SumOfSquare-108,SumOfSquare-112,SumOfSquare-128

`program practicalnumbers;{\$IFDEF Windows}  {\$APPTYPE CONSOLE} {\$ENDIF}var  HasSum: array of byte;function FindLongestContiniuosBlock(startIdx,MaxIdx:NativeInt):NativeInt;var  hs0 : pByte;  l : NativeInt;begin  l := 0;  hs0 := @HasSum[0];  for startIdx := startIdx to MaxIdx do  Begin    IF hs0[startIdx]=0 then      BREAK;    inc(l);  end;  FindLongestContiniuosBlock := l;end; function SumAllSquares(Limit: Uint32):NativeInt;//mark sum and than shift by next summand == addvar  hs0, hs1: pByte;  idx, j, maxlimit, delta,MaxContiniuos,MaxConOffset: NativeInt;begin  MaxContiniuos := 0;  MaxConOffset := 0;  maxlimit := 0;  hs0 := @HasSum[0];  hs0[0] := 1; //has sum of 0*0  idx := 1;   writeln('number offset  longest  sum of');  writeln('                block  squares');  while idx <= Limit do  begin    delta := idx*idx;    //delta is within the continiuos range than break    If (MaxContiniuos-MaxConOffset) > delta then      BREAK;     //mark oldsum+ delta with  oldsum    hs1 := @hs0[delta];    for j := maxlimit downto 0 do      hs1[j] := hs1[j] or hs0[j];     maxlimit := maxlimit + delta;     j := MaxConOffset;    repeat      delta := FindLongestContiniuosBlock(j,maxlimit);      IF delta>MaxContiniuos then      begin        MaxContiniuos:= delta;        MaxConOffset := j;      end;      inc(j,delta+1);    until j > (maxlimit-delta);    writeln(idx:4,MaxConOffset:7,MaxContiniuos:8,maxlimit:8);    inc(idx);  end;  SumAllSquares:= idx;end; var  limit,  sumsquare,  n: NativeInt;begin  Limit := 25;  sumsquare := 0;  for n := 1 to Limit do    sumsquare := sumsquare+n*n;  writeln('sum of square [1..',limit,'] = ',sumsquare) ;  writeln;   setlength(HasSum,sumsquare+1);  n := SumAllSquares(Limit);  writeln(n);  for Limit := 1 to n*n do    if HasSum[Limit]=0 then      write(Limit,',');  setlength(HasSum,0); {\$IFNDEF UNIX}  readln; {\$ENDIF}end. `
Output:
```sum of square [1..25] = 5525

number offset  longest  sum of
block  squares
1      0       2       1   -> 0,1
2      0       2       5
3      0       2      14
4      0       2      30
5      0       2      55
6     34       9      91  ->34..42
7     49      11     140  ->49..59
8     77      15     204  ->77..91
9    129      28     285
10    129     128     385
11    129     249     506
12    129     393     650
13
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,
```

## Phix

As per Raku (but possibly using slightly different logic, and this is using a simple flag array), if we find there will be a block of n2 summables, and we are going to mark every one of those entries plus n2 as summable, those regions will marry up or overlap and it is guaranteed to become at least twice that length in the next step, and all subsequent steps since 2*n2 is also going to be longer than (n+1)2 for all n>1, hence it will (eventually) mark everything beyond that point as summable. You can run this online here.

Strictly speaking the termination test should probably be `if r and sq>r then`, not that shaving off two pointless iterations makes any difference at all.

```with javascript_semantics
sequence summable = {true} -- (1 can be expressed as 1*1)
integer n = 2
while true do
integer sq = n*n
summable &= repeat(false,sq)
-- (process backwards to avoid adding sq more than once)
for i=length(summable)-sq to 1 by -1 do
if summable[i] then
summable[i+sq] = true
end if
end for
summable[sq] = true
integer r = match(repeat(true,(n+1)*(n+1)),summable)
if r then
summable = summable[1..r-1]
exit
end if
n += 1
end while
constant nwansods = "numbers which are not the sum of distinct squares"
printf(1,"%s\n",{join(shorten(apply(find_all(false,summable),sprint),nwansods,5))})
```
Output:
```2 3 6 7 8 ... 92 96 108 112 128  (31 numbers which are not the sum of distinct squares)
```

## Raku

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.

`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];}`
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`

## Wren

Well I found a proof by induction here that there are only a finite number of numbers satisfying this task but I don't see how we can prove it programatically without using a specialist language such as Agda or Coq.

### Brute force

This uses a brute force approach to generate the relevant numbers, similar to Julia, except using the same figures as the above proof. Still slow in Wren, around 20 seconds.

`var squares = (1..18).map { |i| i * i }.toListvar combs = []var results = [] // generate combinations of the numbers 0 to n-1 taken m at a timevar combGen = Fn.new { |n, m|    var s = List.filled(m, 0)    var last = m - 1    var rc // recursive closure    rc = Fn.new { |i, next|        var j = next        while (j < n) {            s[i] = j            if (i == last) {                combs.add(s.toList)            } else {                rc.call(i+1, j+1)            }            j = j + 1        }    }    rc.call(0, 0)} for (n in 1..324) {    var all = true    for (m in 1..18) {        combGen.call(18, m)        for (comb in combs) {            var tot = (0...m).reduce(0) { |acc, i| acc + squares[comb[i]] }            if (tot == n) {                all = false                break            }        }        if (!all) break        combs.clear()    }    if (all) results.add(n)} System.print("Numbers which are not the sum of distinct squares:")System.print(results)`
Output:
```Numbers which are not the sum of distinct squares:
[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]
```

### Quicker

Translation of: C#
Library: Wren-math
Library: Wren-fmt

Hugely quicker in fact - only 24 ms, the same as C# itself.

`import "./math" for Numsimport "./fmt" for Fmt // recursively permutates the list of squares to seek a matching sumvar somssoms = Fn.new { |n, f|    if (n <= 0) return false    if (f.contains(n)) return true    var sum = Nums.sum(f)    if (n > sum) return false    if (n == sum) return true    var rf = f[-1..0].skip(1).toList    return soms.call(n - f[-1], rf) || soms.call(n, rf)} var start = System.clockvar s = []var a = []var sf = "\nStopped checking after finding \$d sequential non-gaps after the final gap of \$d"var i = 1var g = 1var rwhile (g >= (i >> 1)) {    if ((r = i.sqrt.floor) * r == i) s.add(i)    if (!soms.call(i, s)) a.add(g = i)    i = i + 1}System.print("Numbers which are not the sum of distinct squares:")System.print(a.join(", "))Fmt.print(sf, i - g, g)Fmt.print("Found \$d total in \$d ms.", a.count, ((System.clock - start)*1000).round)`
Output:
```Numbers which are not the sum of distinct squares:
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

Stopped checking after finding 130 sequential non-gaps after the final gap of 128
Found 31 total in 24 ms.
```