Numbers which are not the sum of distinct squares: Difference between revisions

Content added Content deleted
(added =={{header|Pascal}}==)
m (→‎{{header|Free Pascal}}: OK,"Do not use magic numbers or pre-determined limits" therefore FindLongestContiniuosBlock)
Line 65: Line 65:
SumOfSquare-2, SumOfSquare-3,SumOfSquare-6,...SumOfSquare-108,SumOfSquare-112,SumOfSquare-128<br>
SumOfSquare-2, SumOfSquare-3,SumOfSquare-6,...SumOfSquare-108,SumOfSquare-112,SumOfSquare-128<br>
<lang pascal>program practicalnumbers;
<lang pascal>program practicalnumbers;
{$IFDEF Windows}
{$IFDEF Windows} {$APPTYPE CONSOLE} {$ENDIF}
{$APPTYPE CONSOLE}
{$ENDIF}
var
var
HasSum: array of byte;
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;
function SumAllSquares(Limit: Uint32):NativeInt;
Line 75: Line 88:
var
var
hs0, hs1: pByte;
hs0, hs1: pByte;
idx, j, maxlimit, delta,len1TopDown: NativeInt;
idx, j, maxlimit, delta,MaxContiniuos,MaxConOffset: NativeInt;
begin
begin
len1TopDown :=0;
MaxContiniuos := 0;
MaxConOffset := 0;
maxlimit := 0;
maxlimit := 0;
hs0 := @HasSum[0];
hs0 := @HasSum[0];
hs0[0] := 1; //has sum of 0*0
hs0[0] := 1; //has sum of 0*0
⚫
writeln('number longest block sum of');
⚫
writeln(' starting at 129 squares');
idx := 1;
idx := 1;

⚫
writeln('number offset longest sum of');
⚫
writeln(' block squares');
while idx <= Limit do
while idx <= Limit do
begin
begin
delta := idx*idx;
delta := idx*idx;
//delta is within the continiuos range than break
If len1TopDown-129 > delta then
If (MaxContiniuos-MaxConOffset) > delta then
⚫
Break;
BREAK;

//mark oldsum+ delta with oldsum
//mark oldsum+ delta with oldsum
hs1 := @hs0[delta];
hs1 := @hs0[delta];
for j := maxlimit downto 0 do
for j := maxlimit downto 0 do
hs1[j] := hs1[j] or hs0[j];
hs1[j] := hs1[j] or hs0[j];

maxlimit := maxlimit + delta;
maxlimit := maxlimit + delta;

//search for a block of only '1' in this block all numbers are possible sum of squarenumbers
len1TopDown :=0;
j := MaxConOffset;
repeat
⚫
for j := 129 to maxlimit do
delta := FindLongestContiniuosBlock(j,maxlimit);
⚫
Begin
IF hs0[j]=0 then
IF delta>MaxContiniuos then
BREAK;
begin
inc(len1TopDown);
MaxContiniuos:= delta;
MaxConOffset := j;
⚫
end;
end;
⚫
writeln(idx:3,len1TopDown:14,maxlimit:14);
inc(j,delta+1);
⚫
until j > (maxlimit-delta);
⚫
writeln(idx:4,MaxConOffset:7,MaxContiniuos:8,maxlimit:8);
inc(idx);
inc(idx);
end;
end;
Line 113: Line 134:
n: NativeInt;
n: NativeInt;
begin
begin
Limit := 100;
Limit := 25;
sumsquare := 0;
sumsquare := 0;
for n := 1 to Limit do
for n := 1 to Limit do
sumsquare := sumsquare+n*n;
sumsquare := sumsquare+n*n;
writeln('sum of square [1..',limit,'] = ',sumsquare) ;
writeln('sum of square [1..',limit,'] = ',sumsquare) ;
writeln;
setlength(HasSum,sumsquare+1);
setlength(HasSum,sumsquare+1);
n := SumAllSquares(Limit);
n := SumAllSquares(Limit);
Line 126: Line 149:
setlength(HasSum,0);
setlength(HasSum,0);
{$IFNDEF UNIX} readln; {$ENDIF}
{$IFNDEF UNIX} readln; {$ENDIF}
end.</lang>
end.
</lang>
{{out}}
{{out}}
<pre>
<pre>
sum of square [1..100] = 338350
sum of square [1..25] = 5525

number longest block sum of
number offset longest sum of
starting at 129 squares
1 0 1
block squares
2 0 5
1 0 2 1 -> 0,1
3 0 14
2 0 2 5
4 0 30
3 0 2 14
5 0 55
4 0 2 30
6 0 91
5 0 2 55
7 0 140
6 34 9 91 ->34..42
8 3 204
7 49 11 140 ->49..59
9 28 285
8 77 15 204 ->77..91
10 128 +2*128+1= 385
9 129 28 285
11 249 +257 = 506
10 129 128 385
12 393 +257 = 650
11 129 249 506
12 129 393 650
13
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,
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,
</pre>
</pre>

=={{header|Phix}}==
=={{header|Phix}}==
As per Raku (but this is using a simple flag array), if we find a block of n<sup><small>2</small></sup> summables,
As per Raku (but this is using a simple flag array), if we find a block of n<sup><small>2</small></sup> summables,
Retrieved from "https://rosettacode.org/wiki/Numbers_which_are_not_the_sum_of_distinct_squares"