Fractional Approximations of Pi

Now that we are just past Pi Approximation Day (22/7 or July 22), I thought about how to find other fractional approximations of \(\pi\) with small numerators and denominators. Instead of using things like continued fractions and Stern-Brocot trees, I decided that I was going to brute force this thing, just because I can.

To find the best fractional approximation \(n/d\) (such as 22/7) for pi, given a denominator \(d\), lets do the following. For each \(d\), compute \(\pi d\) and then take the floor (the greatest integer less than or equal, written as \(\lfloor x\rfloor\)) and the ceiling (the smallest integer greater than or equal, written as \(\lceil x\rceil\)) of \(\pi d\). This results in two fractions,

\[\frac{\lfloor\pi d\rfloor}{d}\]

and

\[\frac{\lceil\pi d\rceil}{d}.\]

One of these must be the best approximation for the given \(d\), because \(\lfloor\pi d\rfloor/d\lt\pi\), \(\lceil\pi d\rceil/d\gt\pi\), and \(\lceil\pi d\rceil=\lfloor\pi d\rfloor+1\).

I’ve then written the following Python program that tries all denominators from 1 to 10000 and prints out a line when it finds a new best approximation.

from __future__ import print_function
from __future__ import division
 
import numpy as np
 
best_diff = 1
for d in range(1, 10001):
    nf = int(np.floor(np.pi * d))
    nc = int(np.ceil(np.pi * d))
    nf_diff = np.abs(nf / d - np.pi)
    nc_diff = np.abs(nc / d - np.pi)
    if nf_diff < best_diff:
        best_diff = nf_diff
        print('{} / {}: {:.2e}'.format(nf, d, best_diff))
    elif nc_diff < best_diff:
        best_diff = nc_diff
        print('{} / {}: {:.2e}'.format(nc, d, best_diff))

Running this program, so with the denominator going up to 10000, produces the following output.

3 / 1: 1.42e-01
13 / 4: 1.08e-01
16 / 5: 5.84e-02
19 / 6: 2.51e-02
22 / 7: 1.26e-03
179 / 57: 1.24e-03
201 / 64: 9.68e-04
223 / 71: 7.48e-04
245 / 78: 5.67e-04
267 / 85: 4.16e-04
289 / 92: 2.88e-04
311 / 99: 1.79e-04
333 / 106: 8.32e-05
355 / 113: 2.67e-07

This output lists each fraction that breaks the record for being closer to \(\pi\), ordered by increasing accuracy. 22/7 is found, and the other well-known approximation of 355/113 also turns up. The fact that no new best is found for a denominator up to 10000 shows that 355/113 is an exceptionally good approximation. The record is only beaten next by 52163/16604.