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:59, 15 October 2023
, 7 months agoAdded Lua
(→{{header|ALGOL 68}}: More notes) |
(Added Lua) |
||
Line 685:
<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 endnd 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>
| |||