A Rational Approximation of Pi Using the Pigeonhole Principle

Below is a short Python script that finds a fractional approximation of \(\pi\) using the first 1001 multiples of \(\pi\) (the case with 11 multiples of \(\pi\) can easily be done by hand). It makes use of the pigeonhole principle. The 11-multiple version of the problem has been used in the module teaching the pigeonhole principle in various classes that I have taken or taught.

The pigeonhole principle states that:

If \(n > m\) and \(n\) pigeons are placed in \(m \) pigeonholes, then one pigeonhole must contain more than one pigeon.

Problem and Solution

Given the following multiples of \(\pi\), each truncated to four decimal places:

\(0\pi = 0.0000, 1\pi = 3.1415, 2\pi = 6.2831, … 1001\pi = 3144.7342 \)

Use the pigeonhole principle to find a good rational approximation to \(\pi\).

If we are given the multiples \(0 \pi \) through \( 1000 \pi \), we have 1001 multiples of \(0 \pi \). Consider the first three digits to the right of the decimal place of a number (in 123.456, the digits 456).

There are only 1000 possibilities for the first three digits to the right of the decimal place. Given 1001 multiples of \(\pi \), we can conclude from the pigeonhole principle that two such multiples must have the same three digits. This means that the difference to the right of the decimal point them is less than 0.001 in absolute value (for example, \(0.1235 - 0.1230 = 0.005\)).

Let \(m \pi, n \pi, m > n \) be two multiples sharing the three numbers to the right of the decimal place. Then:

Because \( m\pi - n\pi \) has a difference to the right of the decimal place that is less than 0.001, it approximates some integer. Therefore, we can use \( \frac{m \pi - n \pi}{m - n} \) as a rational approximation of \pi.

Code

For 11 multiples of \( \pi \), the problem is trivial to do by hand. For 1001 multiples, I’ve written a Python script to solve the problem. You can play around with the code here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
pi.py
Calculates an approximation of pi given the multiples 0pi - 1000pi using
the Pigeonhole Principle. Outputs the first approximation found.

Author: Louis Li
"""

import math


def main():
    # Store the decimals we've found in a dictionary with its multiple of pi
    d = dict()

    for n in xrange(0, 1001):
        n_pi = n * math.pi

        first_three_dec = int(math.floor((n_pi * 1000) % 1000))

        if not first_three_dec in d:
            d[first_three_dec] = n
        else:
            # Calculate an approximation, having found two numbers
            # with the same first three decimal places
            m = d[first_three_dec]
            m_pi = m * math.pi

            print int(round(n_pi - m_pi))
            print "----- = ", ((n_pi - m_pi) / (n - m)), \
                "(m = %d, n = %d)" % (m, n)
            print (n - m)
            print "\nActual value, pi: ", math.pi
            break

if __name__ == '__main__':
    main()

This will output the first solution found:

1
2
3
4
5
355
----- =  3.14159265359 (m = 1, n = 114)
113

Actual value, pi:  3.14159265359

Comments