

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


var squares = (1..18).map { |i| i * i }.toList
var combs = []
var results = []
 
// generate combinations of the numbers 0 to n-1 taken m at a time
var 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)