Ulam numbers: Difference between revisions
no edit summary
No edit summary |
|||
Line 1,308:
Took 9.611s
</pre>
===Version 2===
{{trans|Go}}
The following version, which builds up a sieve as it goes along, is (astonishingly) about 40 times faster!
<lang go>import time
fn ulam(n int) int {
mut ulams := [1, 2]
mut sieve := [1, 1]
mut u := 2
for ulams.len < n {
s := u + ulams[ulams.len-2]
t := s - sieve.len
for i := 0; i < t; i++ {
sieve << 0
}
for i := 1; i <= ulams.len-1; i++ {
v := u + ulams[i-1] - 1
sieve[v]++
}
mut index := -1
for i, e in sieve[u..] {
if e == 1 {
index = u + i
break
}
}
u = index + 1
ulams << u
}
return ulams[n-1]
}
fn commatize(n int) string {
mut s := '$n'
if n < 0 {
s = s[1..]
}
le := s.len
for i := le - 3; i >= 1; i -= 3 {
s = '${s[0..i]},${s[i..]}'
}
if n >= 0 {
return s
}
return "-$s"
}
fn main() {
start := time.now()
for n := 1; n <= 10000; n *= 10 {
mut s := "th"
if n == 1 {
s = "st"
}
println("The ${commatize(n)}$s Ulam number is ${commatize(ulam(n))}")
}
println("\nTook ${time.since(start)}")
}</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 415.000ms
</pre>
| |||