hp41programs

Farey Farey Sequences for the HP-41

Overview

-The Farey sequence F_n is the list of N rational number { a₁/b₁ = 0/1 ; a₂/b₂ = 1/n ; ....... ; a_N/b_N = 1/1 } sorted in increasing order
whith 0 <= a_k <= b_k <= n ; GCD(a_k;b_k) = 1

-The following program uses the formulae: a_k+1 = a_k.m_k - a_k-1 ; b_k+1 = b_k.m_k - b_k-1 where m_k = INT( (b_k-1+ n)/b_k )

F₁ = { 0/1 ; 1/1 }
F₂ = { 0/1 ; 1/2 ; 1/1 }
F₃ = { 0/1 ; 1/3 ; 1/2 ; 2/3 ; 1/1 }
F₄ = { 0/1 ; 1/4 ; 1/3 ; 1/2 ; 2/3 ; 3/4 ; 1/1 }
.............................. etc .............................

Program Listing

Data Registers: R00 = n ; R01 = a_k-1 ; R02 = b_k-1 ; R03 = k ; When the routine stops, R03 = X-register = N = the number of elements in the list.
Flag: F29
Subroutines: /

-Line 33 is append /

01 LBL "FAREY"
02 STO 00
03 STO 02
04 0
05 STO 03
06 SIGN
07 CHS
08 STO 01
09 ST+ 02

10 LBL 01
11 ISG 03
12 CLX
13 RCL 00
14 RCL 02
15 +
16 R^
17 /
18 INT

19 ENTER^
20 R^
21 ST* Y
22 X<> 02
23 -
24 X<>Y
25 R^
26 ST* Y
27 X<> 01

28 -
29 FIX 0
30 CF 29
31 " "
32 ARCL X
33 "~/"
34 ARCL Y
35 FIX 4
36 SF 29

37 AVIEW
38 X#Y?
39 GTO 01
40 RCL 03
41 CLA
42 END

( 68 bytes / SIZE 004 )

STACK	INPUTS	... AVIEW ...	OUTPUTS
Y	/	b_k	/
X	n	a_k	N(n)

where N(n) = the number of fractions

Example:

5 XEQ "FAREY" >>>> 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

and X-register = 11 = the number of terms in this Farey sequence = R03.

References:

[1] John H. Conway & Richard K. Guy - "The Book of Numbers" - Springer Verlag - ISBN 0-387-97993-X
[2] Robert Pulluard - "La HP-48 en Liberté" - D3i Diffusion - ISBN 2-908791-16-1 ( in French )