10
$\begingroup$

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)

enter image description here

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

$\endgroup$

1 Answer 1

3
$\begingroup$

It depends on the model of computation you're using. If your memory slots can contain arbitrarily large integers (rather than single bits), and you can perform arithmetic operations in constant time, the answer is yes. Basically you use the following algorithm to step through the Farey sequence of the correct order:

https://en.wikipedia.org/wiki/Farey_sequence#Next_term

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)$).

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Nov 29, 2015 at 18:41
  • 1
    $\begingroup$ You just need to find any fraction within the interval, then iterate backwards until you hit the leftmost fraction in the interval, then iterate forwards. $\endgroup$ Nov 29, 2015 at 19:38
  • $\begingroup$ 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. $\endgroup$ Nov 29, 2015 at 20:52
  • 1
    $\begingroup$ Oh, then you can just do a breadth-first search of the Stern-Brocot tree, pruning any nodes that are no longer in the interval of interest: en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree $\endgroup$ Nov 29, 2015 at 21:15
  • $\begingroup$ I am implementing this one. Not finished yet, but to be honest I don't see beforehand why this procedure will not take increasing amount of resources. $\endgroup$ Nov 30, 2015 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.