View Single Post
Old 2017-02-27, 15:33   #4
(loop (#_fork))
fivemack's Avatar
Feb 2006
Cambridge, England

3×19×113 Posts

Originally Posted by mickfrancis View Post
Thanks for the response. I'm afraid you'll have to forgive my ignorance, but I can't see at the moment how continued fractions help me here - any hints appreciated.

Write R as a continued fraction, compute the convergents, and the denominator of a convergent sufficiently far along the list will be a usable M - roughly, and there are various O(1) factors here which you probably want to look up in Hardy & Wright, if D is the denominator of a continued fraction convergent then DR will be within about 1/D of an integer.

If you want a worst-case term, there's a nice theorem that phi = (1+sqrt(5))/2 is the hardest number to approximate with continued fractions, and the nth denominator of the continued fraction of phi is the nth Fibonacci number. So if you take your epsilon, and let n be the index of the first Fibonacci number larger than the reciprocal of epsilon, the denominator of the nth continued fraction convergent of R will definitely be a usable multiplier.

Last fiddled with by fivemack on 2017-02-27 at 15:33
fivemack is offline   Reply With Quote