Fusc sequence: Difference between revisions
Content added Content deleted
(add RPL) |
(Frugal version) |
||
Line 3,233: | Line 3,233: | ||
≫ ''''TASK1'''' STO |
≫ ''''TASK1'''' STO |
||
≪ { (0, |
≪ { (0,0) } 1 |
||
1 4 ROLL '''FOR''' j |
1 4 ROLL '''FOR''' j |
||
j R→B '''FUSC''' B→R |
j R→B '''FUSC''' B→R |
||
Line 3,278: | Line 3,278: | ||
<pre> |
<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 } |
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, |
1: { (0,0) (11,37) (108,1173) } |
||
</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> |
</pre> |
||