Numbers which are not the sum of distinct squares: Difference between revisions
Content added Content deleted
m (→{{header|Quackery}}: improved commentary) |
(Added Algol 68) |
||
Line 32: | Line 32: | ||
* [[oeis:A001422|OEIS: A001422 Numbers which are not the sum of distinct squares]] |
* [[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}}== |
=={{header|C#|CSharp}}== |