Ulam numbers: Difference between revisions
→{{header|Wren}}: Added second faster version based on Phix algorithm.
m (→{{header|REXX}}: changed a DO end comment.) |
(→{{header|Wren}}: Added second faster version based on Phix algorithm.) |
||
Line 334:
=={{header|Wren}}==
===Version 1===
{{libheader|Wren-set}}
<lang ecmascript>import "/set" for Set
Line 372 ⟶ 373:
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788
</pre>
===Version 2===
{{trans|Phix}}
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
The above version is reasonably efficient and runs in about 21.6 seconds on my machine (Intel Core i7-8565U). The following version, which builds up a sieve as it goes along, is more than 3 times faster.
<lang ecmascript>import "/seq" for Lst
import "/fmt" for Fmt
var ulam = Fn.new { |n|
var ulams = [1, 2]
var sieve = [1, 1]
var u = 2
while (ulams.count < n) {
var s = u + ulams[-2]
sieve = sieve + ([0] * (s - sieve.count))
for (i in 1..ulams.count - 1) {
var v = u + ulams[i-1] - 1
sieve[v] = sieve[v] + 1
}
u = Lst.indexOf(sieve, 1, u) + 1
ulams.add(u)
}
return ulams[n-1]
}
var start = System.clock
for (p in 0..4) {
var n = 10.pow(p)
Fmt.print("The $,r Ulam number is $,d", n, ulam.call(n))
}
System.print("\nTook %(System.clock - start) seconds.")</lang>
{{out}}
<pre>
The 1st Ulam number is 1
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1,000th Ulam number is 12,294
The 10,000th Ulam number is 132,788
Took 6.366709 seconds.
</pre>
| |||