Farey Sequence



#2

Farey Sequence

I was given this book: "An Introduction to the Theory of Numbers" by Hardy & Wright and there's this chapter about Farey Series I've never heard before. Of course I wanted to calculate them writing a program for one of my HP-calculators. Let's have a look at what I came out with:


RPN for HP-35s:

F001 LBL F               F013 ENTER
F002 STO N F014 x<> C
F003 STO D F015 STO× C
F004 SGN F016 x<> A
F005 STO B F017 STO- C
F006 STO C F018 x<>y
F007 CLx F019 x<> D
F008 STO A F020 STO× D
F009 RCL N F021 x<> B
F010 RCL+ B F022 STO- D
F011 RCL D F023 STOP
F012 INT÷ F024 GTO F009

Example:

5 XEQ F ENTER            0
1

R/S 1
5

R/S 1
4

R/S 1
3

R/S 2
5

. .
. .
. .

R/S 4
5

R/S 1
1


ALG for HP-35s:

E001 LBL E
E002 REGX#>N#>D
E003 1#>B#>C
E004 0#>A
E005 IDIV(N+B,D)#>K
E006 -A+K×(C#>A)#>C
E007 -B+K×(D#>B)#>D
E008 STOP
E009 GTO E005

Please note that #> stands for the black triangle that indicates STO-ring in a variable.
You may notice that this solution starts with 1/4 instead of 0/1. But since the first two entries can easily be found without a calculator, I think this can be accepted.


UserRPL for HP-48GX:

\<< DUP 1 DUP 0
\-> n d c b a
\<< { }
WHILE
a b \->V2 +
c n <
REPEAT
n b + d / IP
a OVER c DUP 'a' STO
* SWAP - 'c' STO
b SWAP d DUP 'b' STO
* SWAP - 'd' STO
END
\>>
\>>

Here we get a list of vectors [ p q ] indicating the fraction: p/q:

{
[ 0 1 ]
[ 1 5 ]
[ 1 4 ]
...
[ 3 4 ]
[ 4 5 ]
[ 1 1 ]
}


SysRPL for HP-48GX:

DEFINE a    1GETLAM
DEFINE a\<- 1PUTLAM
DEFINE b 2GETLAM
DEFINE b\<- 2PUTLAM
DEFINE c 3GETLAM
DEFINE c\<- 3PUTLAM
DEFINE d 4GETLAM
DEFINE d\<- 4PUTLAM
DEFINE n 5GETLAM
DEFINE n\<- 5PUTLAM
::
CK1&Dispatch
real
::
DUP %1 DUP %0
NULLLAM #5 NDUPN {}N BIND
#0
BEGIN
a b ' x/
#3 SYMBN
SWAP #1+
c n %<
WHILE
::
n b %+ d %/ %IP
a OVER c DUP a\<-
%* SWAP %- c\<-
b SWAP d DUP b\<-
%* SWAP %- d\<-
;
REPEAT
{}N
ABND
;
;

Now we get a list of algebraic expressions:

{ '0/1' '1/5' '1/4' ... '3/4' '4/5' '1/1' }

Looking at the different solutions I wondered whether I can still understand what I've done in a few weeks or months from now. Why do I have to burry the algorithm in a bunch of cryptic mnemonics when all I want to say is:


Python:

def farey( n ):
a, b, c, d = 0, 1, 1, n
print "%d/%d" % (a,b)
while (c < n):
k = int((n + b)/d)
a, b, c, d = c, d, k*c - a, k*d - b
print "%d/%d" % (a,b)

farey( 5 )
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1


The BASIC version for HP-71B is missing I know and it might be quiet similar to Python: a short one- or three-liner. Take it as a mini-challenge. Or use whatever calculator you like.

However this is not the International Obfuscated C Code Contest. Quiet the contrary: I tried to stay as close to the original program (Python) as possible. And it's not a complicated algorithm neither. Just be honest: which solution do you understand best at a first glimpse? Then why is it so much more fun to write a program using cryptic mnemonics?

Best regards

Thomas Klemm


#3

Hello Thomas,

I first read about this series in Recreations in the Theory of Numbers by Beiler. One of my favorite books.

Quote:
Just be honest: which solution do you understand best at a first glimpse?

Python. I was programming computers before calculators.

Quote:
Then why is it so much more fun to write a program using cryptic mnemonics?

The challenge. Being closer to the action, almost like writing machine code.

Since this is the year of the 41, here is my version with word-wrapped output (printer required).

i41CXp output:

RAW file: http://sense.net/~egan/41cx/FAREY.RAW

Barcode: http://sense.net/~egan/41cx/farey.pdf

Source:

01 LBL "FAREY"      18 RCL 00           35 CF 00            52 RCL 05           
02 FIX 00 19 RCL 02 36 ARCL Y 53 ALENG
03 CF 29 20 + 37 >"/" 54 +
04 CLA 21 RCL 04 38 ARCL X 55 X#Y?
05 >"F(" 22 / 39 FS? 00 56 >" "
06 ARCL X 23 INT 40 >"," 57 ALENG
07 >") = " 24 ENTER 41 25 58 ST+ 05
08 SF 00 25 X<> 03 42 RCL 05 59 ACA
09 STO 00 26 ST* 03 43 ALENG 60 CLA
10 STO 04 27 X<> 01 44 + 61 FS? 00
11 SIGN 28 ST- 03 45 X<Y? 62 GTO 01
12 STO 02 29 X<>Y 46 GTO 02 63 SF 29
13 STO 03 30 X<> 04 47 PRBUF 64 FIX 04
14 CLX 31 ST* 04 48 0 65 PRBUF
15 STO 01 32 X<> 02 49 STO 05 66 END
16 STO 05 33 ST- 04 50 LBL 02
17 LBL 01 34 X=Y? 51 24

Update: Reduced code size by 25%. Improved word-wrap output to use column 24. Fixed F(1).



Edited: 10 Jan 2009, 1:03 p.m.


#4

On the Teeth of Wheels, an article on the use of the related Stern-Brocot tree in the design of gears.

Quote:
I was programming computers before calculators.

I've started with an HP-41.
There might be some nostalgia involved as well.

Thanks for providing your solution with barcode and the book recommendation. Just had a look at it: seems promising.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Voyager battery installation sequence Peter Murphy (Livermore) 11 656 08-12-2012, 09:04 AM
Last Post: Les Koller
  Fibonacci Sequence Mike T. 29 1,383 11-05-2009, 01:01 PM
Last Post: Ken Shaw
  sequence on HP39G katana 2 216 10-07-2004, 12:32 PM
Last Post: Mike (Stgt)
  sequence Graphing Harrington 0 104 05-13-2004, 03:35 AM
Last Post: Harrington
  HP-15C key sequence donaldg 4 294 05-29-1999, 02:33 AM
Last Post: Jeff Woolsey

Forum Jump: