Farey Sequence « Next Oldest | Next Newest »

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

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

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 2,339 08-12-2012, 09:04 AM Last Post: Les Koller Fibonacci Sequence Mike T. 29 4,991 11-05-2009, 01:01 PM Last Post: Ken Shaw sequence on HP39G katana 2 799 10-07-2004, 12:32 PM Last Post: Mike (Stgt) sequence Graphing Harrington 0 421 05-13-2004, 03:35 AM Last Post: Harrington HP-15C key sequence donaldg 4 1,086 05-29-1999, 02:33 AM Last Post: Jeff Woolsey

Forum Jump: