I was reading about Ford circles today, and was planning on writing about them. But then I noticed that one of the things I wanted to say was based on some things I didn’t say about Farey sequences when I talked about them a few days ago. So I thought I’d go back and fill in that gap, and save Ford circles for tomorrow.

So what did I skip? Well, I mentioned that to get from one Farey sequence to the next, you throw in mediants whose denominators aren’t too big. Is there a way, given a fraction in to figure out what terms in it was the mediant of? Well, we could, of course, list the terms in , in order, and then pick the two that surround the value . I’m after another way.

Since is supposed to be reduced, and are relatively prime, and so there are integers and such that (this usually (in my mind) gets written with a “+”, not a “-“, but just change the sign of your ). Once you’ve found such a pair , all of the other pairs that satisfy the same equation are of the form , where is any integer. Among the , there is only one in the interval . Abusing notation a bit, or assuming you picked well to start, let’s call this value , and its partner . I claim that is the term directly before in .

Before talking about , I should have checked that . If this is not the case, then means , in which case we are in which is just 0/1 and 1/1. Not much interesting going on there. So let’s go ahead and assume .

Now, the linear equation gets re-written to show that (so the fractions are at least in the correct order). Messing about with inequalities some more, you can check that , and since and are relatively prime (they satisfy the linear equation), the fraction is actually in . Let be the predecessor of in (we want to show ). Since it is a neighbor, we showed last time that then . But now we’re saying that all solutions of the equation have a fixed form. That is, and for some integer . But if then is not in , and so is not in . So and , and we’re done.

Man, ok, so, after all that, we now know how to find the term before in . I’ll call it , sticking with our notation above. What about the term after ? You could play mostly the same games as above, I suppose. Or, if the successor is , then we know that and , since we made as a mediant. So and , easy enough. [**Update** 20091109: You have to be careful with this. The above method for finding the successor to in only works because you are in . If you look for successors in in , where , this method, using the predecessor, is wrong. For example, 1/4 is the predecessor of 1/3 in , but the fraction (1-1)/(3-4) suggested by the previous method is clearly NOT the sucessor of 1/3 in ]

So we know the neighbors of in . What is the next Farey sequence when gets a new neighbor? Let’s stick to the next time it gets a new neighbor “on the left” (less than itself). We know that when that happens, it had to be because we made the mediant with the old neighbor, our friend . So the next neighbor is , which doesn’t show up until . The newest neighbor after that will be the mediant with this new neighbor, i.e., , in . Continuing on, we see that all of the neighbors are of the form , for some positive integer . I called these -weighted mediants (of and ) yesterday.

The story goes pretty much the same on the right side. I called the neighbor on the right, in , . The next neighbors will be , , etc. These are the -weighted mediants of and .

We can put both of these into the same statement by noticing that the mediant of with is the same as the mediant of with . In other words, all of the neighbors of , in all of the Farey sequences, can be written as weighted mediants of with . They will have numerators of the form and denominators of the form . Guess what? These are exactly all of the solutions to . Go back a few paragraphs, it’s the same thing I said there.

In summary, the neighbors to , in any Farey sequence, are in one-to-one correspondence with solutions to .

If I knew what I were doing, I could probably have gotten to this statement a bit more quickly. But I don’t remember the last time I knew what I was doing, so there you have it.

Tags: farey, mablowrimo

November 5, 2009 at 9:51 am |

Farey sequences are a cool subject indeed, I’m thoroughly enjoying your series on them. When you find time, go back to Euler’s Flying Circus and give 192 and 198 a try…

198 is arguably the hardest problem posted at Project Euler if you look at how long its been posted and how many people have got it right. Yet it’s quite straightforward to solve once you know all you now know…

November 5, 2009 at 7:18 pm |

Thanks for the encouragement! And for the pointer to fun Project Euler problems. I wasn’t to get to those two for a while, working my way through in order. By the time I got there, I’d probably forget all of the math I’d need to solve them. It might be a few days, but I’ll attack those two next.

November 9, 2009 at 10:07 am |

Curse you Jaime! I’ve been working on 198, and spending far too much time on it. I’ve got 3 “solutions” going, but all of them are too slow to ramp up to the bound 10^8. Got an idea how to improve things… but not sure when I should let myself get back to the problem, versus doing “real work”.

December 9, 2009 at 11:32 pm |

[…] I’m getting to this problem a little out of order. Jaime told me to. I was talking about Neighbors in Farey Sequences, on another blog, and he said this problem would fit well with what I was doing. In fact, if you […]

September 15, 2013 at 12:43 pm |

[…] post was inspired by Sumidot’s blog. The colorful picture was about another related topic: Ford’s […]

November 25, 2016 at 7:06 pm |

[…] https://sumidiot.wordpress.com/2009/11/05/neighbors-in-farey-sequences/ […]