|
Title: Farey Sequence
Submitter: James Kassemi
(other recipes)
Last Updated: 2006/06/24
Version no: 1.0
Category:
Algorithms
|
|
|
Description:
Function provides farey sequence, F(n), for any integer n.
Source: Text Source
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())]
Discussion:
There's probably a more elegant solution out there, but I couldn't find it. Note: it doesn't prepend (0,1) and append (1,1)...
For more info: http://mathworld.wolfram.com/FareySequence.html
|
|
Add comment
|
|
Number of comments: 2
Some simpler ways based on the Farey properties, Scott David Daniels, 2006/06/26
See also my Recipe 52317 (whose comments section seems mangled now).
In the following we have a straight-forward recursive generator
named "Farey_r" and an equivalent, but more efficient, generator
named "farey". "Farey_r" is provided simply to make it 'clear'
(and more provable) what the generator is computing.
def Farey_r(limit, start=(0, 1), stop=(1, 1)):
'''recursive definition of a Farey sequence generator'''
n, d = start
N, D = stop
mediant_d = d + D
if mediant_d <= limit:
mediant = (n + N), mediant_d
for pair in Farey_r(limit, start, mediant): yield pair
for pair in Farey_r(limit, mediant, stop): yield pair
else:
yield start
def farey(limit):
'''Fast computation of Farey sequence as a generator'''
# n, d is the start fraction n/d (0,1) initially
# N, D is the stop fraction N/D (1,1) initially
pend = []
n = 0
d = N = D = 1
while True:
mediant_d = d + D
if mediant_d <= limit:
mediant_n = n + N
pend.append((mediant_n, mediant_d, N, D))
N = mediant_n
D = mediant_d
else:
yield n, d
if pend:
n, d, N, D = pend.pop()
else:
break
Add comment
Yep, James Kassemi, 2006/06/27
Sorry about not referencing your recipe, I thought I did a search, but I must have missed it.
For those who didn't see it, take a look, the mediant calculation approach is certainly more effective.
Add comment
|
|
|
|
