Tidbits @ Kassemi

A collection of opinions, thoughts, tricks and misc. information.

Saturday, June 24, 2006


Farey Sequence Python Implementation

I looked this up a little earlier today, and wasn't finding anything that would give me a simple farey sequence with python. Figured I may as well post what I wrote that I'm about to stick up in the python cookbook.

def farey(n):
def gcd(a,b):
while b: a,b = b,a%b
return a

def simplify(a,b):
g = gcd(a,b)
return (a/g,b/g)

fs = dict()
for i in xrange(1,n+1):
for i2 in xrange(1,i+1):
if i2 < n and i != i2:
r = simplify(i2,i)
fs[float(i2)/i] = r

return [fs[k] for k in sorted(fs.keys())]

It neglects the (0,1) and (1,1) because they're obvious enough and I
end up removing them in my code anyway. Somebody out there can probably
figure out a more efficient and elegant solution, but this is pretty
quick and works just fine.

Take it easy,

Comments: Post a Comment

<< Home


August 2005   September 2005   October 2005   November 2005   December 2005   January 2006   February 2006   March 2006   April 2006   June 2006   July 2006   August 2006   September 2006   October 2006   November 2006  

This page is powered by Blogger. Isn't yours?