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 16:19, 15 October 2023
, 7 months agoAdded Algol 68
m (→{{header|Quackery}}: improved commentary) |
(Added Algol 68) |
||
Line 32:
* [[oeis:A001422|OEIS: A001422 Numbers which are not the sum of distinct squares]]
=={{header|ALGOL 68}}==
Recursive brute force.
<syntaxhighlight lang="algol68">
BEGIN # 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 #
# 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 #
INT max number = 324;
[ 0 : max number ]BOOL is sum; FOR i FROM LWB is sum TO UPB is sum DO is sum[ i ] := FALSE OD;
INT max square = ENTIER sqrt( 324 );
[ 0 : max square ]INT square; FOR i FROM LWB square TO UPB square DO square[ i ] := i * i OD;
PROC flag sum = ( INT curr sum, sq pos )VOID:
IF INT next sum = curr sum + square[ sq pos ];
next sum <= UPB is sum
THEN
is sum[ next sum ] := TRUE;
FOR i FROM sq pos + 1 TO UPB square DO
flag sum( next sum, i )
OD
FI # flag sum # ;
FOR i FROM LWB square TO UPB square DO
flag sum( 0, i )
OD;
# show the numbers that can't be formed from a sum of distinct squares #
# and check 129-324 can be so formed #
INT unformable := 0;
FOR i FROM LWB is sum TO UPB is sum DO
IF NOT is sum[ i ] THEN
print( ( whole( i, -4 ) ) );
IF ( unformable +:= 1 ) MOD 12 = 0 THEN print( ( newline ) ) FI;
IF i > 128 THEN
print( ( newline, "**** unexpected unformable number: ", whole( i, 0 ), newline ) )
FI
FI
OD
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}}==
| |||