Anonymous user
Ulam numbers: Difference between revisions
→{{header|Lua}}: added Lua solution
SqrtNegInf (talk | contribs) (Added Perl) |
(→{{header|Lua}}: added Lua solution) |
||
Line 373:
3.076024 seconds (63 allocations: 473.125 KiB)
</pre>
=={{header|Lua}}==
Implemented from scratch, but algorithmically equivalent to other solutions where a running count of number-of-ways-to-reach-sum is maintained in order to sieve candidate values.
<lang lua>function ulam(n)
local ulams, nways, i = { 1,2 }, { 0,0,1 }, 3
repeat
if nways[i] == 1 then
for j = 1, #ulams do
local sum = i + ulams[j]
nways[sum] = (nways[sum] or 0) + 1
end
ulams[#ulams+1] = i
end
i = i + 1
until #ulams == n
return ulams[#ulams]
end
for _,n in ipairs({10,100,1000,10000,100000}) do
local s, u, e = os.clock(), ulam(n), os.clock()
print(string.format("%dth is %d (%f seconds elapsed)", n, u, e-s))
end</lang>
{{out}}
Times are Lua 5.4 on i7-2600@3.4GHz
<pre>10th is 18 (0.000000 seconds elapsed)
100th is 690 (0.000000 seconds elapsed)
1000th is 12294 (0.020000 seconds elapsed)
10000th is 132788 (1.724000 seconds elapsed)
100000th is 1351223 (277.824000 seconds elapsed)</pre>
=={{header|Perl}}==
| |||