

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.



Task
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.



See also
 OEIS: A001422 Numbers which are not the sum of distinct squares


#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 $n
def 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 $n
def 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 array
def 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