Numbers which are not the sum of distinct squares

From Rosetta Code
Task
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.


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


ALGOL 68

Recursive brute force (tempting though it is to use 9 nested loops... :) ), using the proof that if 129-324 can be expressed as the sum of distinct squares, then all integers greater than 128 can be so expressed - see the link in the Wren sample.

CO find the integers that can't be expressed as the sum of distinct squares
   it can be proved that if 120-324 can be expressed as the sum of distinct
   squares then all integers greater than 129 can be so expressed
   (see the link in the Wren sample) so we need to check that 129-324 can
   be so expressed and find the numbers below 129 that can't be so expressed
CO
BEGIN
    INT max number = 324;
    [ 0 : max number ]BOOL is sum; FOR i FROM LWB is sum TO UPB is sum DO is sum[ i ] := FALSE OD;
    INT max square = ENTIER sqrt( 324 );
    [ 0 : max square ]INT  square; FOR i FROM LWB square TO UPB square DO square[ i ] := i * i OD;

    PROC flag sum = ( INT curr sum, sq pos )VOID:
         IF INT next sum = curr sum + square[ sq pos ];
            next sum <= UPB is sum
         THEN
            is sum[ next sum ] := TRUE;
            FOR i FROM sq pos + 1 TO UPB square DO
                flag sum( next sum, i )
            OD
         FI # flag sum # ;

    FOR i FROM LWB square TO UPB square DO
        flag sum( 0, i )
    OD;
    # show the numbers that can't be formed from a sum of distinct squares       #
    # and check 129-324 can be so formed                                         #
    INT unformable := 0;
    FOR i FROM LWB is sum TO UPB is sum DO
        IF NOT is sum[ i ] THEN
            print( ( whole( i, -4 ) ) );
            IF ( unformable +:= 1 ) MOD 12 = 0 THEN print( ( newline ) ) FI;
            IF i > 128 THEN
                print( ( newline, "**** unexpected unformable number: ", whole( i, 0 ), newline ) )
            FI
        FI
    OD
END
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

ALGOL W

Translation of: ALGOL 68
begin comment find the integers that can't be expressed as the sum of distinct squares
              it can be proved that if 120-324 can be expressed as the sum of distinct
              squares then all integers greater than 129 can be so expressed
              (see the link in the Wren sample) so we need to check that 129-324 can
              be so expressed and find the numbers below 129 that can't be so expressed
            ;
    integer MAX_NUMBER, MAX_SQUARE;
    MAX_NUMBER := 324;
    MAX_SQUARE := entier( sqrt( MAX_NUMBER ) );

    begin
        logical array isSum  ( 0 :: MAX_NUMBER );
        integer array square ( 0 :: MAX_SQUARE );
        integer unformable;

        procedure flagSum ( integer value currSum, sqPos ) ; begin
             integer nextSum;
             nextSum := currSum + square( sqPos );
             if nextSum <= MAX_NUMBER then begin
                isSum( nextSum ) := true;
                for i := sqPos + 1 until MAX_SQUARE do flagSum( nextSum, i )
             end of_nextSum_le_MAX_NUMBER
        end flagSum ;

        for i := 0 until MAX_NUMBER do isSum(  i ) := false;
        for i := 0 until MAX_SQUARE do square( i ) := i * i;
        for i := 0 until MAX_SQUARE do flagSum( 0, i );
        % show the numbers that can't be formed from a sum of distinct squares %
        % and check 129-324 can be so formed %
        unformable := 0;
        for i := 0 until MAX_NUMBER do
        if not isSum( i ) then begin
            writeon( i_w := 4, s_w := 0, i );
            unformable := unformable + 1;
            if unformable rem 12 = 0 then write();
            if i > 128 then write( i_w := 1, s_w := 0, "**** unexpected unformable number: ", i )
        end if_not_isSum__i
    end
end.
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

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

BASIC

FreeBASIC

Translation of: XPL0
Function SumSq(num As Integer) As Integer    'Return sum of squares specified by bits in num
    Dim As Integer n = 1, suma = 0, Sq
    While num
        If num And 1 Then
            Sq = n*n
            suma += Sq
        End If
        num Shr= 1
        n += 1
    Wend
    Return suma
End Function

Dim As Integer limite = 1e6, cant = 0, i
Dim As Boolean flags(limite)

For i = 0 To limite-1
    flags(i) = True
Next
For i = 0 To limite-1
    If i < limite Then flags(SumSq(i)) = False
Next

For i = 0 To Sqr(limite)-1
    If flags(i) Then cant += 1: Print i; 
Next
Print Chr(10); cant; " numbers which are not the sum of distinct squares."

Sleep
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
 31 numbers which are not the sum of distinct squares.


Gambas

Public flags[1000000] As Boolean

Public Sub Main() 
  
  Dim limite As Integer = 1e6, cant As Integer = 0, i As Integer 
  
  For i = 0 To limite - 1 
    flags[i] = True 
  Next 
  For i = 0 To limite - 1 
    If i < limite Then flags[SumSq(i)] = False 
  Next 
  
  For i = 0 To Sqr(limite) - 1 
    If flags[i] Then 
      cant += 1
      Print i; " "; 
    End If
  Next 
  Print Chr(10); cant; " numbers which are not the sum of distinct squares." 
  
End

Function SumSq(num As Integer) As Integer
  
  Dim n As Integer = 1, suma As Integer = 0, Sq As Integer

  While num 
    If num And 1 Then 
      Sq = n * n 
      suma += Sq 
    End If 
    num = num Shr 1 
    n += 1
  Wend 
  Return suma 
  
End Function
Output:
Same as FreeBASIC entry.

C++

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>

void print_vector(const std::vector<int32_t>& list) {
	std::cout << "[";
	for ( uint64_t i = 0; i < list.size() - 1; ++i ) {
		std::cout << list[i] <<", ";
	}
	std::cout << list.back() << "]" << std::endl;
}

bool sum_of_distinct_squares(const int32_t& n, const std::vector<int32_t>& squares) {
	if ( n <= 0 ) {
		return false;
	}
	if ( find(squares.begin(), squares.end(), n) != squares.end() ) {
		return true;
	}

	const int32_t sum = std::accumulate(squares.begin(), squares.end(), 0);
	if ( n > sum ) {
		return false;
	}
	if ( n == sum ) {
		return true;
	}

	std::vector<int32_t> reversed_squares(squares);
	reversed_squares.erase(reversed_squares.end() - 1);
	std::reverse(reversed_squares.begin(), reversed_squares.end());

	return sum_of_distinct_squares(n - squares[squares.size() - 1], reversed_squares)
		|| sum_of_distinct_squares(n, reversed_squares);
}

int main() {
	std::vector<int32_t> squares;
	std::vector<int32_t> result;
	int32_t test_number = 1;
	int32_t previous_test_number = 1;
	while ( previous_test_number >= ( test_number >> 1 ) ) {
		const int32_t square_root = static_cast<int32_t>(std::sqrt(test_number));
		if ( square_root * square_root == test_number ) {
			squares.emplace_back(test_number);
		}
		if ( ! sum_of_distinct_squares(test_number, squares) ) {
			result.emplace_back(test_number);
			previous_test_number = test_number;
		}
		test_number++;
	}

	std::cout << "Numbers which are not the sum of distinct squares:" << std::endl;
	print_vector(result);
	std::cout << "\n" << "Stopped checking after finding " << ( test_number - previous_test_number )
		<< " sequential non-gaps after the final gap of " << previous_test_number << std::endl;
	std::cout << "Found " << result.size() << " numbers in total" << std::endl;
}
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 numbers in total

Delphi

Works with: Delphi version 6.0

Testing number beyond 128, show no values greater than this value.

{This code would normally be a separate library but is present her for clarity}

{Iterater object to step through all the indices
{ corresponding to the bits in "N". This is used }
{ step through all the combinations of items }

type TBitIterator = class(TObject)
 private
   FNumber,FIndex: integer;
 public
  procedure Start(StartNumber: integer);
  function Next(var Index: integer): boolean;
 end;

procedure TBitIterator.Start(StartNumber: integer);
{Set the starting value of the number }
begin
FNumber:=StartNumber;
end;


function TBitIterator.Next(var Index: integer): boolean;
{Return the next available index}
begin
Result:=False;
while FNumber>0 do
	begin
	Result:=(FNumber and 1)=1;
	if Result then Index:=FIndex;
	FNumber:=FNumber shr 1;
	Inc(FIndex);
	if Result then break;
	end;
end;

{------------------------------------------------------------------------------}


procedure NonSquareSums(Memo: TMemo);
var Squares: TCardinalDynArray;
var I,N,Cnt: integer;
var S: string;

	function GetSum(N: integer): integer;
	{Iterate through all indices corresponding to N}
	{Get get the sum of their values}
	var Inx: integer;
	var BI: TBitIterator;
	begin
	BI:=TBitIterator.Create;
	try
	BI.Start(N);
	Result:=0;
	while BI.Next(Inx) do
	 Result:=Result+Squares[Inx];
	finally BI.Free; end;
	end;

	function HasSquareSum(N: integer): boolean;
	{See if N is sum of squares}
	var I: integer;
	begin
	Result:=True;
	for I:=0 to High(Squares) do
	 if GetSum(I)=N then exit;
	Result:=False;
	end;


begin
{build array of squares for speed}
{64K^2 max 32-bit integer value}
SetLength(Squares,65536);
for I:=1 to High(Squares) do Squares[I-1]:=I*I;
S:=''; Cnt:=0;
{Test numbers up to sqrt(64K) = 64}
for I:=1 to trunc(sqrt(Length(Squares))) do
 if not HasSquareSum(I) then
	begin
	{display number that aren't sum of squares}
	Inc(Cnt);
	S:=S+Format('%4d',[I]);
	if (Cnt mod 10)=0 then S:=S+CRLF;
	end;
Memo.Lines.Add('Numbers which are not the sum of distinct squares');
Memo.Lines.Add('Count = '+IntToStr(Cnt));
Memo.Lines.Add(S);
end;
Output:
Numbers which are not the sum of distinct squares
Count = 31
   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

Elapsed Time: 333.278 ms.


EasyLang

Translation of: Lua
maxNumber = 324
len isSum[] maxNumber
maxSquare = floor sqrt maxNumber
# 
proc flagSum currSum sqPos . .
   nextSum = currSum + sqPos * sqPos
   if nextSum <= maxNumber
      isSum[nextSum] = 1
      for i = sqPos + 1 to maxSquare
         flagSum nextSum i
      .
   .
.
for i = 1 to maxSquare
   flagSum 0 i
.
for i = 1 to maxNumber
   if isSum[i] = 0
      write i & " "
   .
.

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

J

Code:

task=: {{
  r=. 'invalid'
  lim=. 1
  whilst. -.r -: have do.
    have=. r
    lim=. lim+1
    r=. (i.*:lim) -. (#:i.2^lim)+/ .**:i.lim
  end.
}}

In other words, find all integers up to the square of our limit, and remove from that sequence all corresponding sums of squares. Keep increasing the limit until we stop finding new values which are not sums of squares.

Result:

   task''
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

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public final class NumbersNotSumDistinctSquares {

	public static void main(String[] aArgs) {
		List<Integer> squares = new ArrayList<Integer>();
		List<Integer> result = new ArrayList<Integer>();
	    int testNumber = 1;
	    int previousTestNumber = 1;
	    while ( previousTestNumber >= ( testNumber >> 1 ) ) {
	        final int squareRoot = (int) Math.sqrt(testNumber);
	        if ( squareRoot * squareRoot == testNumber ) {
	            squares.add(testNumber);
	        }
	        if ( ! sumOfDistinctSquares(testNumber, squares) ) {	           
	            result.add(testNumber);
	            previousTestNumber = testNumber;
	        }
	        testNumber += 1;
	    }
	    
	    System.out.println("Numbers which are not the sum of distinct squares:");
	    System.out.println(result);
	    System.out.println();
	    System.out.println("Stopped checking after finding " + ( testNumber - previousTestNumber )
	    	+ " sequential non-gaps after the final gap of " + previousTestNumber);
	    System.out.println("Found " + result.size() + " numbers in total");
	}
	
	private static boolean sumOfDistinctSquares(int aN, List<Integer> aSquares) {
		if ( aN <= 0 ) { 
			return false;
		}
		if ( aSquares.contains(aN) ) {
			return true;
		}
		
		final int sum = aSquares.stream().mapToInt(Integer::intValue).sum();
		if ( aN > sum ) {
	        return false;
	    }
	    if ( aN == sum ) {
	        return true;
	    }
	    
	    List<Integer> reversedSquares = new ArrayList<Integer>(aSquares);
	    reversedSquares.remove(reversedSquares.size() - 1);
	    Collections.reverse(reversedSquares);
	    
	    return sumOfDistinctSquares(aN - aSquares.get(aSquares.size() - 1), reversedSquares)
	    	|| sumOfDistinctSquares(aN, reversedSquares);
	}

}
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 numbers 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 $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
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. Now
11 * 11 < 128 < 12 * 12. It is also true that we need no square less than 144 (12 * 12) to
reduce via subtraction of squares all the numbers above 400 to a number > 128 and < 400 by
subtracting discrete squares of numbers over 12, since the interval between such squares can
be well below 128: for example, |14^2 - 15^2| is 29. So, we can always find a serial subtraction
of discrete integer squares from any number > 400 that targets the interval between 129 and
400. Once we get to that interval, we already have shown in the program below that we can
use 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]

Lua

Translation of: ALGOL 68
do  --[[ find the integers that can't be expressed as the sum of distinct squares
         it can be proved that if 120-324 can be expressed as the sum of distinct squares
         then all integers greater than 129 can be so expressed (see the link in
         the Wren sample) so we need to check that 129-324 can be so expressed
         and find the numbers below 129 that can't be so expressed
    --]]
    local maxNumber = 324
    local isSum     = {}
    local maxSquare = math.floor( math.sqrt( 324 ) )
    local square    = {} for i = 0,maxSquare do square[ i ] = i * i end

    local function flagSum ( currSum, sqPos )
         local nextSum = currSum + square[ sqPos ]
         if nextSum <= maxNumber then
            isSum[ nextSum ] = true
            for i = sqPos + 1, maxSquare do
                flagSum( nextSum, i )
            end
         end
    end

    for i = 0,maxSquare do
        flagSum( 0, i )
    end
    --[[ show the numbers that can't be formed from a sum of distinct squares
         and check 129-324 can be so formed
    --]]
    local unformable = 0
    for i = 0, maxNumber do
        if not isSum[ i ] then
            io.write( string.format( "%4d", i ) )
            unformable = unformable + 1
            if unformable % 12 == 0 then io.write( "\n" ) end
            if i > 128 then
                io.write( "\n", "**** unexpected unformable number: ", i, "\n" )
            end
        end
    end
end
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

Mathematica /Wolfram Language

ClearAll[SumOfSquareable]
SumOfSquareable[n_Integer] := MemberQ[Total /@ Subsets[Range[1, Floor[Sqrt[n]]]^2, {1, \[Infinity]}], n]
notsummable = {};
i = 1;
Do[
 If[SumOfSquareable[i],
  If[i > 1,
   If[i - Max[notsummable] > Max[notsummable],
    Break[]
    ]
   ]
  ,
  AppendTo[notsummable, i]
  ];
 i++
 ,
 {\[Infinity]}
 ]
notsummable
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}

Modula-2

Works with: XDS Modula-2

Mathematical justification is provided in part by the ProofWiki article "Numbers not Sum of Distinct Squares" linked from the Wren solution. It's shown that if

(1) every integer in the range 129..324 (= 18^2) can be expressed as a sum of distinct squares, then

(2) every integer from 129 onwards can be so expressed.

However, the author leaves the reader to complete the proof of (2) by verifying (1). The program therefore needs to do that, but needn't consider integers greater than 324.

MODULE NotSumDistinctSq;
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
VAR
  sds : ARRAY [0..324] OF BOOLEAN; (* sum of distinct squares? *)
  j, k, r, rsq, max_true, start, nr_in_line : CARDINAL;
BEGIN
  sds[0] := TRUE;
  FOR j := 1 TO 324 DO sds[j] := FALSE; END;
  max_true := 0; (* maximum index for which sds is TRUE *)
  FOR r := 1 TO 18 DO
    rsq := r*r;
    (* NB Work backwards, so that the only TRUE values found
       are those set up by previous values of r. *)
    start := 324 - rsq;
    IF start > max_true THEN start := max_true; END;
    FOR j := start TO 0 BY -1 DO
      IF sds[j] THEN
        k := j + rsq;
        sds[k] := TRUE;
        IF k > max_true THEN max_true := k; END;
      END;
    END;
  END;

  (* Verify that all integers 129..324 are sums of distinct squares *)
  j := 129;
  WHILE (j <= 324) AND sds[j] DO INC(j); END;
  IF j <= 324 THEN
    WriteString( "*** Verification failed ***");
    RETURN;
  END;

  (* Print the result *)
  WriteString( "Positive integers not the sum of distinct squares");
  WriteLn;
  nr_in_line := 0;
  FOR j := 0 TO 128 DO
    IF NOT sds[j] THEN
      IF nr_in_line = 12 THEN
        WriteLn; nr_in_line := 0;
      END;
      WriteCard(j, 4);
      INC( nr_in_line);
    END;
  END;
END NotSumDistinctSq.
Output:
Positive integers 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

Nim

Translation of: Wren, C#, Go
import std/[algorithm, math, monotimes, strformat, strutils, times]

proc soms(n: int; f: seq[int]): bool =
  ## Recursively permutates the list of squares to seek a matching sum.
  if n <= 0: return false
  if n in f: return true
  case cmp(n, sum(f))
  of 1:
    result = false
  of 0:
    result = true
  else:
    let rf = reversed(f.toOpenArray(0, f.len - 2))
    result = soms(n - f[^1], rf) or soms(n, rf)

let start = getMonoTime()
var s, a: seq[int]
var i, g = 1
while g >= i shr 1:
  let r = sqrt(i.toFloat).int
  if r * r == i: s.add i
  if not soms(i, s):
    g = i
    a.add g
  inc i

echo "Numbers which are not the sum of distinct squares:"
echo a.join(" ")
echo &"\nStopped checking after finding {i - g} sequential non-gaps after the final gap of {g}."
echo &"Found {a.len} total in {(getMonotime() - start).inMicroseconds} µs."
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 1536 µs.

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 == add
var
  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,

Perl

Translation of: Raku
use v5.36;
use List::Util <sum uniq none>;
use Algorithm::Combinatorics 'combinations';

my @squares = map { $_**2 } 0..100;
my $sq;

while (++$sq) {
    my(@sums, @run);
    for (1..$sq) {
        push @sums, sum @squares[@$_] for combinations [1..$sq+1], $_
    }
    @sums = uniq sort { $a <=> $b } @sums;
    for (@sums) {
        push(@run, $_) and next unless @run;
        if ($_ == $run[-1] + 1) { push @run, $_ } else { last if @run > $squares[$sq]; @run = () }
    }
    next unless @run;
    for my $i (1..$run[-1]) {
         push @res, $i if none { $i eq $_ } @sums
    }
    last if @run > $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

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)

Quackery

from, index, end, and incr are defined at Loops/Increment loop index within loop body#Quackery.

Method

We generate numbers which are the Sum Of Distinct Squares (SODS) up to N2 by generating a list of the SODS up to (N-1)2, then adding each of those numbers + N2 to the list. For N=0 the list is [0]. This method produces some duplicates along the way so after each iteration we remove any duplicates using sort unique. (unique requires a sorted list.)

As noted in other solutions, once there is a run longer than (N+1)2, all the subsequent numbers will be SODS. missing returns the length and position of the longest run. (After the last iteration, some SODS will be missing from the list after the longest run, but we can be confident that they will be found in further iterations as noted in other task solutions.) The length is used to test for when we can stop iterating, and the position tells us where we can trim the list.

Finally, missing generates a list of the numbers which are not SODS from the list of SODS. (This is why we need to trim the list; so it does not include the numbers which are SODS but had not yet been added to the list.)

  [ [] swap
    behead swap
    witheach
      [ 2dup = iff
          drop done
        dip join ]
    join ]                          is unique  ( [ --> [   )

  [ stack ]                         is cut     (   --> s   )

  [ -1 cut put
    1 temp put
    1 swap
    behead swap
     witheach
      [ tuck - -1 = iff
          [ dip 1+
            over temp share
            > if 
              [ over temp replace
                 i^ cut replace ] ]
        else
          [ nip 1 swap ] ]
     2drop
     temp take cut take ]           is maxrun  ( [ --> n n )

  [ [] swap 0 over
    witheach [ bit | ]
    swap -1 peek times
      [ dup i^ bit & not if
          [ dip [ i^ join ] ] ]
    drop ]                          is missing ( [ --> [   )

  1 temp put
  ' [ 0 ]
  1 from
    [ dup witheach
        [ temp share +
          join ]
      sort unique
      dup maxrun drop
      index 2 + temp tally
      temp share > iff
        end done
      2 incr ]
  temp release
  dup maxrun
  nip split
  drop missing
  say "Numbers that are not the sum of distinct squares:"
  cr echo
Output:
Numbers that 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 ]

Raku

Try it online!

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

Uiua

The Wren solution gives a little more justification for my assumption...

N ← 16 # by inspection
# all sums of the first N squares, sorted and deduped
⊏⊸⍏◴≡(/+▽)⊙¤⋯⇡÷2ⁿ⟜(2×.↘1⇡)N
# find missing numbers
▽¬°⊚:⇡⊡¯1.
# After 128 the next 900 can all be generated, so assume that's it done.
# ⟜⧻▽≤128.
Output:
31
[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 }.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)
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 Nums
import "./fmt" for Fmt

// recursively permutates the list of squares to seek a matching sum
var soms
soms = 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.clock
var s = []
var a = []
var sf = "\nStopped checking after finding $d sequential non-gaps after the final gap of $d"
var i = 1
var g = 1
var r
while (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.

XPL0

This generates all combinations of sums of N squared up to a Limit. For a Limit = 1000 = $3E8 = %11_1110_1000 this sums 100+81+64+49+36+16. A Limit of one million shows that there is a huge gap following 128 of values that cannot be generated by any combination of sums of squares. The mathematical argument why none exist beyond 128 is provided by the Julia example.

func SumSq(B);          \Return sum of squares specified by bits in B
int  B, N, Sq, Sum;
[N:= 1;  Sum:= 0;
while B do
    [if B & 1 then
        [Sq:= N*N;
        Sum:= Sum + Sq;
        ];
    B:= B>>1;
    N:= N+1;
    ];
return Sum;
];

def  Limit = 1_000_000;
char Flags(Limit);
int  I;
[for I:= 0 to Limit-1 do
    Flags(I):= true;
for I:= 0 to Limit-1 do
    if I < Limit then
        Flags(SumSq(I)):= false;
for I:= 0 to sqrt(Limit)-1 do
    if Flags(I) then
        [IntOut(0, I);  ChOut(0, ^ )];
]
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