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
C#[edit]
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[edit]
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[edit]
FreeBASIC[edit]
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[edit]
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.
Go[edit]
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[edit]
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
jq[edit]
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[edit]
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]
Mathematica/Wolfram Language[edit]
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[edit]
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[edit]
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[edit]
Free Pascal[edit]
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[edit]
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[edit]
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)
Raku[edit]
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
Wren[edit]
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[edit]
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[edit]
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[edit]
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