Stern-Brocot sequence: Difference between revisions

=={{header|RPL}}==

Task 1 is done by applying the algorithm explained above.

Other requirements are based on Mike Stay's formula for OEIS AA002487:

a(n) = a(n-2) + a(n-1) - 2*(a(n-2) mod a(n-1))

which avoids keeping a huge subset of the sequence in memory

{{works with|Halcyon Calc|4.2.7}}

{| class="wikitable"

! RPL code

! Comment

|-

|

≪

{ 1 1 } 1

'''WHILE''' OVER SIZE 4 PICK < '''REPEAT'''

GETI ROT ROT DUP2 GET 4 ROLL +

ROT SWAP + SWAP

DUP2 GET ROT SWAP + SWAP

'''END''' ROT DROP2

≫ ‘'''TASK1'''’ STO

≪

0 1

2 4 ROLL '''START'''

DUP2 + LAST MOD 2 * - ROT DROP '''NEXT'''

SWAP DROP

≫ ‘'''STERN'''’ STO

≪ 1

'''WHILE''' DUP '''STERN''' 3 PICK ≠ '''REPEAT''' 1 + '''END''' R→C

≫ ‘'''WHEN'''’ STO

|

'''TASK1''' ''( n -- {SB(1)..SB(n) )''

initialize stack with SB(1), SB(2) and pointer i

loop until SB(n) reached

get SB(i)+SB(i+1)

add to list

add SB(i+1) to list

clean stack

'''STERN''' ''( n -- SB(n) )''

initialize stack with SB(0), SB(1)

loop n-2 times

SB(i)=SB(i-1)+SB(i-2)-2*(SB(i-2) mod SB(i-1))

clean stack

'''WHEN''' ''( m -- (n,SB(n)) )'' with SB(n) = m

loop until found

|}

{{in}}

<pre>

15 TASK1

{ } 1 10 FOR n n WHEN + NEXT

100 WHEN

</pre>

{{out}}

<pre>

3: { 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 }

2: { (1,1) (2,3) (3,5) (4,9) (5,11) (6,33) (7,19) (8,21) (9,35) (10,39) }

1: (100,1179)

</pre>

===Faster version for big values of n===

We use here the fact that

SB(2^k) = 1 and SB(2^k + 1) = k+1 for any k>0

which can be easily demonstrated by using the definition of the fusc sequence, identical to the Stern-Brocot sequence (OEIS AA002487).

{| class="wikitable"

! RPL code

! Comment

|-

|

≪

'''IF''' DUP 4 < '''THEN''' 0 1

'''ELSE'''

DUP LN 2 LN / IP 2 OVER ^

ROT SWAP - 1 ROT 1 +

'''END'''

≫ ‘'''Offset'''’ STO

≪

'''Offset'''

2 4 ROLL '''START'''

DUP2 + LAST MOD 2 * - ROT DROP '''NEXT'''

SWAP DROP

≫ ‘'''STERN'''’ STO

|

'''Offset''' ''( n -- 1 k+1 offset )''

start at the beginning for small n values

otherwise

get k with 2^k ≤ n

initialize stack to 1, k+1, n-2^k

'''STERN''' ''( n -- SB(n) )''

initialize stack

loop n-2 times

SB(i)=SB(i-1)+SB(i-2)-2*(SB(i-2) mod SB(i-1))

clean stack

|}

2147484950 '''STERN'''

1: 1385