Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
(added =={{header|Pascal}}==) |
|||
Line 56: | 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] |
[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|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}}== |
=={{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, |