Rosetta Code

Ulam numbers: Difference between revisions

Page Discussion

Ulam numbers (view source)

Revision as of 20:07, 4 December 2020

126 bytes added ,  3 years ago
Added really fast XPL0 example.
(→‎Version 2: Added a note about 100,000th Ulam number.)
(Added really fast XPL0 example.)
Line 497:
 
=={{header|XPL0}}==
Seeing "set" in the Go version and "sieve" in Phix, etc. lit a little
This version is three times faster than before. It takes 20 minutes on a Pi4.
light bulb. This version exploits those ideas and finds the 100,000th
<lang XPL0>func Ulam(N); \Return Nth Ulam number▼
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, Size, L, H, Query, Sum, Cnt;▼
int List(Max); \array of Ulam ];numbers▼
[if N < 3 then return N;▼
char Sums(Max*2); \array: 0, 1, or more ways to sum Ulams
List:= Reserve(0);
▲int ListI, Size, L, H, Query, Sum, CntT;
▲[if N <= 32 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;
repeat QuerySize:= List(Size-1)2; + 1; \possiblestart after first next2 memberUlams
repeat Query:= List(Size-1)+1; \possible next Ulam no.
loop [Cnt:= 0;▼
loop [if Sums(Query) = 1 forthen H:= Size-1 downto \sums 1 doway so it's next
[for LI:= 0 to HSize-1 do \update Sums array with
[Sum:= List(L)Query + List(HI); \ all combos of sums
ifT:= Sums(Sum)+1; > Query then L:= Size \exit Lbut limit formax loopcount
else if SumT <= Query2 then Sums(Sum):= T;
[Cnt:= Cnt+1;▼
if Cnt >= 2 then \exit both for loops
[L:= Size; H:= 1];
▲ ];
▲ ];
if Sum < Query then H:= 1; \exit H for loop
];▼
if Cnt = 1 then \sum was unique
[List(Size):= Query;
Size:= Size+1;
quit; \quit loop
];
QueryList(Size):= Query+1; \possibleadd Query nextto memberList
▲ [CntSize:= CntSize+1;
▲ ]quit;
];
Query:= Query+1; \possible next Ulam no.
▲ loop [Cnt:= 0];
until Size >= N;
return Query;
Line 536 ⟶ 535:
IntOut(0, Ulam(N)); CrLf(0);
N:= N*10;
until N > 10000100_000;
]</lang>
 
Line 545 ⟶ 544:
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788
The 100000th Ulam number is 1351223
</pre>
Loren
772

edits

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