Rosetta Code

Ulam numbers: Difference between revisions

Page Discussion

Ulam numbers (view source)

Revision as of 16:59, 29 July 2021

6,344 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (used a bigger font size to display the supercript so that it can be read easier.)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 884:
 
=={{header|Phix}}==
<!--<lang Phix>function ulam(integer nphixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
sequence ulams = {1, 2},
<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>
sieve = {1, 1}
<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>
integer u := 2
<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>
while length(ulams)<n do
<span style="color: #004080;">integer</span> <span style="color: #000000;">u</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">2</span>
integer s = u+ulams[$-1], t
<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>
sieve &= repeat(0,s-length(sieve))
<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>
for i=1 to length(ulams)-1 do
<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>
s = u+ulams[i]
<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>
t = sieve[s]+1
<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>
if t<=2 then
<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>
sieve[s] = t
<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>
end if
<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>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
u = find(1,sieve,u+1)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
ulams &= u
<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>
end while
<span style="color: #000000;">ulams</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">u</span>
return ulams[n]
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end function
<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>
atom t0 = time()
for p=0 to 4 do
<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>
integer n = power(10,p)
<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>
printf(1,"The %,d%s Ulam number is %,d\n",{n,ord(n),ulam(n)})
<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>
end for
<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>
?elapsed(time()-t0)</lang>
<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>
<!--</lang>-->
{{out}}
<pre>
Line 924 ⟶ 927:
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<br>
<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}}==
Petelomax
7,815

edits

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