

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


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 sum
func 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