<p>Neighboring fractions in Farey sequences are described in Sec. 3 of Neighboring Fractions in Farey Subsequences, <a href="http://arxiv.org/abs/0801.1981" rel="nofollow">http://arxiv.org/abs/0801.1981</a> .</p>
What is the most efficient way to determine the Farey sequence of degree n?
<p>I am going to implement a Farey fraction approximation for converting limited-precision user input into possibly-repeating rationals.<br>
<a href="http://mathworld.wolfram.com/FareySequence.html" rel="nofollow">http://mathworld.wolfram.com/FareySequence.html</a></p>

<p>I can easily locate the closest Farey fraction in a sequence, and I can find Fn by recursively searching for mediant fractions by building the Stern-Brocot tree.<br>
<a href="http://mathworld.wolfram.com/Stern-BrocotTree.html" rel="nofollow">http://mathworld.wolfram.com/Stern-BrocotTree.html</a></p>

<p>However, the method I've come up with for finding the fractions in the sequence Fn seems very inefficient:<br>
(pseudo)<br></p>

<pre><code>For int i = 0 to fractions.count -2
{
    if fractions[i].denominator + fractions[i+1].denominator &lt; n
    {    
        insert new fraction(
            numerator = fractions[i].numerator + fractions[i+1].numerator
            ,denominator = fractions[i].denominator + fractions[i+1].denominator)
            //note that fraction will reduce itself
        addedAnElement = true
    }
}
if addedAnElement 
    repeat
</code></pre>

<p>I will almost always be defining the sequence Fn where n = 10^m where m >1</p>

<p>So perhaps it might be best to build the sequence one time and cache it... but it still seems like there should be a better way to derive it. </p>

<p><strong>EDIT:</strong><br>
This paper has a promising algorithm:<br>
<a href="http://www.math.harvard.edu/~corina/publications/farey.pdf" rel="nofollow">http://www.math.harvard.edu/~corina/publications/farey.pdf</a></p>

<p>I will try to implement. <br>
The trouble is that their "most efficient" algorithm requires knowing the prior two elements. I know element one of any sequence is 1/n but finding the second element seems a challenge...</p>

<p><strong>EDIT2:</strong><br>
I'm not sure how I overlooked this:<br>
Given F0 = 1/n<br>
If x > 2 then <br>
F1 = 1/(n-1)</p>

<p>Therefore for all n > 2, the first two fractions will always be<br>
1/n, 1/(n-1) and I can implement the solution from Patrascu.<br></p>

<p>So now, we the answer to this question should prove that this solution is or isn't optimal using benchmarks..</p>