Anonymous user
Numbers which are not the sum of distinct squares: Difference between revisions
Numbers which are not the sum of distinct squares (view source)
Revision as of 14:07, 25 November 2021
, 2 years ago→{{header|Free Pascal}}: OK,"Do not use magic numbers or pre-determined limits" therefore FindLongestContiniuosBlock
(added =={{header|Pascal}}==) |
m (→{{header|Free Pascal}}: OK,"Do not use magic numbers or pre-determined limits" therefore FindLongestContiniuosBlock) |
||
Line 65:
SumOfSquare-2, SumOfSquare-3,SumOfSquare-6,...SumOfSquare-108,SumOfSquare-112,SumOfSquare-128<br>
<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
hs0 := @HasSum[0];
for startIdx := startIdx to MaxIdx do
IF hs0[startIdx]=0 then
inc(l);
end;
FindLongestContiniuosBlock := l;
end;
function SumAllSquares(Limit: Uint32):NativeInt;
Line 75 ⟶ 88:
var
hs0, hs1: pByte;
idx, j, maxlimit, delta,
begin
MaxConOffset := 0;
maxlimit := 0;
hs0 := @HasSum[0];
hs0[0] := 1; //has sum of 0*0
writeln('number longest block sum of');▼
writeln(' starting at 129 squares');▼
idx := 1;
while idx <= Limit do
begin
delta := idx*idx;
//delta is within the continiuos range than break
If
▲ Break;
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;
repeat
for j := 129 to maxlimit do▼
delta := FindLongestContiniuosBlock(j,maxlimit);
▲ Begin
IF
MaxConOffset := j;
▲ end;
end;
writeln(idx:3,len1TopDown:14,maxlimit:14);▼
inc(j,delta+1);
inc(idx);
end;
Line 113 ⟶ 134:
n: NativeInt;
begin
Limit :=
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);
Line 126 ⟶ 149:
setlength(HasSum,0);
{$IFNDEF UNIX} readln; {$ENDIF}
end.
</lang>
{{out}}
<pre>
sum of square [1..
number
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,
</pre>
=={{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,
| |||