Ulam numbers: Difference between revisions
No edit summary |
No edit summary |
||
Line 1,377: | Line 1,377: | ||
Took 415.000ms |
Took 415.000ms |
||
</pre> |
|||
===Version 3=== |
|||
{{trans|Go}} |
|||
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 vlang>import time |
|||
fn ulam(n int) int { |
|||
if n <= 2 { |
|||
return n |
|||
} |
|||
max := 1_352_000 |
|||
mut list := []int{len:max+1} |
|||
list[0], list[1] = 1, 2 |
|||
mut sums := []byte{len:2*max+1} |
|||
sums[3] = 1 |
|||
mut size := 2 |
|||
mut query := 0 |
|||
for { |
|||
query = list[size-1] + 1 |
|||
for { |
|||
if sums[query] == 1 { |
|||
for i in 0..size { |
|||
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 |
|||
} |
|||
fn commatize(n int) string { |
|||
mut s := '$n' |
|||
if n < 0 { |
|||
s = s[1..] |
|||
} |
|||
le := s.len |
|||
for i := le - 3; i >= 1; i -= 3 { |
|||
s = '${s[0..i]},${s[i..]}' |
|||
} |
|||
if n >= 0 { |
|||
return s |
|||
} |
|||
return "-$s" |
|||
} |
|||
fn main() { |
|||
start := time.now() |
|||
for n := 1; n <= 100000; n *= 10 { |
|||
mut s := "th" |
|||
if n == 1 { |
|||
s = "st" |
|||
} |
|||
println("The ${commatize(n)}$s Ulam number is ${commatize(ulam(n))}") |
|||
} |
|||
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 |
|||
The 100,000th Ulam number is 1,351,223 |
|||
Took 42.912s |
|||
</pre> |
</pre> |
||
Revision as of 19:34, 4 May 2022
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 nth Ulam number.
- References
11l
<lang 11l>F ulam(n)
I n <= 2 R n V mx = 1352000 V lst = [1, 2] [+] [0] * mx V sums = [0] * (mx * 2 + 1) sums[3] = 1 V size = 2 Int query L size < n query = lst[size - 1] + 1 L I sums[query] == 1 L(i) 0 .< size V sum = query + lst[i] V t = sums[sum] + 1 I t <= 2 sums[sum] = t (lst[size], size) = (query, size + 1) L.break query++ R query
L(p) 5
V n = 10 ^ p print(‘The #.#. Ulam number is #.’.format(n, I n != 1 {‘th’} E ‘st’, ulam(n)))</lang>
- Output:
The 1st Ulam number is 1 The 10th Ulam number is 18 The 100th Ulam number is 690 The 1000th Ulam number is 12294 The 10000th Ulam number is 132788
Action!
Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU. <lang Action!>PROC Main()
DEFINE MAX="1000" INT ARRAY ulam(MAX) INT uCount,n,count,x,y BYTE flag
ulam(0)=1 ulam(1)=2 uCount=2 PrintI(ulam(0)) Put(32) PrintI(ulam(1)) n=3 WHILE uCount<MAX DO flag=0 count=0 FOR x=0 TO uCount-2 DO FOR y=x+1 TO uCount-1 DO IF ulam(x)+ulam(y)=n THEN flag=1 count==+1 FI OD OD IF flag=1 AND count=1 THEN ulam(uCount)=n uCount==+1 Put(32) PrintI(n) FI n==+1 OD
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
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 ...
AWK
<lang AWK>
- 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)
} </lang>
- Output:
10 18 50 253 100 690 500 5685 1000 12294
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <time.h>
void fatal(const char* message) {
fprintf(stderr, "%s\n", message); exit(1);
}
void* xmalloc(size_t n) {
void* ptr = malloc(n); if (ptr == NULL) fatal("Out of memory"); return ptr;
}
void* xrealloc(void* p, size_t n) {
void* ptr = realloc(p, n); if (ptr == NULL) fatal("Out of memory"); return ptr;
}
int* extend(int* array, int min_length, int* capacity) {
int new_capacity = *capacity; if (new_capacity >= min_length) return array; while (new_capacity < min_length) new_capacity *= 2; array = xrealloc(array, new_capacity * sizeof(int)); memset(array + *capacity, 0, (new_capacity - *capacity) * sizeof(int)); *capacity = new_capacity; return array;
}
int ulam(int n) {
int* ulams = xmalloc((n < 2 ? 2 : n) * sizeof(int)); ulams[0] = 1; ulams[1] = 2; int sieve_length = 2; int sieve_capacity = 2; int* sieve = xmalloc(sieve_capacity * sizeof(int)); sieve[0] = sieve[1] = 1; for (int u = 2, ulen = 2; ulen < n; ) { sieve_length = u + ulams[ulen - 2]; sieve = extend(sieve, sieve_length, &sieve_capacity); for (int i = 0; i < ulen - 1; ++i) ++sieve[u + ulams[i] - 1]; for (int i = u; i < sieve_length; ++i) { if (sieve[i] == 1) { u = i + 1; ulams[ulen++] = u; break; } } } int result = ulams[n - 1]; free(ulams); free(sieve); return result;
}
int main() {
clock_t start = clock(); for (int n = 1; n <= 100000; n *= 10) printf("Ulam(%d) = %d\n", n, ulam(n)); clock_t finish = clock(); printf("Elapsed time: %.3f seconds\n", (finish - start + 0.0)/CLOCKS_PER_SEC); return 0;
}</lang>
- Output:
Ulam(1) = 1 Ulam(10) = 18 Ulam(100) = 690 Ulam(1000) = 12294 Ulam(10000) = 132788 Ulam(100000) = 1351223 Elapsed time: 8.630 seconds
C++
<lang cpp>#include <algorithm>
- include <chrono>
- include <iostream>
- include <vector>
int ulam(int n) {
std::vector<int> ulams{1, 2}; std::vector<int> sieve{1, 1}; for (int u = 2; ulams.size() < n; ) { sieve.resize(u + ulams[ulams.size() - 2], 0); for (int i = 0; i < ulams.size() - 1; ++i) ++sieve[u + ulams[i] - 1]; auto it = std::find(sieve.begin() + u, sieve.end(), 1); if (it == sieve.end()) return -1; u = (it - sieve.begin()) + 1; ulams.push_back(u); } return ulams[n - 1];
}
int main() {
auto start = std::chrono::high_resolution_clock::now(); for (int n = 1; n <= 100000; n *= 10) std::cout << "Ulam(" << n << ") = " << ulam(n) << '\n'; auto end = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> duration(end - start); std::cout << "Elapsed time: " << duration.count() << " seconds\n";
}</lang>
- Output:
Ulam(1) = 1 Ulam(10) = 18 Ulam(100) = 690 Ulam(1000) = 12294 Ulam(10000) = 132788 Ulam(100000) = 1351223 Elapsed time: 9.09242 seconds
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!
Although not shown here, the 100,000th Ulam number (1,351,223) is computed in about 13.5 seconds. <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
Version 3
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>
- 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
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>
Java
<lang java>public class UlamNumbers {
public static void main(String[] args) { long start = System.currentTimeMillis(); for (int n = 1; n <= 100000; n *= 10) { System.out.printf("Ulam(%d) = %d\n", n, ulam(n)); } long finish = System.currentTimeMillis(); System.out.printf("Elapsed time: %.3f seconds\n", (finish - start)/1000.0); }
private static int ulam(int n) { int[] ulams = new int[Math.max(n, 2)]; ulams[0] = 1; ulams[1] = 2; int sieveLength = 2; int[] sieve = new int[sieveLength]; sieve[0] = sieve[1] = 1; for (int u = 2, ulen = 2; ulen < n; ) { sieveLength = u + ulams[ulen - 2]; sieve = extend(sieve, sieveLength); for (int i = 0; i < ulen - 1; ++i) ++sieve[u + ulams[i] - 1]; for (int i = u; i < sieveLength; ++i) { if (sieve[i] == 1) { u = i + 1; ulams[ulen++] = u; break; } } } return ulams[n - 1]; }
private static int[] extend(int[] array, int minLength) { if (minLength <= array.length) return array; int newLength = 2 * array.length; while (newLength < minLength) newLength *= 2; int[] newArray = new int[newLength]; System.arraycopy(array, 0, newArray, 0, array.length); return newArray; }
}</lang>
- Output:
Ulam(1) = 1 Ulam(10) = 18 Ulam(100) = 690 Ulam(1000) = 12294 Ulam(10000) = 132788 Ulam(100000) = 1351223 Elapsed time: 9.098 seconds
jq
Adaptation of awk solution <lang jq># Input: the target number of Ulam numbers to generate
- Output: an array of Ulam numbers
def ulams:
. as $target | label $done | {ulam: [1, 2], nulams: 2} | foreach range(3; infinite) as $n (.; .count = 0 | .x = 0 | until( .x == .nulams or .count > 1; .y = .x+1
| until( .y >= .nulams or .count > 1;
if (.ulam[.x] + .ulam[.y] == $n) then .count += 1 else . end
| .y += 1) | .x += 1)
| if .count == 1 then .nulams += 1 | .ulam[.nulams-1] = $n else . end; select(.nulams >= $target) | .ulam, break $done);
def nth_ulam: ulams[.-1];</lang>
Illustration <lang jq>(5 | nth_ulam) | "5 => \(.)", "", ([5, 10, 100] as $in
| (100|ulams) as $u | $in[] | "\(.) => \($u[. - 1])" )
</lang>
- Output:
5 => 6 5 => 6 10 => 18 100 => 690
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)
Lua
Implemented from scratch, but algorithmically equivalent to other solutions where a running count of number-of-ways-to-reach-sum is maintained in order to sieve candidate values. <lang lua>function ulam(n)
local ulams, nways, i = { 1,2 }, { 0,0,1 }, 3 repeat if nways[i] == 1 then for j = 1, #ulams do local sum = i + ulams[j] nways[sum] = (nways[sum] or 0) + 1 end ulams[#ulams+1] = i end i = i + 1 until #ulams == n return ulams[#ulams]
end
for _,n in ipairs({10,100,1000,10000,100000}) do
local s, u, e = os.clock(), ulam(n), os.clock() print(string.format("%dth is %d (%f seconds elapsed)", n, u, e-s))
end</lang>
- Output:
Times are Lua 5.4 on i7-2600@3.4GHz
10th is 18 (0.000000 seconds elapsed) 100th is 690 (0.000000 seconds elapsed) 1000th is 12294 (0.020000 seconds elapsed) 10000th is 132788 (1.724000 seconds elapsed) 100000th is 1351223 (277.824000 seconds elapsed)
Nim
Phix algorithm
This is a translation of Wren second solution which uses Phix algorithm.
It has been compiled with option -d:release
which means that all runtime checks are done but debugging data is limited.
<lang Nim>import strformat, times
func ulam(n: Positive): int =
var ulams = @[1, 2] sieve = @[1, 1] u = 2 while ulams.len < n: let s = u + ulams[^2] sieve.setLen(s) for i in 0..<ulams.high: let v = u + ulams[i] - 1 inc sieve[v] for i in u..sieve.high: if sieve[i] == 1: u = i + 1 break ulams.add u result = ulams[^1]
let t0 = cpuTime() var n = 1 for _ in 0..4:
let suffix = if n == 1: "st" else: "th" echo &"The {n}{suffix} Ulam number is {ulam(n)}." n *= 10
echo &"\nTook {cpuTime() - t0:.3f} s."</lang>
- Output:
The program runs in about 150 ms on my laptop (i5-8250U with 8GB of RAM and running Linux Manjaro). It allows to get the 100_000th Ulam number in about 30 seconds.
The 1st Ulam number is 2. The 10th Ulam number is 18. The 100th Ulam number is 690. The 1000th Ulam number is 12294. The 10000th Ulam number is 132788. Took 0.148 s.
XPL0 algorithm
This is a translation of Wren third solution which uses XPL0 algorithm.
It has been compiled with the same option as the other version.
<lang Nim> import strformat, times
func ulam(n: Positive): int =
if n <= 2: return n const Max = 1352000 var list = newSeq[int](Max) list[0] = 1 list[1] = 2 var sums = newSeq[byte](2 * Max + 1) sums[3] = 1 var size = 2 var query: int while size < n: query = list[size-1] + 1 while true: if sums[query] == 1: for i in 0..<size: let sum = query + list[i] let t = sums[sum] + 1 if t <= 2: sums[sum] = t list[size] = query inc size break inc query result = query
let t0 = cpuTime() var n = 10 while n <= 100_000:
echo &"The {n}th Ulam number is {ulam(n)}." n *= 10
echo &"\nTook {cpuTime() - t0:.3f} s."</lang>
- Output:
In a first translation, we got the result in about 24 seconds which is the time obtained by the XPL0 version on a less powerful machine. We found that declaring "sums" as a sequence of bytes (8 bits) instead of a sequence of integers (64 bits) makes a big difference. We then got the result in 5 seconds. Note than there are also some ways to improve the other algorithm by using 32 bits integers rather than 64 bits integers, but it will still remain at least 50 % less efficient.
The 10th Ulam number is 18. 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. Took 4.986 s.
Pascal
like GO,PHIX who was first
<lang pascal>program UlamNumbers; {$IFDEF FPC}
{$MODE DELPHI} {$Optimization On,All}
{$ENDIF} uses
sysutils;
const
maxUlam = 100000; Limit = 1351223+4000;
type
tCheck = Uint16; tpCheck = pUint16;
var
Ulams : array of Uint32; Check0 : array of tCheck; Ulam_idx :NativeInt;
procedure init; begin
setlength(Ulams,maxUlam); Ulams[0] := 1; Ulams[1] := 2; Ulam_idx := 1; setlength(check0,Limit);
check0[1]:=1; check0[2]:=1;
end;
procedure OutData(idx,num:NativeInt); Begin
writeln(' Ulam(',idx+1,')',#9#9,num:10);
end;
function findNext(i:nativeInt;pCh0:tpCheck):NativeInt; begin
result := i; repeat if pCh0[result] = 1 then break; inc(result); until false;
end;
procedure SumOne(idx:NativeUint;pCh:tpCheck;pUlams:pUint32); //seperated speeds up a lot by reducing register pressure in main Begin
For idx := idx downto 0 do pCh[pUlams[idx]] +=1;
end;
var
pCh0,pCh : tpCheck; pUlams : pUint32; ul,idx,lmtidx :nativeInt;
Begin
Init; lmtidx := 9; pCh0:= @Check0[0]; pUlams := @Ulams[0]; OutData(0,pUlams[0]); ul := pUlams[Ulam_idx]; pCh:= @pCh0[ul]; repeat SumOne(Ulam_idx-1,pCh,pUlams); ul := findNext(ul+1,pCh0); inc(Ulam_idx); pUlams[Ulam_idx] := ul; pCh:= @pCh0[ul]; IF ul>Limit DIV 2 then break; if Ulam_idx=lmtIdx then Begin OutData(Ulam_idx,ul); lmtidx := lmtidx*10+9; end; until Ulam_idx >= maxUlam-1;
idx := Ulam_idx-1; //now reducing then the highest used summing idx while Ulam_idx< maxUlam-1 do begin while ul+pUlams[idx] > limit do dec(idx); SumOne(idx,pCh,pUlams); ul := findNext(ul+1,pCh0); inc(Ulam_idx); pUlams[Ulam_idx] := ul; pCh:= @pCh0[ul]; end; OutData(Ulam_idx,ul); setlength(check0,0); setlength(Ulams,0);
end.
</lang>
- Output:
Ulam(1) 1 Ulam(10) 18 Ulam(100) 690 Ulam(1000) 12294 Ulam(10000) 132788 Ulam(100000) 1351223 // real 0m4,731s AMD 2200G //TIO.RUN Free Pascal Compiler version 3.0.4 [2018/07/13] for x86_64 Copyright (c) 1993-2017 by Florian Klaempfl and others Target OS: Linux for x86-64 Compiling .code.tio.pp Linking .bin.tio /usr/bin/ld: warning: link.res contains output sections; did you forget -T? 92 lines compiled, 0.2 sec Real time: 3.025 s
Perl
<lang perl>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;</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 The 10000th Ulam number is: 132788
Phix
with javascript_semantics 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 timings all predate any {{trans|Phix}})
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
<lang python>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) </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 (Elapsed time: 11.470759391784668 seconds)
- Extra
In [1]: %time ulam(100_000) Wall time: 23min 58s Out[1]: 1351223 In [37]:
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 & displays the Nth Ulam number (or any number of specified values).*/ 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($) /*process each of the specified values.*/ x= Ulam( word($, k) ) /*invoke Ulam to find a Ulam number. */ 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 /*add Z to the sequence. */ !.z= 1 /*set the semaphore for Z. */ end z= z + 1 /*bump next possible 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
- output (courtesy of Paul Kislanko's PC) when using the input of: 100000
the 100,000th Ulam number is: 1,351,223
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
Rust
<lang rust>fn ulam(n: usize) -> usize {
let mut ulams = vec![1, 2]; let mut sieve = vec![1, 1]; let mut u = 2; while ulams.len() < n { sieve.resize(u + ulams[ulams.len() - 2], 0); for i in 0..ulams.len() - 1 { sieve[u + ulams[i] - 1] += 1; } for i in u..sieve.len() { if sieve[i] == 1 { u = i + 1; ulams.push(u); break; } } } ulams[n - 1]
}
fn main() {
use std::time::Instant; let start = Instant::now(); let mut n = 1; while n <= 100000 { println!("Ulam({}) = {}", n, ulam(n)); n *= 10; } println!("Elapsed time: {:.2?}", start.elapsed());
}</lang>
- Output:
Ulam(1) = 1 Ulam(10) = 18 Ulam(100) = 690 Ulam(1000) = 12294 Ulam(10000) = 132788 Ulam(100000) = 1351223 Elapsed time: 10.68s
Sidef
<lang ruby>func ulam(n) {
static u = Set(1,2) static ulams = [0, 1, 2]
return ulams[n] if (ulams.end >= n)
++n
for(var i = 3; true; ++i) { var count = 0
ulams.each {|v| if (u.has(i - v) && (v != i-v)) { break if (count++ > 2) } }
if (count == 2) { ulams << i u << i break if (ulams.len == n) } }
ulams.tail
}
for k in (1..3) {
say "The 10^#{k}-th Ulam number is: #{ulam(10**k)}"
}</lang>
- Output:
The 10^1-th Ulam number is: 18 The 10^2-th Ulam number is: 690 The 10^3-th Ulam number is: 12294
Vlang
Version 1
<lang vlang>import time fn ulam(n int) int {
mut ulams := [1, 2] mut set := {1: true, 2: true} mut i := 3 for { mut count := 0 for j := 0; j < ulams.len; j++ { ok := set[i-ulams[j]] if ok && ulams[j] != (i-ulams[j]) { count++ if count > 2 { break } } } if count == 2 { ulams << i set[i] = true if ulams.len == n { break } } i++ } return ulams[n-1]
}
fn main() {
start := time.now() for n := 10; n <= 10000; n *= 10 { println("The ${n}th Ulam number is ${ulam(n)}") } println("\nTook ${time.since(start)}")
}</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 Took 9.611s
Version 2
The following version, which builds up a sieve as it goes along, is (astonishingly) about 40 times faster! <lang go>import time fn ulam(n int) int {
mut ulams := [1, 2] mut sieve := [1, 1] mut u := 2 for ulams.len < n { s := u + ulams[ulams.len-2] t := s - sieve.len for i := 0; i < t; i++ { sieve << 0 } for i := 1; i <= ulams.len-1; i++ { v := u + ulams[i-1] - 1 sieve[v]++ } mut index := -1 for i, e in sieve[u..] { if e == 1 { index = u + i break } } u = index + 1 ulams << u } return ulams[n-1]
}
fn commatize(n int) string {
mut s := '$n' if n < 0 { s = s[1..] } le := s.len for i := le - 3; i >= 1; i -= 3 { s = '${s[0..i]},${s[i..]}' } if n >= 0 { return s } return "-$s"
}
fn main() {
start := time.now() for n := 1; n <= 10000; n *= 10 { mut s := "th" if n == 1 { s = "st" } println("The ${commatize(n)}$s Ulam number is ${commatize(ulam(n))}") } 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 415.000ms
Version 3
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 vlang>import time fn ulam(n int) int {
if n <= 2 { return n } max := 1_352_000 mut list := []int{len:max+1} list[0], list[1] = 1, 2 mut sums := []byte{len:2*max+1} sums[3] = 1 mut size := 2 mut query := 0 for { query = list[size-1] + 1 for { if sums[query] == 1 { for i in 0..size { 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
}
fn commatize(n int) string {
mut s := '$n' if n < 0 { s = s[1..] } le := s.len for i := le - 3; i >= 1; i -= 3 { s = '${s[0..i]},${s[i..]}' } if n >= 0 { return s } return "-$s"
}
fn main() {
start := time.now() for n := 1; n <= 100000; n *= 10 { mut s := "th" if n == 1 { s = "st" } println("The ${commatize(n)}$s Ulam number is ${commatize(ulam(n))}") } 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 The 100,000th Ulam number is 1,351,223 Took 42.912s
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.
Version 3
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. <lang ecmascript>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.")</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 The 100,000th Ulam number is 1,351,223 Took 409.990502 seconds.
XPL0
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.
<lang XPL0>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; ]</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 The 100000th Ulam number is 1351223