I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Ulam numbers

From Rosetta Code
Ulam numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

With the following initial conditions:

      u1 = 1 
      u2 = 2 

We define the   nth   Ulam number   un   as the smallest number that is greater than   un-1     and
is the unique sum of two different Ulam numbers   ui (<n)   and   uj (<n).


Task

Write a function to generate the   n-th   Ulam number.


References



AWK[edit]

 
# syntax: GAWK -f ULAM_NUMBERS.AWK
BEGIN {
u = split("1,2",ulam,",")
for (n=3; ; n++) {
count = 0
for (x=1; x<=u-1; x++) {
for (y=x+1; y<=u; y++) {
if (ulam[x] + ulam[y] == n) {
count++
}
}
}
if (count == 1) {
ulam[++u] = n
if (u ~ /^(10|50|100|500|1000)$/) {
printf("%6d %6d\n",u,n)
if (++shown >= 5) { break }
}
}
}
exit(0)
}
 
Output:
    10     18
    50    253
   100    690
   500   5685
  1000  12294

FreeBASIC[edit]

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
 
Output:
 10          18
 100          690
 1000        12294
 10000        132788

Go[edit]

Version 1[edit]

Translation of: Wren
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))
}
}
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[edit]

Translation of: 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!

Although not shown here, the 100,000th Ulam number (1,351,223) is computed in about 13.5 seconds.

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))
}
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

Version 3[edit]

Translation of: 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.

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))
}
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
The 100,000th Ulam number is 1,351,223

Took 3.226255944s

Haskell[edit]

Lazy List[edit]

 
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


Julia[edit]

Translation of: Wren
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
 
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)

Perl[edit]

Translation of: Julia
use strict;
use warnings;
use feature <say state>;
 
sub ulam {
my($n) = @_;
state %u = (1 => 1, 2 => 1);
state @ulams = <0 1 2>; # 0 a placeholder to shift indexing up one
 
return $ulams[$n] if $ulams[$n];
 
$n++;
my $i = 3;
 
while () {
my $count = 0;
 
$u{ $i - $ulams[$_] }
and $ulams[$_] != $i - $ulams[$_]
and $count++ > 2
and last
for 0..$#ulams;
 
$count == 2
and push(@ulams,$i)
and $u{$i} = 1
and @ulams == $n
and last;
 
$i++;
}
$ulams[$n-1];
}
 
printf "The %dth Ulam number is: %d\n", 10**$_, ulam(10**$_) for 1..4;
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
The 10000th Ulam number is: 132788

Phix[edit]

function ulam(integer n)
sequence ulams = {1, 2},
sieve = {1, 1}
integer u := 2
while length(ulams)<n do
integer s = u+ulams[$-1], t
sieve &= repeat(0,s-length(sieve))
for i=1 to length(ulams)-1 do
s = u+ulams[i]
t = sieve[s]+1
if t<=2 then
sieve[s] = t
end if
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)
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
"1.0s"

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 1 minute and 40s, for me. (I fully expect translations of this better algorithm to run even faster, btw)


Python[edit]

Translation of: XPL0
import time
 
def ulam(n):
if n <= 2:
return n
mx = 1352000
lst = [1, 2] + [0] * mx
sums = [0] * (mx * 2 + 1)
sums[3] = 1
size = 2
while size < n:
query = lst[size-1] + 1
while True:
if sums[query] == 1:
for i in range(size):
sum = query + lst[i]
t = sums[sum] + 1
if t <= 2:
sums[sum] = t
lst[size], size = query, size + 1
break
query += 1
return query
 
t0 = time.time()
for p in range(5):
n = 10**p
print(f"The {n}{'th' if n!=1 else 'st'} Ulam number is {ulam(n)}")
 
print("\nElapsed time:", time.time() - t0)
 
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

(Elapsed time: 11.470759391784668 seconds)
Extra
In [1]: %time ulam(100_000)
Wall time: 23min 58s
Out[1]: 1351223

In [37]: 

Raku[edit]

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]
}
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[edit]

Translation of: Wren

This REXX version has several speed improvements.

/*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 @.#
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
output   (courtesy of Paul Kislanko's PC)   when using the input of:     100000
the  100,000th  Ulam number is:  1,351,223

Ring[edit]

 
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
 

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[edit]

Version 1[edit]

Library: Wren-set
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
}
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[edit]

Translation of: Phix
Library: Wren-seq
Library: Wren-fmt

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.

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.")
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.

Version 3[edit]

Translation of: XPL0

This version is even quicker than Version 2 and reduces the time needed to calculate the 10,000th Ulam number to about 3.65 seconds. It also makes the 100,000th Ulam number a viable proposition for the Wren interpreter coming in at about 6 minutes 50 seconds.

The only downside with this version is that you need to know how much memory to allocate in advance.

import "/fmt" for Fmt
 
var ulam = Fn.new { |n|
if (n <= 2) return n
var max = 1352000
var list = List.filled(max+1, 0)
list[0] = 1
list[1] = 2
var sums = List.filled(max*2+1, 0)
sums[3] = 1
var size = 2
var query
while (true) {
query = list[size-1] + 1
while (true) {
if (sums[query] == 1) {
for (i in 0..size-1) {
var sum = query + list[i]
var t = sums[sum] + 1
if (t <= 2) sums[sum] = t
}
list[size] = query
size = size + 1
break
}
query = query + 1
}
if (size >= n) break
}
return query
}
 
var start = System.clock
var n = 10
while (true) {
Fmt.print("The $,r Ulam number is $,d", n, ulam.call(n))
n = n * 10
if (n > 100000) break
}
System.print("\nTook %(System.clock - start) seconds.")
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
The 100,000th Ulam number is 1,351,223

Took 409.990502 seconds.

XPL0[edit]

Seeing "set" in the Go version and "sieve" in Phix, etc. lit a little light bulb. This version exploits those ideas and finds the 100,000th Ulam number in 24.7 seconds on a Pi4.

func    Ulam(N);                \Return Nth Ulam number
int N;
def Max = 1_352_000; \enough for 100_000th Ulam number
int List(Max); \array of Ulam numbers
char Sums(Max*2); \array: 0, 1, or more ways to sum Ulams
int I, Size, Query, Sum, T;
[if N <= 2 then return N;
for I:= 0 to Max*2 do Sums(I):= 0;
List(0):= 1; List(1):= 2;
Sums(3):= 1; \only one way to sum Ulams: 1+2 = 3
Size:= 2; \start after first 2 Ulams
repeat Query:= List(Size-1)+1; \possible next Ulam no.
loop [if Sums(Query) = 1 then \sums 1 way so it's next
[for I:= 0 to Size-1 do \update Sums array with
[Sum:= Query + List(I); \ all combos of sums
T:= Sums(Sum)+1; \ but limit max count
if T <= 2 then Sums(Sum):= T;
];
List(Size):= Query; \add Query to List
Size:= Size+1;
quit;
];
Query:= Query+1; \possible next Ulam no.
];
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 > 100_000;
]
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
The 100000th Ulam number is 1351223