A question on Farey's sequences.
in [Math]
|
Prev: theory behind the upper limit approx 400 million light years Chapt 11, Space is EM; magnet & iron filings Experiment #106; ATOM TOTALITY
Next: Simple permutation question
From: Ludovicus on 23 May 2010 07:48 Is it possible to calculate the place k of a given reduced fracction a / b in the Farey's sequence of order N?. And viceversa: Given the position k in a sequence of order N, to deduct the fraction a / b. Example: The fracction 4 / 97 occur in the place 197 of the Farey's sequence of order 113. How can I know it without calculate all the smaller terms?
From: spudnik on 23 May 2010 13:26 the second part of the question is clearly trivial, and the first part seems to be its inverse, or what ever. have Farey sequences ever been used for continued fractions, or does that make any sense, at all? > Example: The fracction 4 / 97 occur in the place 197 of > the Farey's sequence of order 113. How can I know it > without calculate all the smaller terms? --Pi, the surfer's canonical value -- good to at least one place! http://wlym.com
From: Ludovicus on 23 May 2010 15:43 On May 23, 1:26 pm, spudnik <Space...(a)hotmail.com> wrote: > the second part of the question is clearly trivial, and > the first part seems to be its inverse, or what ever. > Trivial? Please. I am interested in knowing the algorithm. And tell me what fracction is in place 5887 in the Farey's sequence of order 257.
From: achille on 23 May 2010 18:25 On May 24, 3:43 am, Ludovicus <luir...(a)yahoo.com> wrote: > On May 23, 1:26 pm, spudnik <Space...(a)hotmail.com> wrote:> the second part of the question is clearly trivial, and > > the first part seems to be its inverse, or what ever. > > Trivial? Please. I am interested in knowing the algorithm. > And tell me what fracction is in place 5887 > in the Farey's sequence of order 257. 37/127? The algorithm listed in Wiki's 'Farey sequence' entry is very effective in generating the whole sequence for given order. (even though it need to calculate all the small terms.) REF: http://en.wikipedia.org/wiki/Farey_sequence
From: Gerry Myerson on 23 May 2010 19:19
In article <3f85ea9c-ab70-4393-bf11-358a7cd5c0ba(a)y21g2000vba.googlegroups.com>, Ludovicus <luiroto(a)yahoo.com> wrote: > Is it possible to calculate the place k of a given reduced > fracction a / b in the Farey's sequence of order N?. > And viceversa: Given the position k in a sequence of > order N, to deduct the fraction a / b. > Example: The fracction 4 / 97 occur in the place 197 of > the Farey's sequence of order 113. How can I know it > without calculate all the smaller terms? I don't know if there's a better way to get exact answers, but you can get good approximations based on two facts: 1. The number of terms in the Farey sequence of order N is the sum from 1 to N of phi(n), where phi is the Euler phi-function, and that sum is asymptotic to (3 / pi^2) N^2, 2. The Farey sequence is, in the limit, uniformly distributed. So the sequence of order 113 has about 3881 terms, and (4 / 97)(3881) = 160, so 4 / 97 should be around the 160th term. Obviously this approximation is very rough. There are better approximations out there for the sum of phi(n). -- Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email) |