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 17:23, 15 October 2023
, 7 months agoAdded Algol W
(Added Lua) |
(Added Algol W) |
||
Line 77:
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|ALGOL W}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="algolw">
begin comment find the integers that can't be expressed as the sum of distinct squares
it can be proved that if 120-324 can be expressed as the sum of distinct
squares then all integers greater than 129 can be so expressed
(see the link in the Wren sample) so we need to check that 129-324 can
be so expressed and find the numbers below 129 that can't be so expressed
;
integer MAX_NUMBER, MAX_SQUARE;
MAX_NUMBER := 324;
MAX_SQUARE := entier( sqrt( MAX_NUMBER ) );
begin
logical array isSum ( 0 :: MAX_NUMBER );
integer array square ( 0 :: MAX_SQUARE );
integer unformable;
procedure flagSum ( integer value currSum, sqPos ) ; begin
integer nextSum;
nextSum := currSum + square( sqPos );
if nextSum <= MAX_NUMBER then begin
isSum( nextSum ) := true;
for i := sqPos + 1 until MAX_SQUARE do flagSum( nextSum, i )
end of_nextSum_le_MAX_NUMBER
end flagSum ;
for i := 0 until MAX_NUMBER do isSum( i ) := false;
for i := 0 until MAX_SQUARE do square( i ) := i * i;
for i := 0 until MAX_SQUARE do flagSum( 0, i );
% show the numbers that can't be formed from a sum of distinct squares %
% and check 129-324 can be so formed %
unformable := 0;
for i := 0 until MAX_NUMBER do
if not isSum( i ) then begin
writeon( i_w := 4, s_w := 0, i );
unformable := unformable + 1;
if unformable rem 12 = 0 then write();
if i > 128 then write( i_w := 1, s_w := 0, "**** unexpected unformable number: ", i )
end if_not_isSum__i
end
end.
</syntaxhighlight>
{{out}}
<pre>
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|C#|CSharp}}==
| |||