Ulam numbers: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(→{{header|ALGOL 68}}: Improve the algorithm to be more like the XPL0 sample) |
m (→{{header|Wren}}: Minor tidy) |
||
| (6 intermediate revisions by 5 users not shown) | |||
Line 54:
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>
Line 93 ⟶ 170:
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # find some Ulam numbers, U(n) = the smallest number > U(n-1) that is #
Line 119 ⟶ 196:
FI;
FOR p TO u count - 1 DO
INT
IF pi > UPB ulam THEN
# need a bigger ulam buffer #
Line 127 ⟶ 204:
ulam := new ulam
FI;
CHAR upi
IF upi = unused
THEN ulam[ pi ] := one # u[ p
ELIF upi = one
THEN ulam[ pi ] := multiple # u[ p
FI
OD
Line 307 ⟶ 384:
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|FreeBASIC}}==
Line 590 ⟶ 737:
| length as == 1 = True
| otherwise = False</syntaxhighlight>
=={{header|J}}==
Implementation:
<syntaxhighlight lang=J>require'stats'
nextulam=: , {{<./(#~ ({:y)<])(~. #~ 1 = #/.~) +/"1 y{~2 comb #y}}
ulam=: <: { (nextulam^:(<:@(>./)`(1 2"_)))</syntaxhighlight>
This could be optimized, for example: caching could help.
Examples:
<syntaxhighlight lang=J> ulam 1
1
ulam 10
18
ulam 100
690
ulam 1000
12294
ulam 10000
132788
ulam 20 30 40 50 60
69 126 189 253 341</syntaxhighlight>
=={{header|Java}}==
Line 1,315 ⟶ 1,487:
</pre>
=={{header|V (Vlang)}}==
===Version 1===
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">import time
fn ulam(n int) int {
mut ulams := [1, 2]
Line 1,438 ⟶ 1,610:
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 {
Line 1,516 ⟶ 1,688:
===Version 1===
{{libheader|Wren-set}}
<syntaxhighlight lang="
var ulam = Fn.new() { |n|
Line 1,560 ⟶ 1,732:
{{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="
import "./fmt" for Fmt
var ulam = Fn.new { |n|
Line 1,603 ⟶ 1,775:
The only downside with this version is that you need to know how much memory to allocate in advance.
<syntaxhighlight lang="
var ulam = Fn.new { |n|
| |||