Ulam numbers: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
Line 1,377:
Took 415.000ms
</pre>
===Version 3===
{{trans|Go}}
This version is even quicker than Version 2 and reduces the time needed to calculate the 10,000th and 100,000th Ulam numbers to about 40 milliseconds and 3.25 seconds respectively.
As mentioned in the Wren version 3 example, you need to know how much memory to allocate in advance.
<lang vlang>import time
fn ulam(n int) int {
if n <= 2 {
return n
}
max := 1_352_000
mut list := []int{len:max+1}
list[0], list[1] = 1, 2
mut sums := []byte{len:2*max+1}
sums[3] = 1
mut size := 2
mut query := 0
for {
query = list[size-1] + 1
for {
if sums[query] == 1 {
for i in 0..size {
sum := query + list[i]
t := sums[sum] + 1
if t <= 2 {
sums[sum] = t
}
}
list[size] = query
size++
break
}
query++
}
if size >= n {
break
}
}
return query
}
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 <= 100000; 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
The 100,000th Ulam number is 1,351,223
Took 42.912s
</pre>
| |||