The Museum of HP Calculators

Farey Sequences for the HP-41

This program is Copyright © 2005 by Jean-Marc Baillard and is used here by permission.

This program is supplied without representation or warranty of any kind. Jean-Marc Baillard and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

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: /
 

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  " "                      ( one space )
32  ARCL X
33  "~/"                    ( append / )
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	/	bk	/
X	n	ak	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.
 

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

Go back to the HP-41 software library
Go back to the general software library
Go back to the main exhibit hall