Ulam numbers: Difference between revisions
→{{header|Go}}: Added a third version based on the XPL0 algorithm.
m (→{{header|REXX}}: added the 100,000 Ulam number.) |
(→{{header|Go}}: Added a third version based on the XPL0 algorithm.) |
||
Line 183:
Took 74.45373ms
</pre>
===Version 3===
{{trans|XPL0}}
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 go>package main
import (
"fmt"
"time"
)
func ulam(n int) int {
if n <= 2 {
return n
}
const MAX = 1_352_000
list := make([]int, MAX+1)
list[0], list[1] = 1, 2
sums := make([]byte, 2*MAX+1)
sums[3] = 1
size := 2
var query int
for {
query = list[size-1] + 1
for {
if sums[query] == 1 {
for i := 0; i < size; i++ {
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
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n)
if n < 0 {
s = s[1:]
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if n >= 0 {
return s
}
return "-" + s
}
func main() {
start := time.Now()
for n := 10; n <= 100000; n *= 10 {
fmt.Println("The", commatize(n), "\bth Ulam number is", commatize(ulam(n)))
}
fmt.Println("\nTook", time.Since(start))
}</lang>
{{out}}
<pre>
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 3.226255944s
</pre>
| |||