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:52, 7 January 2024
, 4 months ago→{{header|Wren}}: Changed to Wren S/H
(Added Quackery.) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (10 intermediate revisions by 3 users not shown) | |||
Line 32:
* [[oeis:A001422|OEIS: A001422 Numbers which are not the sum of distinct squares]]
=={{header|ALGOL 68}}==
Recursive brute force (tempting though it is to use 9 nested loops... :) ), using the proof that if 129-324 can be expressed as the sum of distinct squares, then all integers greater than 128 can be so expressed - see the link in the Wren sample.
<syntaxhighlight lang="algol68">
CO 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
CO
BEGIN
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|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}}==
Line 383 ⟶ 482:
</pre>
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight lang=easylang>
maxNumber = 324
len isSum[] maxNumber
maxSquare = floor sqrt maxNumber
#
proc flagSum currSum sqPos . .
nextSum = currSum + sqPos * sqPos
if nextSum <= maxNumber
isSum[nextSum] = 1
for i = sqPos + 1 to maxSquare
flagSum nextSum i
.
.
.
for i = 1 to maxSquare
flagSum 0 i
.
for i = 1 to maxNumber
if isSum[i] = 0
write i & " "
.
.
</syntaxhighlight>
=={{header|Go}}==
Line 639 ⟶ 764:
<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|Lua}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="lua">
do --[[ 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
--]]
local maxNumber = 324
local isSum = {}
local maxSquare = math.floor( math.sqrt( 324 ) )
local square = {} for i = 0,maxSquare do square[ i ] = i * i end
local function flagSum ( currSum, sqPos )
local nextSum = currSum + square[ sqPos ]
if nextSum <= maxNumber then
isSum[ nextSum ] = true
for i = sqPos + 1, maxSquare do
flagSum( nextSum, i )
end
end
end
for i = 0,maxSquare do
flagSum( 0, i )
end
--[[ show the numbers that can't be formed from a sum of distinct squares
and check 129-324 can be so formed
--]]
local unformable = 0
for i = 0, maxNumber do
if not isSum[ i ] then
io.write( string.format( "%4d", i ) )
unformable = unformable + 1
if unformable % 12 == 0 then io.write( "\n" ) end
if i > 128 then
io.write( "\n", "**** unexpected unformable number: ", i, "\n" )
end
end
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>
Line 952 ⟶ 1,127:
=={{header|Quackery}}==
<code>from</code>, <code>index</code>, <code>end</code>, and <code>incr</code> are defined at [[Loops/Increment loop index within loop body#Quackery]].
'''Method'''
Line 962 ⟶ 1,137:
Finally, <code>missing</code> generates a list of the numbers which are not SODS from the list of SODS. (This is why we need to trim the list; so it does not include the numbers which are SODS but had not yet been added to the list.)
<syntaxhighlight lang="Quackery"> [
behead swap
witheach
[ 2dup = iff
drop done
dip join ]
join ] is unique ( [ --> [ )
[ stack ] is cut ( --> s )
[ -1 cut put
1 temp put
Line 968 ⟶ 1,152:
behead swap
witheach
[ tuck - -1 = iff
[ dip 1+
over temp share
> if
[ over
[ nip 1 swap ] ]
2drop
temp take cut take ]
[ [] swap 0 over
Line 984 ⟶ 1,168:
[ dup i^ bit & not if
[ dip [ i^ join ] ] ]
drop ]
1 temp put
Line 1,034 ⟶ 1,218:
===Brute force===
This uses a brute force approach to generate the relevant numbers, similar to Julia, except using the same figures as the above proof. Still slow in Wren, around 20 seconds.
<syntaxhighlight lang="
var combs = []
var results = []
Line 1,089 ⟶ 1,273:
{{libheader|Wren-fmt}}
Hugely quicker in fact - only 24 ms, the same as C# itself.
<syntaxhighlight lang="
import "./fmt" for Fmt
| |||