# Smallest denominator for given accuracy

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 Convergents function.

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”

1. Mark Dickinson

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.

2. Mark Dickinson

Here’s what I get for the table, via Python:

Tolerance           π                   e                   φ
--------------------------------------------------------------------------------
1/100               22/7                19/7                13/8
1/1000              201/64              87/32               55/34
1/10000             333/106             193/71              144/89
1/100000            355/113             1071/394            377/233
1/1000000           355/113             2721/1001           1597/987
1/10000000          75948/24175         15062/5541          4181/2584
1/100000000         100798/32085        23225/8544          10946/6765
1/1000000000        103993/33102        49171/18089         46368/28657
1/10000000000       312689/99532        419314/154257       121393/75025


And here’s the script that produced the above table:

from fractions import Fraction
from decimal import Decimal

from simplefractions import simplest_in_interval

def interval_from_digits(digits):
"""
Given a truncated decimal expansion of an irrational number,
return an interval containing that number.

Example
-------
>>> interval_from_digits("3.141")
(Fraction(3141, 1000), Fraction(1571, 500))
"""
lower = Fraction(digits)
max_truncation_error = Fraction(f"1e{Decimal(digits).as_tuple().exponent}")
upper = lower + max_truncation_error
return lower, upper

def best_approximation(interval, tolerance):
"""
Given a small interval containing a target irrational number and a
tolerance, find the simplest fraction that approximates that irrational to
within the given tolerance.

Raises ValueError if the interval is not small enough to determine
the simplest fraction uniquely.
"""
lower, upper = interval

best_candidate = simplest_in_interval(lower - tolerance, upper + tolerance)

# Double check that it falls in the slightly-too-narrow interval
if not upper - tolerance <= best_candidate <= lower + tolerance:
raise ValueError("interval is too wide")
return best_candidate

# Values we're interested in, to 50 places after the point (truncated,
# not rounded).
pi_digits = "3.14159265358979323846264338327950288419716939937510"
e_digits = "2.71828182845904523536028747135266249775724709369995"
phi_digits = "1.61803398874989484820458683436563811772030917980576"

# Containing intervals
pi_interval = interval_from_digits(pi_digits)
e_interval = interval_from_digits(e_digits)
phi_interval = interval_from_digits(phi_digits)

# Table of best approximations
print(f"{'Tolerance':20}{'π':20}{'e':20}{'φ':20}")
print("-"*80)
for places in range(2, 11):
tolerance = Fraction(f"1e{-places}")
print(
f"{str(tolerance):20}"
f"{str(best_approximation(pi_interval, tolerance)):20}"
f"{str(best_approximation(e_interval, tolerance)):20}"
f"{str(best_approximation(phi_interval, tolerance)):20}"
)


The “simplefractions” package is a tiny package that I wrote a while ago for almost exactly this purpose; it’s available on PyPI.

3. Mark Dickinson

Apologies. Looks like that was a formatting fail.