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

1R/S 1

5R/S 1

4R/S 1

3R/S 2

5. .

. .

. .R/S 4

5R/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