

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


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))})
