Estimating Pi Using Coprime Numbers

Did you know you can estimate the value of π (pi) using probability and number theory?

This challenge explores a surprising mathematical relationship:
The probability that two randomly chosen integers are coprime, P(\text{coprime}) is equal to \frac{6}{\pi^2}

Coprime numbers?

Two numbers are coprime if their only common factor is 1.

Using this idea, you can estimate π by randomly generating pairs of integers and checking how often they are coprime.
​
If:
P(\text{coprime}) = \frac{6}{\pi^2} ​
Then we can rearrange to estimate π:
\pi \approx \sqrt{\frac{6}{P(\text{coprime})}} ​

So the aim of this challenge will be to write a program to:

• Generate many random pairs of integers
• Count how many of these pairs are coprime
• Use the ratio to estimate π

Not that to work out if two numbers are coprime, we will need to create a function to calculate their Greatest Common Denominator.

Step 1: Generating N pairs of random integers

For this step we will use the random library to generate random integer values (between 1 and 10,000), and a for loop, to generate N pairs.

import random, math

N = 1000
for i in range(0,N):
   number1 = random.randint(1,10000)
   number2 = random.randint(1,10000)

Step 2: Finding out if our pair of numbers are coprime

To check if two numbers are coprime, we first need to calculate their Greatest Common Denominator. We can do so using the following function, based on Euclid’s Division Algorithm:

def gcd(a, b):
    # Repeat until b becomes 0
    while b != 0:
        remainder = a % b   # Find the remainder when a is divided by b
        a = b               # Move b into a
        b = remainder       # Move remainder into b

    # When b is 0, a contains the GCD
    return a

We can use this function in our previous for loop to count how many pairs of numbers are coprime:

import random, math

N = 1000
coprime_count = 0

for i in range(0,N):
   number1 = random.randint(1,10000)
   number2 = random.randint(1,10000)
   if gcd(number1, number2) == 1:
      coprime_count = coprime_count + 1

Step 3: Outputting the ratio of coprime pairs:

We can now calculate and display the ratio of coprime pairs (Probability that two randomly generated numbers are coprime):

probability = coprime_count / N

Estimating Pi

We can now estimate Pi using the following formula:
\pi \approx \sqrt{\frac{6}{P(\text{coprime})}}

pi_estimate = math.sqrt(6 / probability)

And finally we can display our estimate on screen as well as calculate the percentage of accuracy of our estimate:

print("Number of pairs", N)
print("Number of coprime", coprime_count)
print("Estimated value of Pi:", pi_estimate)
print("Actual value of Pi:", math.pi)
print("Percentage of accuracy:", round(100 * abs(math.pi - pi_estimate)/math.pi,2))

Python Code

Your turn! You can now complete the code below:

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area