Rosetta Code

Ulam numbers: Difference between revisions

Page Discussion

Ulam numbers (view source)

Revision as of 14:21, 22 June 2024

50,219 bytes added ,  16 days ago
m
→‎{{header|EasyLang}}
(→‎{{header|FreeBASIC}}: - tweak to improve running time by ~50%)
 
(74 intermediate revisions by 26 users not shown)
Line 5:
<big><big> u<sub>2</sub> = 2 </big></big>
 
weWe define the &nbsp; <big> n<sup>th</sup> </big> &nbsp; Ulam number &nbsp; <big> u<sub>n</sub> </big> &nbsp; as the smallest number that is greater than &nbsp; <big> u<sub>n-1</sub> &nbsp; and uniquely written as a sum of two different Ulam numbers &nbsp; u<sub/big>i &nbsp;(<n)</sub> &nbsp; and &nbsp; u<sub>j&nbsp;(<n)</sub>.
<br>is the unique sum of two different Ulam numbers &nbsp; <big> u<sub>i&nbsp;(<n)</sub> </big> &nbsp; and &nbsp; <big> u<sub>j&nbsp;(<n)</sub></big>.
 
 
;Task:
Write a function to generate the &nbsp; <big> n-<sup>th</sup> </big> &nbsp; Ulam number.
 
 
Line 15 ⟶ 16:
* &nbsp; [[oeis:A002858|OEIS Ulam numbers]]
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight 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)))</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* Ulam numbers 25/01/2021
ULAMNUM CSECT
USING ULAMNUM,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R1,1 1
ST R1,ULAM ulam(1)=1
LA R1,2 2
ST R1,ULAM+4 ulam(2)=2
LA R9,2 k=2
LA R8,2 n=2
DO WHILE=(C,R9,LT,NN) do while k<nn
LA R8,1(R8) n=n+1
XR R10,R10 count=0
LR R0,R9 k
BCTR R0,0 -1
LA R6,1 i=1
DO WHILE=(CR,R6,LE,R0) do i=1 to k-1
LR R7,R6 i
LA R7,1(R7) j=i+1
DO WHILE=(CR,R7,LE,R9) do j=i+1 to k
LR R1,R6 i
SLA R1,2 ~
L R2,ULAM-4(R1) ulam(i)
LR R1,R7 j
SLA R1,2 ~
L R3,ULAM-4(R1) ulam(j)
AR R2,R3 ulam(i)+ulam(j)
IF CR,R2,EQ,R8 THEN if ulam(i)+ulam(j)=n then
LA R10,1(R10) count=count+1
ENDIF , endif
LA R7,1(R7) j++
ENDDO , enddo j
LA R6,1(R6) i++
ENDDO , enddo i
IF C,R10,EQ,=F'1' THEN if count=1 then
LA R9,1(R9) k=k+1
LR R1,R9 k
SLA R1,2 ~
ST R8,ULAM-4(R1) ulam(k)=n
LR R4,R9 k
SRDA R4,32 ~
D R4,=F'50' k/50
IF LTR,R4,Z,R4 THEN if mod(k,50)=0 then
XDECO R9,PG k
XDECO R8,PG+12 n
XPRNT PG,L'PG print buffer
ENDIF , endif
ENDIF , endif
ENDDO , enddo n
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
U EQU 500 u : max value
NN DC A(U) nn
ULAM DS (U)F ulam(u)
PG DC CL80' ' buffer
REGEQU
END ULAMNUM</syntaxhighlight>
{{out}}
<pre>
50 253
100 690
150 1257
200 1792
250 2484
300 3068
350 3632
400 4326
450 4996
500 5685
</pre>
 
=={{header|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.
<syntaxhighlight 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</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Ulam_numbers.png Screenshot from Atari 8-bit computer]
<pre>
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 ...
</pre>
 
 
 
=={{header|Ada}}==
{{trans|C}}
<syntaxhighlight lang="ada">pragma Ada_2022; -- enables Ada 2022 features
 
-- Ada has a lot of safety checks that are turned on by default.
-- It is possible to turn them off, especially when you know they aren't needed,
-- but this should be done only when you've done your homework.
-- Turning this one off makes the program nearly 30x slower on my machine;
-- you may want to see how it works differently on yours.
pragma Suppress (All_Checks);
-- pragma Suppress (Tampering_Check);
 
with Ada.Containers.Vectors;
 
with Ada.Real_Time;
use all type Ada.Real_Time.Time_Span; -- makes Time_Span's operators public
 
with Ada.Text_IO;
 
procedure Ulam_Numbers is
 
package IO renames Ada.Text_IO;
 
package IntVecs is new Ada.Containers.Vectors
(Index_Type => Positive, Element_Type => Natural);
subtype IntVec is IntVecs.Vector;
 
Something_Went_Wrong : exception;
 
function Ulam (Nth : Positive) return Positive is
Numbers, Sieve : IntVec;
Ith : Positive := 2;
begin
-- initialize
Numbers.Append (1);
Numbers.Append (2);
Sieve.Append (1);
Sieve.Append (1);
 
-- main loop
while Positive (Numbers.Length) < Nth loop
 
declare
Old_Length : constant Positive := Positive (Sieve.Length) + 1;
Extend_To : constant Positive :=
Ith + Numbers (Numbers.Last_Index);
begin
 
-- extend sieve
Sieve.Set_Length (Ada.Containers.Count_Type (Extend_To));
for Jth in Old_Length .. Extend_To loop
Sieve (Jth) := 0;
end loop;
 
for Number of Numbers loop
Sieve (Ith + Number) := Sieve (Ith + Number) + 1;
end loop;
Sieve (Ith + Numbers.Last_Element) :=
Sieve (Ith + Numbers.Last_Element) - 1;
 
Ith := Sieve.Find_Index (1, Ith + 1);
if Ith > Positive (Sieve.Length) then
raise Something_Went_Wrong with "Iteration" & Ith'Image;
end if;
Numbers.Append (Ith);
 
end;
 
end loop;
 
return Numbers.Last_Element;
 
end Ulam;
 
Start, Stop : Ada.Real_Time.Time;
Total_Time : Ada.Real_Time.Time_Span := Ada.Real_Time.Time_Span_Zero;
 
Entries_To_Compute : constant array (Positive range <>) of Integer :=
[10, 100, 1_000, 10_000, 100_000];
 
begin
 
Start := Ada.Real_Time.Clock;
 
for Ith of Entries_To_Compute loop
IO.Put_Line ("The" & Ith'Image & "th Ulam number is" & Ulam (Ith)'Image);
end loop;
 
Stop := Ada.Real_Time.Clock;
Total_Time := (@ + Stop) - Start;
IO.Put_Line ("Elapsed time: " & Total_Time'Image);
 
end Ulam_Numbers;
</syntaxhighlight>
{{out}}
<pre>
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
Elapsed time: 20.473358675
</pre>
 
=={{header|ALGOL 68}}==
Basically, the same algotithm as XPL0.
<syntaxhighlight lang="algol68">
BEGIN # find some Ulam numbers, U(n) = the smallest number > U(n-1) that is #
# the uniue sum of U(i) and U(j), i, j < n, i =/= j, U(1)=1, U(2) = 2 #
INT max ulam = 10 000; # maximum ulam number to find #
[ 1 : max ulam ]INT u; # ulam numbers found #
FOR i TO UPB u DO u[ i ] := 0 OD;
INT ulam size = 20 000; # initial size of the ulam number buffer #
CHAR unused = "0", one = "1", multiple = "2"; # states of ulam numbers #
FLEX[ 1 : ulam size ]CHAR ulam;FOR i TO UPB ulam DO ulam[ i ] := unused OD;
ulam[ 3 ] := ulam[ 2 ] := ulam[ 1 ] := one; u[ 1 ] := 1; u[ 2 ] := 2;
print( ( " 1 2" ) );
INT u count := 2; # numer of ulam numbers found #
INT power of ten := 100; # next "power of ten" ulam number to show #
FOR i FROM 3 WHILE u count < max ulam DO
IF ulam[ i ] = one THEN
# can use this number #
u[ u count +:= 1 ] := i;
IF u count < 21 THEN
print( ( " ", whole( i, 0 ) ) );
IF u count = 20 THEN print( ( "..." ) ) FI
ELIF u count = power of ten THEN
print( ( newline, "The ", whole( power of ten, -6 ), "th Ulam number is: ", whole( i, 0 ) ) );
power of ten *:= 10
FI;
FOR p TO u count - 1 DO
INT pi = u[ p ] + i;
IF pi > UPB ulam THEN
# need a bigger ulam buffer #
[ 1 : UPB ulam + ulam size ]CHAR new ulam;
new ulam[ 1 : UPB ulam ] := ulam;
FOR u FROM UPB ulam + 1 TO UPB new ulam DO new ulam[ u ] := unused OD;
ulam := new ulam
FI;
CHAR upi = ulam[ pi ];
IF upi = unused
THEN ulam[ pi ] := one # u[ p ] + i is unique so far #
ELIF upi = one
THEN ulam[ pi ] := multiple # u[ p ] + i isn't unique #
FI
OD
FI
OD
END
</syntaxhighlight>
{{out}}
<pre>
1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69...
The 100th Ulam number is: 690
The 1000th Ulam number is: 12294
The 10000th Ulam number is: 132788
</pre>
 
=={{header|AWK}}==
<syntaxhighlight 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)
}
</syntaxhighlight>
{{out}}
<pre>
10 18
50 253
100 690
500 5685
1000 12294
</pre>
 
=={{header|C}}==
{{trans|Phix}}
<syntaxhighlight 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;
}</syntaxhighlight>
 
{{out}}
<pre>
Ulam(1) = 1
Ulam(10) = 18
Ulam(100) = 690
Ulam(1000) = 12294
Ulam(10000) = 132788
Ulam(100000) = 1351223
Elapsed time: 8.630 seconds
</pre>
 
=={{header|C++}}==
{{trans|Phix}}
<syntaxhighlight 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";
}</syntaxhighlight>
 
{{out}}
<pre>
Ulam(1) = 1
Ulam(10) = 18
Ulam(100) = 690
Ulam(1000) = 12294
Ulam(10000) = 132788
Ulam(100000) = 1351223
Elapsed time: 9.09242 seconds
</pre>
 
=={{header|Delphi}}==
{{trans|Phix}}
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
 
 
 
function GetUlamNumber(N: integer): integer;
var Ulams: array of integer;
var U,ULen,I: integer;
var Sieve: array of integer;
begin
SetLength(Ulams,Max(N,2));
Ulams[0]:= 1;
Ulams[1]:= 2;
SetLength(Sieve, 2);
Sieve[0]:=1;
Sieve[1]:= 1;
U:=2; ULen:=2;
while Ulen < N do
begin
SetLength(Sieve,U + Ulams[Ulen - 2]);
for I:= 0 to ulen - 2 do
Sieve[u + Ulams[I] - 1]:=Sieve[u + Ulams[i] - 1]+1;
for I:=U to High(Sieve) do
if Sieve[I] = 1 then
begin
U:=I + 1;
Ulams[Ulen]:=U;
Inc(ULen);
break;
end;
end;
Result:=ULams[N - 1];
end;
 
 
 
procedure ShowUlamNumbers(Memo: TMemo);
var N: integer;
var S: string;
begin
N:=1;
while N<=100000 do
begin
S:=Format('Ulam(%d)',[N]);
Memo.Lines.Add(Format('%-12S = %8d', [S, GetUlamNumber(N)]));
N:=N * 10
end;
end;
 
 
</syntaxhighlight>
{{out}}
<pre>
Ulam(1) = 1
Ulam(10) = 18
Ulam(100) = 690
Ulam(1000) = 12294
Ulam(10000) = 132788
Ulam(100000) = 1351223
 
Elapsed Time: 17.685 Sec.
 
</pre>
 
 
=={{header|EasyLang}}==
{{trans|Ring}}
<syntaxhighlight>
func getulam n .
ulam[] = [ 1 2 ]
i = 3
repeat
cnt = 0
for x = 1 to len ulam[] - 1
ux = ulam[x]
for y = x + 1 to len ulam[]
if ux + ulam[y] >= i
if ux + ulam[y] > i
break 1
.
cnt += 1
if cnt > 1
break 2
.
.
.
.
if cnt = 1
ulam[] &= i
.
until len ulam[] = n
i += 1
.
return i
.
print getulam 100
</syntaxhighlight>
{{out}}
<pre>
690
</pre>
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">redim as uinteger ulam(1 to 2)
ulam(1) = 1 : ulam(2) = 2
 
Line 50 ⟶ 632:
for i as uinteger = 1 to 4
print 10^i, get_ulam(10^i, ulam())
next i</pre>
</syntaxhighlight>
 
{{out}}
<pre> 10 18
100 690
1000 12294
10000 132788</pre>
 
=={{header|Go}}==
===Version 1===
{{trans|Wren}}
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 89 ⟶ 679:
fmt.Println("The", n, "\bth Ulam number is", ulam(n))
}
}</langsyntaxhighlight>
 
{{out}}
Line 97 ⟶ 687:
The 1000th Ulam number is 12294
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!
 
Although not shown here, the 100,000th Ulam number (1,351,223) is computed in about 13.5 seconds.
<syntaxhighlight 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))
}</syntaxhighlight>
 
{{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>
 
===Version 3===
{{trans|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.
<syntaxhighlight 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))
}</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
Line 102 ⟶ 850:
 
===Lazy List===
<langsyntaxhighlight lang="haskell">
import Data.List
 
Line 131 ⟶ 879:
isSingleton as
| length as == 1 = True
| otherwise = False</langsyntaxhighlight>
 
=={{header|PhixJ}}==
 
<lang Phix>function ulam(integer n)
Implementation:
sequence ulams = {1, 2},
 
sieve = {1, 1}
<syntaxhighlight lang=J>require'stats'
integer u := 2
nextulam=: , {{<./(#~ ({:y)<])(~. #~ 1 = #/.~) +/"1 y{~2 comb #y}}
while true do
ulam=: <: { (nextulam^:(<:@(>./)`(1 2"_)))</syntaxhighlight>
integer s = u+ulams[$-1]
 
sieve &= repeat(0,s-length(sieve))
This could be optimized, for example: caching could help.
for i=1 to length(ulams)-1 do
 
sieve[u+ulams[i]] += 1
Examples:
end for
 
u = find(1,sieve,u+1)
<syntaxhighlight lang=J> ulam 1
ulams &= u
1
if length(ulams)=n then exit end if
ulam end while10
18
ulam 100
690
ulam 1000
12294
ulam 10000
132788
ulam 20 30 40 50 60
69 126 189 253 341</syntaxhighlight>
 
=={{header|Java}}==
{{trans|Phix}}
<syntaxhighlight 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;
}
}</syntaxhighlight>
 
{{out}}
<pre>
Ulam(1) = 1
Ulam(10) = 18
Ulam(100) = 690
Ulam(1000) = 12294
Ulam(10000) = 132788
Ulam(100000) = 1351223
Elapsed time: 9.098 seconds
</pre>
 
=={{header|jq}}==
'''Adaptation of [[#awk|awk]] solution'''
<syntaxhighlight 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];</syntaxhighlight>
 
'''Illustration'''
<syntaxhighlight lang="jq">(5 | nth_ulam) | "5 => \(.)",
"",
([5, 10, 100] as $in
| (100|ulams) as $u
| $in[]
| "\(.) => \($u[. - 1])" )
</syntaxhighlight>
{{out}}
<pre>
5 => 6
 
5 => 6
10 => 18
100 => 690
</pre>
 
=={{header|Julia}}==
{{trans|Wren}}
<syntaxhighlight 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 function
 
nthUlam(5)
for p=1 to 4 do
 
integer n = power(10,p)
for n in [10, 100, 1000, 10000]
printf(1,"The %,d%s Ulam number is %,d\n",{n,ord(n),ulam(n)})
@time println("The ", n, "th Ulam number is: ", nthUlam(n))
end for</lang>
end
</syntaxhighlight>{{out}}
<pre>
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)
</pre>
 
=={{header|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.
<syntaxhighlight 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</syntaxhighlight>
{{out}}
Times are Lua 5.4 on i7-2600@3.4GHz
<pre>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)</pre>
 
=={{header|Nim}}==
===Phix algorithm===
{{trans|Wren}}
This is a translation of Wren second solution which uses Phix algorithm.
 
It has been compiled with option <code>-d:release</code> which means that all runtime checks are done but debugging data is limited.
<syntaxhighlight 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."</syntaxhighlight>
 
{{out}}
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.
<pre>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.</pre>
 
===XPL0 algorithm===
{{trans|Wren}}
This is a translation of Wren third solution which uses XPL0 algorithm.
 
It has been compiled with the same option as the other version.
 
<syntaxhighlight 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."</syntaxhighlight>
 
{{out}}
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.
<pre>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.</pre>
 
=={{header|Pascal}}==
{{works with|Free Pascal}} like GO,PHIX who was first
<syntaxhighlight 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.
</syntaxhighlight>{{out}}
<pre> 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</pre>
=={{header|Perl}}==
{{trans|Julia}}
<syntaxhighlight 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;</syntaxhighlight>
{{out}}
<pre>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</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">ulam</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ulams</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">sieve</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">u</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ulams</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ulams</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">t</span>
<span style="color: #000000;">sieve</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sieve</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ulams</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ulams</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">t</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sieve</span><span style="color: #0000FF;">,</span><span style="color: #000000;">u</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">ulams</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">u</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">ulams</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The %,d%s Ulam number is %,d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">ulam</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{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
"1.0s"
</pre>
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
<small>(The above timings all predate any <nowiki>{{trans|Phix}}</nowiki>)</small><br>
 
The above algorithm can also yield "The 100,000th Ulam number is 1,351,223" in 1 minute and 40s, for me.
<small>(I fully expect translations of this better algorithm to run even faster, btw)</small>
 
=={{header|Python}}==
{{trans|XPL0}}
<syntaxhighlight 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)
</syntaxhighlight>
 
{{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
 
(Elapsed time: 11.470759391784668 seconds)</pre>
 
;Extra:
<pre>In [1]: %time ulam(100_000)
Wall time: 23min 58s
Out[1]: 1351223
 
In [37]:
</pre>
 
=={{header|Raku}}==
 
<syntaxhighlight lang="raku" perl6line>my @ulams = 1, 2, &next-ulam … *;
 
sub next-ulam {
Line 178 ⟶ 1,445:
for 1 .. 4 {
say "The {10**$_}th Ulam number is: ", @ulams[10**$_ - 1]
}</langsyntaxhighlight>
{{out}}
<pre>The 10th Ulam number is: 18
Line 186 ⟶ 1,453:
 
=={{header|REXX}}==
{{trans|Wren}}
<lang rexx>/*REXX program finds and displays the Nth Ulam number (or a series of various numbers).*/
 
parse arg highs /*obtain optional argument from the CL.*/
This REXX version has several speed improvements.
if highs='' | highs="," then highs= 10 100 1000 /*Not specified? Then use the defaults.*/
<syntaxhighlight lang="rexx">/*REXX program finds & displays the Nth Ulam number (or any number of specified values).*/
do i=1 for words(highs)
parse arg $ z= Ulam( word(highs, i) ) /*define the first two Ulam numbers. /*obtain optional argument from the CL.*/
if $='' | $="," then $= 10 100 1000 10000 /*Not specified? Then use the defaults.*/
say 'the ' commas(#)th(#) ' Ulam number is: ' commas(@.#)
 
end /*i*/
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 /*define1st thetwo firstterms; two Ulam#: numbers. sequence length. */
#= 2 !.= 0; !.1= 1; !.2= 1 /*thesemaphore numberfor ofeach Ulamterm numbersin sequence. (so far).*/
z= 3 do j=3; !.= /*searchvalue forof numbersnext possible term in this rangeseq. */
do until #==n
mx= 0 /*define the maximum sum (so far). */
do acnt=1 for # /* [↑] compute all possible Ulam sums.*/0
do bj=a+1 to for #; _= z - @.j /*compute a_: sum from twoshort Ulamcircuit numbersvalue. */
if s= @!.a_ + then if @.bj\==_ then do; cnt= cnt + /*compute a sum from two Ulam numbers. */1
if s<@.# then iterate /*Is the sum is too small? Then skip. */ if cnt>2 then leave
!.s= !.s s /*append a sum to a list of sums for S.*/ end
mx= max(mx, s) end /*obtain the maximum sum, a later limitj*/
end /*b*/
end /*a*/
 
do fif cnt=@.#+1=2 tothen mxdo; #= # + 1 /* [↓] find if/*bump the sumnumber isof uniqueterms. */
if ! @.f=#='' z then iterate /*Isadd the numberZ defined? to No,the sequence. then skip*/
if words(!.f)>1 then iterate /*Is the sum unique? " "!.z= 1 " /*set the semaphore for Z. */
#= # + 1 /*bump the count of Ulam numbers found.*/end
@.# z= strip(!.f)z + 1 /*elidebump anynext superfluouspossible blanksterm. in list.*/
if #==n then leave j end /*Found the Nth number? Then we're doneuntil*/
return @.#</syntaxhighlight>
leave /*now, go and find the next Ulam number*/
{{out|output|text=&nbsp; when using the default input of: &nbsp; &nbsp; <tt> 10 &nbsp; 100 &nbsp; 1000 &nbsp; 10000 </tt>}}
end /*f*/
<pre>
end /*j*/; return @.# /*return the Nth Ulam number to caller.*/</lang>
the 10th Ulam number is: 18
{{out|output|text=&nbsp; when using the default inputs:}}
the 100th Ulam number is: 690
the 1,000th Ulam number is: 12,294
the 10,000th Ulam number is: 132,788
</pre>
{{out|output|text=&nbsp; (courtesy of Paul Kislanko's PC) &nbsp; when using the input of: &nbsp; &nbsp; <tt> 100000 </tt>}}
<pre>
the 10th 100,000th Ulam number is: 181,351,223
the 100th Ulam number is: 690
the 1,000th Ulam number is: 12,294
</pre>
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
load "stdlib.ring"
 
Line 265 ⟶ 1,537:
ok
next
</syntaxhighlight>
</lang>
Output:
<pre>
Line 272 ⟶ 1,544:
The 1000th Ulam number is: 12294
The 10000th Ulam number is: 132788
</pre>
 
=={{header|Rust}}==
{{trans|Phix}}
<syntaxhighlight 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());
}</syntaxhighlight>
 
{{out}}
<pre>
Ulam(1) = 1
Ulam(10) = 18
Ulam(100) = 690
Ulam(1000) = 12294
Ulam(10000) = 132788
Ulam(100000) = 1351223
Elapsed time: 10.68s
</pre>
 
=={{header|Sidef}}==
{{trans|Perl}}
<syntaxhighlight 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)}"
}</syntaxhighlight>
{{out}}
<pre>
The 10^1-th Ulam number is: 18
The 10^2-th Ulam number is: 690
The 10^3-th Ulam number is: 12294
</pre>
 
=={{header|V (Vlang)}}==
===Version 1===
{{trans|Go}}
<syntaxhighlight lang="v (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)}")
}</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
===Version 2===
{{trans|Go}}
The following version, which builds up a sieve as it goes along, is (astonishingly) about 40 times faster!
<syntaxhighlight 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)}")
}</syntaxhighlight>
 
{{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 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.
<syntaxhighlight lang="v (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)}")
}</syntaxhighlight>
 
{{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>
 
=={{header|Wren}}==
===Version 1===
{{libheader|Wren-set}}
<langsyntaxhighlight ecmascriptlang="wren">import "./set" for Set
 
var ulam = Fn.new() { |n|
Line 305 ⟶ 1,860:
System.print("The %(n)th Ulam number is %(ulam.call(n))")
if (n == 10000) break
}</langsyntaxhighlight>
 
{{out}}
<pre>
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788
</pre>
 
===Version 2===
{{trans|Phix}}
{{libheader|Wren-seq}}
{{libheader|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.
<syntaxhighlight lang="wren">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.")</syntaxhighlight>
 
{{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 6.366709 seconds.
</pre>
 
===Version 3===
{{trans|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.
<syntaxhighlight lang="wren">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.")</syntaxhighlight>
 
{{out}}
<pre>
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.
</pre>
 
=={{header|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.
 
<syntaxhighlight 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;
]</syntaxhighlight>
 
{{out}}
Line 313 ⟶ 2,018:
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788
The 100000th Ulam number is 1351223
</pre>
Chkas
2,083

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/304379...365652"