Numbers which are not the sum of distinct squares
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
A finite number can not be generated by any combination of distinct squares:
2, 3, 6, 7, etc.
- Task
Find and show here, on this page, every positive integer than can not be generated as the sum of distinct squares.
Do not use magic numbers or pre-determined limits. Justify your answer mathematically.
- See also
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).
<lang csharp>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); }
}</lang>
- 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
Julia
A true proof of the sketch below would require formal mathematical induction. <lang julia>#= 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)
</lang>
- 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]
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
<lang pascal>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. </lang>
- 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,
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.
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
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.
<lang perl6>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];
}</lang>
- 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
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.
So I've therefore used 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. <lang ecmascript>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)</lang>
- 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]