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 10:25, 25 November 2021
, 2 years agoadded =={{header|Pascal}}==
(added =={{header|Pascal}}==) |
|||
Line 56:
[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|Pascal}}==
==={{header|Free Pascal}}===
Modified [[Practical_numbers#Pascal]].<BR>
Searching for a block of numbers that are all a possible sum of square numbers.<br>
There is a symmetry of hasSum whether<br>
2,3,6,..108,112,128,<br>
are not reachably nor<br>
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 SumAllSquares(Limit: Uint32):NativeInt;
//mark sum and than shift by next summand == add
var
hs0, hs1: pByte;
idx, j, maxlimit, delta,len1TopDown: NativeInt;
begin
len1TopDown :=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;
If len1TopDown-129 > 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;
//search for a block of only '1' in this block all numbers are possible sum of squarenumbers
len1TopDown :=0;
for j := 129 to maxlimit do
Begin
IF hs0[j]=0 then
BREAK;
inc(len1TopDown);
end;
writeln(idx:3,len1TopDown:14,maxlimit:14);
inc(idx);
end;
SumAllSquares:= idx;
end;
var
limit,
sumsquare,
n: NativeInt;
begin
Limit := 100;
sumsquare := 0;
for n := 1 to Limit do
sumsquare := sumsquare+n*n;
writeln('sum of square [1..',limit,'] = ',sumsquare) ;
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>
{{out}}
<pre>
sum of square [1..100] = 338350
number longest block sum of
starting at 129 squares
1 0 1
2 0 5
3 0 14
4 0 30
5 0 55
6 0 91
7 0 140
8 3 204
9 28 285
10 128 +2*128+1= 385
11 249 +257 = 506
12 393 +257 = 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,
| |||