Hofstadter Q sequence: Difference between revisions
Content added Content deleted
Not a robot (talk | contribs) (Add BCPL) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
| Line 2,494: | Line 2,494: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Just to be flash, I also calculated the 100 millionth term - the only limiting factor here |
Just to be flash, I also (on the desktop only) calculated the 100 millionth term - the only limiting factor here is the length of Q |
||
( |
(theoretically 402,653,177 on 32 bit). |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">Q</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> |
|||
function q(integer n) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
integer l = length(Q) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">)</span> |
|||
while n>l do |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
l += 1 |
|||
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
Q &= Q[l-Q[l-1]]+Q[l-Q[l-2]] |
|||
<span style="color: #000000;">Q</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]]+</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]]</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
return Q[n] |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
{} = q(10) -- (or collect one by one) |
|||
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (or collect one by one)</span> |
|||
printf(1,"First ten terms: %s\n",{sprint(Q[1..10])}) |
|||
<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;">"First ten terms: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">10</span><span style="color: #0000FF;">])})</span> |
|||
printf(1,"1000th: %d\n",q(1000)) |
|||
<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;">"1000th: %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">))</span> |
|||
printf(1,"100,000th: %d\n",q(100_000)) |
|||
<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;">"100,000th: %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100_000</span><span style="color: #0000FF;">))</span> |
|||
integer n = 0 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
for i=2 to 100_000 do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">100_000</span> <span style="color: #008080;">do</span> |
|||
n += Q[i]<Q[i-1] |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">Q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"Flips up to 100,000: %d\n",{n}) |
|||
<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;">"Flips up to 100,000: %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">})</span> |
|||
atom t0 = time() |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span> |
|||
printf(1,"100,000,000th: %d (%3.2fs)\n",{q(100_000_000),time()-t0})</lang> |
|||
<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: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"100,000,000th: %d (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100_000_000</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> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||