# Confusion with practically implementing rational approximations

Writing a program visualizing Ford circles I've encountered a seemingly purely programmatic puzzle but then gradually realized there are some mathematical aspects of it which I don't understand. Let me start with an output (it is from a question on Mathematica SE)

This is a particular case - zooming in to a real number $x$ ($\frac1\pi$ in this case). In some detail, I do the following: at each step, I increase the zoom factor by the same fixed number $z$ ($1.04$ in this case); so, it is (roughly) $z^n$ at the $n$th step. I then consider the rectangle $(x-z^{-n},x+z^{-n})\times(0,z^{-n})$. I have certain amount of Ford circles which showed up in the previous rectangles. I then throw out those which drop out of the picture. Then, I check in succession all possible new denominators $q$ of those ratios $\frac pq$ such that their Ford circle radii $\frac1{2q^2}$ would exceed one pixel in the picture (in this case, the picture is roughly $500\times250$ pixels, so the condition is roughly $q<\sqrt{500z^n}$). Among those new $q$ I then choose those $p$ with $p$ coprime to $q$ and the Ford circle of $\frac pq$ intersecting my $n$th rectangle.

Thus at each step I throw out some $\frac pq$s with $q\leqslant\sqrt{500z^{n-1}}$ and add some new ones with $\sqrt{500z^{n-1}}<q\leqslant\sqrt{500z^n}$.

Now comes the question

From the above description, it is clear that the number of new potential denominators I have to check grows roughly by a factor of $\sqrt z$ after each step (measuring actual program runs confirms this). On the other hand, as the picture shows, the number of circles on each frame is roughly the same; again, counting them programmatically confirms this (but also it is clear that by physical reasons the number of all possible circles that can be distinguished on a drawing like this is bounded). This suggests that there might be some rational approximation algorithm which might output this fixed amount of rationals by using the same amount of resources for each step. More precisely,

Given a real number $x$ and another one $z=1+\varepsilon$, and also another one $N$, is there an algorithm which for every natural $n$ would give the list of all irreducible fractions $\frac pq$ with $\sqrt{Nz^{n-1}}<q\leqslant\sqrt{Nz^n}$ and $x-z^{-n}-\frac1{2q^2}\leqslant\frac pq\leqslant x+z^{-n}+\frac1{2q^2}$ in the same time and using the same amount of memory for all $n$?

Alternatively, if you use the traditional model of computation where you can only manipulate a bounded number of bits in constant time, then clearly no such algorithm exists (since merely printing the digits of $q$ takes time proportional to $\log(q)$).
• Acknowledged. But why don't I need increasing amount of resources to locate the needed interval in the needed Farey sequence? I mean, the number of the sequence grows as $\sqrt{Nz^n}$ so its length as $Cz^n$, how do I locate the starting value? After that it is clear, I just step through it one by one, but how to find out where to start? – მამუკა ჯიბლაძე Nov 29 '15 at 18:41
• Hmmm after having accepted - now trying to use it and I'm still stuck. I actually need two adjacent fractions of the $n$th Farey sequence in the interval to start. Actually (modifying the question slightly) I'm OK with starting from already having done the previous step, i. e. supposing I already have the required subsequence of the $\lfloor\sqrt{Nz^{n-1}}\rfloor$th Farey sequence in the $n-1$st interval, I now need to get the subsequence of the $\lfloor\sqrt{Nz^n}\rfloor$th sequence in the $n$th interval, and for that I need its two adjacent entries in this interval. – მამუკა ჯიბლაძე Nov 29 '15 at 20:52