The Museum of HP Calculators

HP Forum Archive 18

Farey Sequence
Message #1 Posted by Thomas Klemm on 9 Jan 2009, 4:22 p.m.

## 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

 Re: Farey SequenceMessage #2 Posted by Egan Ford on 10 Jan 2009, 1:10 a.m.,in response to message #1 by Thomas Klemm 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: 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 XY 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.

 Re: Farey SequenceMessage #3 Posted by Thomas Klemm on 12 Jan 2009, 5:35 p.m.,in response to message #2 by Egan Ford 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.

Go back to the main exhibit hall