Ulam numbers: Difference between revisions
(→{{header|Phix}}: added some timing comparisons) |
m (→{{header|REXX}}: changed a couple of comments.) |
||
| Line 219: | Line 219: | ||
do j=3; !.=; low= @.# /*search for numbers in this range. */ |
do j=3; !.=; low= @.# /*search for numbers in this range. */ |
||
mx= 0 /*define the maximum sum (so far). */ |
mx= 0 /*define the maximum sum (so far). */ |
||
do a=# by -1 for # /* [↓] compute all possible Ulam sums.*/ |
|||
do a=# by -1 for # /* [↑] compute all possible Ulam sums.*/ |
|||
aa= @.a /*scalar var. is faster than a compound*/ |
aa= @.a /*scalar var. is faster than a compound*/ |
||
do b=a-1 by -1 for a-1 /*compute sums from two Ulam numbers. */ |
do b=a-1 by -1 for a-1 /*compute sums from two Ulam numbers. */ |
||
Revision as of 23:31, 2 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
<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
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>
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, Go took 4.9s, Wren (on tio) 27s,
Ring timed out (>60s) on tio before getting the 1,000th number,
Raku (on repl.it) 9mins 50s,
FreeBASIC 17mins 44s (ouch!).
The Haskell entry does not compile on either tio or repl.it
REXX, XPL0 ignored as they only attempt up to the 1,000th number.
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
<lang rexx>/*REXX program finds and displays the Nth Ulam number (or any number of various numbers)*/ parse arg highs /*obtain optional argument from the CL.*/ if highs= | highs="," then highs= 10 100 1000 /*Not specified? Then use the defaults.*/
do i=1 for words(highs)
z= Ulam( word(highs, i) ) /*define the first two Ulam numbers. */
say 'the ' commas(#)th(#) ' Ulam number is: ' commas(@.#)
end /*i*/
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 /*define the first two Ulam numbers. */
#= 2 /*the number of Ulam numbers (so far).*/
do j=3; !.=; low= @.# /*search for numbers in this range. */
mx= 0 /*define the maximum sum (so far). */
do a=# by -1 for # /* [↓] compute all possible Ulam sums.*/
aa= @.a /*scalar var. is faster than a compound*/
do b=a-1 by -1 for a-1 /*compute sums from two Ulam numbers. */
s= aa + @.b /*compute a sum " " " " */
if s<=low then iterate a /*Is the sum is too small? Then skip. */
!.s= !.s s /*append a sum to a list of sums for S.*/
if s>mx then mx= s /*obtain the maximum sum, a later limit*/
end /*b*/
end /*a*/
do f=@.#+1 for mx-@.# /* [↓] find if the sum is unique. */
if !.f== then iterate /*Is the number defined? No, then skip*/
if words(!.f)>1 then iterate /*Is the sum unique? " " " */
#= # + 1 /*bump the count of Ulam numbers found.*/
@.#= strip(!.f) /*assign a new Ulam number (stripped). */
if #==n then leave j /*Found the Nth number? Then we're done*/
leave /*now, go and find the next Ulam number*/
end /*f*/
end /*j*/; return @.# /*return the Nth Ulam number to caller.*/</lang>
- output when using the default inputs:
the 10th Ulam number is: 18 the 100th Ulam number is: 690 the 1,000th Ulam number is: 12,294
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
<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
XPL0
<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:= 0];
];
];
];
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 > 1000; \(faster algorithm needed) ]</lang>
- Output:
The 10th Ulam number is 18 The 100th Ulam number is 690 The 1000th Ulam number is 12294