Fusc sequence: Difference between revisions
Frugal version
(add RPL) |
(Frugal version) |
||
Line 3,233:
≫ ''''TASK1'''' STO
≪ { (0,
1 4 ROLL '''FOR''' j
j R→B '''FUSC''' B→R
Line 3,278:
<pre>
2: { 0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 }
1: { (0,
</pre>
===Frugal version===
Based on Mike Stay's formula, this program does not need recursion or storage of n/2 previous terms, and is faster.
Since <code>fusc(2^n)=1</code> and <code>fusc(2^n+1)=n+1</code>, this formula can improve the calculation for big values of n, as the iteration can start at floor(log2(n)) instead of 1.
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
{ (0,0) } 0 0 1
2 6 ROLL '''FOR''' j
DUP2 + LAST MOD 2 * - ROT DROP
'''IF''' DUP XPON 4 PICK >
'''THEN''' ROT DROP DUP XPON ROT ROT
4 ROLL OVER j SWAP R→C + 4 ROLLD '''END'''
'''NEXT''' 3 DROPN
≫ ''''TASK2'''' STO
|
'''TASK2''' ''( n -- { (a,fusc(a)).. )''
initialize stack: result list, length, fusc(0) and fusc(1)
loop n-2 times
fusc(j) = jusc(j-2) + fusc(j-1) - 2*(fusc(j-2) mod fusc(j-1))
if new length record
update record in stack
add (j,fusc(j)) to list
clean stack
|}
{{in}}
<pre>
36000 TASK2
</pre>
{{out}}
<pre>
1: { (0,0) (11,37) (1173,108) (35499,1076) }
</pre>
| |||