Ulam numbers: Difference between revisions
(→{{header|Wren}}: Added second faster version based on Phix algorithm.) |
(→{{header|Go}}: Added second astonishingly fast version based on Phix algorithm.) |
||
Line 61: | Line 61: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
===Version 1=== |
|||
{{trans|Wren}} |
{{trans|Wren}} |
||
<lang go>package main |
<lang go>package main |
||
Line 105: | Line 106: | ||
The 1000th Ulam number is 12294 |
The 1000th Ulam number is 12294 |
||
The 10000th Ulam number is 132788 |
The 10000th Ulam number is 132788 |
||
</pre> |
|||
===Version 2=== |
|||
{{trans|Phix}} |
|||
The above version is reasonably efficient and runs in about 2.9 seconds on my machine (Intel Core i7-8565U). The following version, which builds up a sieve as it goes along, is (astonishingly) about 40 times faster! |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"time" |
|||
) |
|||
func ulam(n int) int { |
|||
ulams := []int{1, 2} |
|||
sieve := []int{1, 1} |
|||
u := 2 |
|||
for len(ulams) < n { |
|||
s := u + ulams[len(ulams)-2] |
|||
t := s - len(sieve) |
|||
for i := 0; i < t; i++ { |
|||
sieve = append(sieve, 0) |
|||
} |
|||
for i := 1; i <= len(ulams)-1; i++ { |
|||
v := u + ulams[i-1] - 1 |
|||
sieve[v]++ |
|||
} |
|||
index := -1 |
|||
for i, e := range sieve[u:] { |
|||
if e == 1 { |
|||
index = u + i |
|||
break |
|||
} |
|||
} |
|||
u = index + 1 |
|||
ulams = append(ulams, u) |
|||
} |
|||
return ulams[n-1] |
|||
} |
|||
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 := 1; n <= 10000; n *= 10 { |
|||
s := "th" |
|||
if n == 1 { |
|||
s = "st" |
|||
} |
|||
fmt.Println("The", commatize(n), "\b"+s+" Ulam number is", commatize(ulam(n))) |
|||
} |
|||
fmt.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 74.45373ms |
|||
</pre> |
</pre> |
||
Revision as of 14:15, 4 December 2020
With the following initial conditions:
u1 = 1 u2 = 2
we define the nth Ulam number un as the number that is greater than un-1 and
uniquely written as a sum of two different Ulam numbers ui (<n) and uj (<n).
- Task
Write a function to generate the n-th Ulam number.
- References
FreeBASIC
<lang freebasic>redim as uinteger ulam(1 to 2) ulam(1) = 1 : ulam(2) = 2
function get_ulam( n as uinteger, ulam() as uinteger ) as uinteger
dim as uinteger nu = ubound(ulam), c, r, s, t, i, usr if n <= nu then return ulam(n) 'if we have already calculated this one, just return it 'otherwise, calculate it and all intermediate terms redim preserve ulam(1 to n) for t = nu+1 to n i = ulam(t-1) while true i += 1 : c = 0 for r = 1 to t-2 for s = r+1 to t-1 usr = ulam(s)+ulam(r) if usr > i then exit for 'efficiency if usr = i then if c = 1 then continue while c += 1 end if next s next r if c = 0 then continue while 'I'm not 100% sure this is even possible... ulam(t) = i exit while wend next t return ulam(n)
end function
for i as uinteger = 1 to 4
print 10^i, get_ulam(10^i, ulam())
next i </lang>
- Output:
10 18 100 690 1000 12294 10000 132788
Go
Version 1
<lang go>package main
import "fmt"
func ulam(n int) int {
ulams := []int{1, 2} set := map[int]bool{1: true, 2: true} i := 3 for { count := 0 for j := 0; j < len(ulams); j++ { _, ok := set[i-ulams[j]] if ok && ulams[j] != (i-ulams[j]) { count++ if count > 2 { break } } } if count == 2 { ulams = append(ulams, i) set[i] = true if len(ulams) == n { break } } i++ } return ulams[n-1]
}
func main() {
for n := 10; n <= 10000; n *= 10 { fmt.Println("The", n, "\bth Ulam number is", ulam(n)) }
}</lang>
- Output:
The 10th Ulam number is 18 The 100th Ulam number is 690 The 1000th Ulam number is 12294 The 10000th Ulam number is 132788
Version 2
The above version is reasonably efficient and runs in about 2.9 seconds on my machine (Intel Core i7-8565U). The following version, which builds up a sieve as it goes along, is (astonishingly) about 40 times faster! <lang go>package main
import (
"fmt" "time"
)
func ulam(n int) int {
ulams := []int{1, 2} sieve := []int{1, 1} u := 2 for len(ulams) < n { s := u + ulams[len(ulams)-2] t := s - len(sieve) for i := 0; i < t; i++ { sieve = append(sieve, 0) } for i := 1; i <= len(ulams)-1; i++ { v := u + ulams[i-1] - 1 sieve[v]++ } index := -1 for i, e := range sieve[u:] { if e == 1 { index = u + i break } } u = index + 1 ulams = append(ulams, u) } return ulams[n-1]
}
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 := 1; n <= 10000; n *= 10 { s := "th" if n == 1 { s = "st" } fmt.Println("The", commatize(n), "\b"+s+" Ulam number is", commatize(ulam(n))) } fmt.Println("\nTook", time.Since(start))
}</lang>
- Output:
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 74.45373ms
Haskell
Lazy List
<lang haskell> import Data.List
ulam
:: Integral i => Int -> i
ulam 1 = 1 ulam 2 = 2 ulam n
| n > 2 = ulams !! (n-1)
ulams
:: Integral n => [n]
ulams = 1:2:(nexts [2,1]) nexts us = u: (nexts (u:us))
where n = length us [u] = head . filter isSingleton . group . sort $ [v | i <- [0 .. n-2], j <- [i+1 .. n-1] , let s = us !! i , let t = us !! j , let v = s+t , v > head us ]
isSingleton :: [a] -> Bool isSingleton as
| length as == 1 = True | otherwise = False</lang>
Julia
<lang julia>function nthUlam(n)
ulams = [1, 2] memoized = Set([1, 2]) i = 3 while true count = 0 for j in 1:length(ulams) if i - ulams[j] in memoized && ulams[j] != i - ulams[j] (count += 1) > 2 && break end end if count == 2 push!(ulams, i) push!(memoized, i) length(ulams) == n && break end i += 1 end return ulams[n]
end
nthUlam(5)
for n in [10, 100, 1000, 10000]
@time println("The ", n, "th Ulam number is: ", nthUlam(n))
end
</lang>
- Output:
The 10th Ulam number is: 18 0.000657 seconds (27 allocations: 1.422 KiB) The 100th Ulam number is: 690 0.000959 seconds (39 allocations: 7.094 KiB) The 1000th Ulam number is: 12294 0.027564 seconds (52 allocations: 72.188 KiB) The 10000th Ulam number is: 132788 3.076024 seconds (63 allocations: 473.125 KiB)
Phix
<lang Phix>function ulam(integer n)
sequence ulams = {1, 2}, sieve = {1, 1} integer u := 2 while length(ulams)<n do integer s = u+ulams[$-1] sieve &= repeat(0,s-length(sieve)) for i=1 to length(ulams)-1 do sieve[u+ulams[i]] += 1 end for u = find(1,sieve,u+1) ulams &= u end while return ulams[n]
end function
atom t0 = time() for p=0 to 4 do
integer n = power(10,p) printf(1,"The %,d%s Ulam number is %,d\n",{n,ord(n),ulam(n)})
end for ?elapsed(time()-t0)</lang>
- Output:
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 "2.5s"
For comparison, Julia took 4.5s (9.3s on repl.it), Go took 4.9s, Wren (on tio) 27s,
Ring timed out (>60s) on tio before getting the 1,000th number,
REXX (also on tio) got to the 1,000th number in 12.3s but timed out before getting the 10,000th,
Raku (on repl.it) 9mins 50s,
FreeBASIC 17mins 44s, and I cancelled XPL0 (on EXPL32) after 53 minutes.
The Haskell entry does not compile for me on either tio or repl.it
The above algorithm can also yield "The 100,000th Ulam number is 1,351,223" in 4 minutes and 14s, for me. (I fully expect translations of this better algorithm to run even faster, btw)
Raku
<lang perl6>my @ulams = 1, 2, &next-ulam … *;
sub next-ulam {
state $i = 1; state @sums = 0,1,1; my $last = @ulams[$i]; (^$i).map: { @sums[@ulams[$_] + $last]++ }; ++$i; quietly ($last ^.. *).first: { @sums[$_] == 1 };
}
for 1 .. 4 {
say "The {10**$_}th Ulam number is: ", @ulams[10**$_ - 1]
}</lang>
- Output:
The 10th Ulam number is: 18 The 100th Ulam number is: 690 The 1000th Ulam number is: 12294 The 10000th Ulam number is: 132788
REXX
This REXX version has several speed improvements. <lang rexx>/*REXX program finds and displays the Nth Ulam number (or any number of various numbers)*/ parse arg $ /*obtain optional argument from the CL.*/ if $= | $="," then $= 10 100 1000 10000 /*Not specified? Then use the defaults.*/
do k=1 for words($) x= Ulam( word($, k) ) /*define the first two Ulam numbers. */ say 'the ' commas(#)th(#) ' Ulam number is: ' commas(x) end /*k*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ th: parse arg th; return word('th st nd rd', 1 + (th//10)*(th//100%10\==1)*(th//10<4)) /*──────────────────────────────────────────────────────────────────────────────────────*/ Ulam: parse arg n; @.1= 1; @.2=2; #= 2 /*1st two terms; #: sequence length. */
!.= 0; !.1= 1; !.2=1 /*semaphore for each term in sequence. */ z= 3 /*value of next possible term in seq. */ do until #==n cnt= 0 do j=1 for #; _= z - @.j /*_: short circuit value.*/ if !._ then if @.j\==_ then do; cnt= cnt + 1 if cnt>2 then leave end end /*j*/
if cnt==2 then do; #= # + 1 /*bump the number of terms*/ @.#= z; !.z= 1 /*add I to sequence; bool.*/ end z= z + 1 /*bump the next poss. term*/ end /*until*/ return @.#</lang>
- output when using the default input of: 10 100 1000 10000
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
Ring
<lang ring> load "stdlib.ring"
limit = 12500 Ulam = [] add(Ulam,1) add(Ulam,2)
for n = 3 to limit
flag = 0 count = 0 len = len(Ulam) for x = 1 to len-1 for y = x+1 to len if Ulam[x] + Ulam[y] = n flag = 1 count = count + 1 ok next next if flag = 1 and count = 1 add(Ulam,n) ln = len(Ulam) if ln = 10 see "The 10th Ulam number is: " + n + nl ok if ln = 100 see "The 100th Ulam number is: " + n + nl ok if ln = 1000 see "The 1000th Ulam number is: " + n + nl ok if ln = 10000 see "The 10000th Ulam number is: " + n + nl ok ok
next </lang> Output:
The 10th Ulam number is: 18 The 100th Ulam number is: 690 The 1000th Ulam number is: 12294 The 10000th Ulam number is: 132788
Wren
Version 1
<lang ecmascript>import "/set" for Set
var ulam = Fn.new() { |n|
var ulams = [1, 2] var set = Set.new(ulams) var i = 3 while (true) { var count = 0 for (j in 0...ulams.count) { if (set.contains(i - ulams[j]) && ulams[j] != (i - ulams[j])) { count = count + 1 if (count > 2) break } } if (count == 2) { ulams.add(i) set.add(i) if (ulams.count == n) break } i = i + 1 } return ulams[-1]
}
var n = 1 while (true) {
n = n * 10 System.print("The %(n)th Ulam number is %(ulam.call(n))") if (n == 10000) break
}</lang>
- Output:
The 10th Ulam number is 18 The 100th Ulam number is 690 The 1000th Ulam number is 12294 The 10000th Ulam number is 132788
Version 2
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>
- Output:
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.
XPL0
This version is three times faster than before. It takes 20 minutes on a Pi4. <lang XPL0>func Ulam(N); \Return Nth Ulam number int N; int List, Size, L, H, Query, Sum, Cnt; [if N < 3 then return N; List:= Reserve(0); List(0):= 1; List(1):= 2; Size:= 2; repeat Query:= List(Size-1) + 1; \possible next member
loop [Cnt:= 0; for H:= Size-1 downto 1 do [for L:= 0 to H-1 do [Sum:= List(L) + List(H); if Sum > Query then L:= Size \exit L for loop else if Sum = Query then [Cnt:= Cnt+1; if Cnt >= 2 then \exit both for loops [L:= Size; H:= 1]; ]; ]; if Sum < Query then H:= 1; \exit H for loop ]; if Cnt = 1 then \sum was unique [List(Size):= Query; Size:= Size+1; quit; \quit loop ]; Query:= Query+1; \possible next member ];
until Size >= N; return Query; ];
int N; [N:= 10; repeat Text(0, "The "); IntOut(0, N);
Text(0, "th Ulam number is "); IntOut(0, Ulam(N)); CrLf(0); N:= N*10;
until N > 10000; ]</lang>
- Output:
The 10th Ulam number is 18 The 100th Ulam number is 690 The 1000th Ulam number is 12294 The 10000th Ulam number is 132788