Skip to content

Instantly share code, notes, and snippets.

@manucorporat
Created March 30, 2013 15:30
Show Gist options
  • Save manucorporat/5277108 to your computer and use it in GitHub Desktop.
Save manucorporat/5277108 to your computer and use it in GitHub Desktop.
Simulation in python of the probability that two randomly chosen numbers are coprime, is close to 6 / PI^2
# Simulation created by Manuel Martinez-Almeida
# http://en.wikipedia.org/wiki/Coprime_integers
import fractions
import math
import random
def calculateProbability(end, steps):
count = 0
for i in range(0, steps):
# get two random integers, from 1 to $end
nu0 = random.randint(1, end)
nu1 = random.randint(1, end)
# increment the counter if both integers are coprimes,
# coprimes: greatest common divisor is 1. gcd(nu0, nu1) == 1
if fractions.gcd(nu0, nu1) == 1:
count += 1
return float(count)/steps
# UNIT TEST
result = calculateProbability(10000000000, 1000000)
pi = math.sqrt(6 / result)
error = abs(math.pi-pi)
# SHOW RESULTS
print "Results:"
print " Calculated: ", pi
print " PI: ", math.pi
print "\nError:"
print " Absolute error: ", error
print " Relative error: ", error/math.pi
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment