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
| 
Go back to the main exhibit hall