The following table gives the best rational approximations to π, e, and φ (golden ratio) for a given accuracy goal. Here “best” means the fraction with the smallest denominator that meets the accuracy requirement.
I found these fractions using Mathematica’s
For any irrational number, the “convergents” of its continued fraction representation give a sequence of rational approximations, each the most accurate possible given the size of its denominator. The convergents of a continued fraction are like the partial sums of a series, the intermediate steps you get in evaluating the limit. More on that here.
Notice there are some repeated entries in the approximations for π. For example, the best approximation for π after the familiar 22/7 is 333/106 = 3.141509…. The fraction with the smallest denominator that gives you at least 3 decimal places actually gives you 4 decimal place. Buy one get one free.
There’s only one repeated row in the e column and none in the φ column. So it may seem there are no interesting patterns in the approximations to φ. But there are. It’s just that our presentation conceals them.
For one thing, all the numerators and denominators in the φ column are Fibonacci numbers. In fact, each fraction contains consecutive Fibonacci numbers: each numerator is the successor of the denominator in the Fibonacci series. There are no repeated rows because these ratios converge slowly to φ.
We don’t see the pattern in the convergents for φ clearly in the table because we pick out the ones that meet our accuracy goals. If we showed all the convergents we’d see that the nth convergent is the ratio of the (n+1)st and nth Fibonacci numbers.
In a sense made precise here, φ is the hardest irrational number to approximate with rational numbers. The bottom row of the table above gives the 8th convergent for π, the 15th convergent for e, and the 25th convergent for φ.
3 thoughts on “Smallest denominator for given accuracy”
Some of those table entries don’t look quite right: for example, for the π column, I think the next entry after `22/7` should be `201/64` (which is within `1e-3` of π, but has smaller denominator than `333/106`). Similarly, the π entry for `10^-7` should be `75948/24175`. Those numbers are semiconvergents rather than convergents – to find the “best” approximation within given bounds, it’s necessary to take those semiconvergents into account.
Here’s what I get for the table, via Python:
And here’s the script that produced the above table:
The “simplefractions” package is a tiny package that I wrote a while ago for almost exactly this purpose; it’s available on PyPI.
Apologies. Looks like that was a formatting fail.