Ulam numbers
With the following initial conditions:
u1 = 1
u2 = 2
we define the n-th 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
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 true 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
if length(ulams)=n then exit end if
end while
return ulams[n]
end function
for p=1 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</lang>
- Output:
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
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 nmber is: ", @ulams[10**$_ - 1]
}</lang>
- Output:
The 10th Ulam nmber is: 18 The 100th Ulam nmber is: 690 The 1000th Ulam nmber is: 12294 The 10000th Ulam nmber is: 132788
REXX
<lang rexx>/*REXX program finds and displays all Ulam numbers up to (below) a specified number.*/ parse arg high . /*obtain optional argument from the CL.*/ if high== | high=="," then high= 200 /*Not specified? Then use the default.*/ @.1= 1; @.2= 2 /*define the first two Ulam numbers. */
- = 2 /*the number of Ulam numbers (so far).*/
do j=3; !.= /*search for numbers in this range. */
mx= 0 /*define the maximum sum (so far). */
do a=1 to # /* [+] compute all possible Ulam sums.*/
do b=a+1 to #; s= @.a + @.b /*compute a sum from two Ulam numbers. */
if s<@.# then iterate /*Is the sum is too small? Then skip. */
!.s= !.s s /*append a sum to a list of sums for S.*/
mx= max(mx, s) /*obtain the maximum sum, a later limit*/
end /*b*/
end /*a*/
do f=@.#+1 to 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? " " " */
if f>=high then leave j /*Is the sum>=high? Then we're done.*/
#= # + 1 /*bump the count of Ulam numbers found.*/
@.#= strip(!.f) /*elide and superfluous blanks in list.*/
leave /*now, go and find the next Ulam number*/
end /*f*/
end /*j*/
say # ' Ulam numbers found which are less than ' high":" $=
do k=1 for #; $= $ @.k /*build a list of Ulam numbers. */
end /*k*/
say strip($)</lang>
- output when using the default input:
41 Ulam numbers found which are less than 200: 1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102 106 114 126 131 138 145 148 155 175 177 180 182 189 197
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