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$?
