How to use the farey sequence generator
- Choose List a sequence, Neighbors or Approximate a decimal.
- For a list, enter n up to 30. For neighbors, enter n and a fraction with denominator at most n.
- To approximate a decimal, type it and the largest denominator you are willing to use.
- Read the terms, the neighbors with their mediants, or the closest fraction with its error.
Formula
Next term after a/b, c/d in F(n): (k c - a) / (k d - b), k = floor((n + b) / d)
Length of F(n) = 1 + phi(1) + phi(2) + ... + phi(n)
Neighbors a/b and c/d: b c - a d = 1
Mediant: (a + c) / (b + d)
phi is Euler's totient function, the count of numbers up to k that share no factor with k. The best bounded approximation of a decimal is one of the two Farey neighbors on either side of it.
F5, a neighbor search and pi
F5 has 11 terms: 0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5 and 1. Here 1 + (1 + 1 + 2 + 2 + 4) = 11. F10 has 33 terms and F30 has 279.
In F10 the neighbors of 3/7 are 2/5 and 4/9. Each pair satisfies b c - a d = 1: for 2/5 and 3/7 it is 5 x 3 - 2 x 7 = 1, and for 3/7 and 4/9 it is 7 x 4 - 3 x 9 = 1. Their mediants with 3/7 are 5/12 and 7/16. For 3.14159265358979 and denominators up to 100 the neighbors are 311/99 below and 22/7 above, and 311/99 is closer, off by 0.000178512. Allowing denominators up to 1000 gives 355/113, off by about 2.67e-7.
Why Farey neighbors matter
Two fractions are neighbors in some Farey sequence exactly when their cross products differ by 1. Between two neighbors there is no other fraction with a denominator up to the order of the sequence, so the first fraction to appear between them is their mediant, and it shows up when the order reaches the sum of their denominators. This is why neighbors give the best approximations with a limited denominator.
For fractions in general use the fraction calculator, expand a decimal into its continued fraction with the continued fraction calculator, or convert with the fraction to decimal converter.
Approximating a decimal
The page walks the Stern-Brocot tree toward your decimal, always taking mediants, and stops when the next mediant would use a denominator above your limit. The last lower and upper fractions are the two neighbors on each side. The better one is the closest fraction with a denominator within the limit. Exact fractions are detected: 0.5 with any limit above 1 is 1/2 with no error.
Assumptions and limits
- Farey sequences contain reduced fractions from 0 to 1. The list stops at order 30 and the neighbor search at order 2000.
- The decimal is read exactly as typed, not as a binary floating-point number, so 0.1 means one tenth.
- Decimals may be zero or more, up to 1,000,000, with at most 40 characters. Negative numbers and exponents are not accepted.
- The largest denominator can be up to one trillion in the approximation mode.
Frequently asked questions
What is a Farey sequence?
The Farey sequence of order n lists, in increasing order, every reduced fraction between 0 and 1 whose denominator is at most n. F5 has 11 terms, from 0/1 to 1/1.
What is the mediant of two fractions?
Add the numerators and add the denominators: the mediant of 1/2 and 2/3 is 3/5. It always lies strictly between the two fractions.
How do I find the best fraction with a small denominator?
Enter the decimal and the biggest denominator you can use. The page returns the nearest fraction below and above, and the closer of the two is the best approximation within that limit.
Why is 355/113 so accurate for pi?
It comes from the continued fraction of pi, which has an unusually large number right after 3, 7, 15, 1 and 292. Large numbers in the expansion mean the preceding convergent is very close, and 355/113 is off by about 2.7e-7.