All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Random Primes (Posted on 2003-07-10) Difficulty: 4 of 5
If you pick any two integers at random, what is that probability that they will be relatively prime? ("relatively prime" means that the two numbers share no divisors except 1)

Tell how you end up with the answer.

See The Solution Submitted by not_so_einstein    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 3 of 9 |
First a caveat: The method by which you randomize the numbers is going to affect the probability. If each of the two random numbers is drawn from a uniform distribution of integers from 1 to 10, then the probability would be 63% as 63 out of the 100 equally possible pairings would be relatively prime. If drawn from a uniform distribution from 1 to 100, the probability would be 60.87% as 6087 of the possible 10000 pairings would be relatively prime. If the two numbers were each the result of a toss of two dice, 784 of the 1296 ways of the dice falling would result in relative primeness, or 60.49...%.

But if we assume that what is meant is to find what the probability approaches if the two numbers are drawn from a uniform distribution from 1 to n, as n increases without limit, then the following logic applies:

The probability that the two numbers would both be even (divisible by 2) is (1/2)^2 so the probability that they are not both divisible by 2 is 1- (1/2)^2. This is independent of the probability that they are divisible by 3. The probability that they are not divisible by 3 is 1 - (1/3)^2. This is repeated for each prime divisor, as the probability of divisibility by different primes is independent, and divisibility by primes is all that counts. So we need (1-(1/2)^2)*(1-(1/3)^2)*(1-(1/5)^2)*(1-(1/7)^2)*(1-(1/11)^2)*....

By the time the 10th prime, 29, is considered, the probability is down to .612344.... By the hundredth prime, 541, it is down to .6080819.... By the thousandth prime, 7919, .607929.... By the 10,000th prime, 104,729, it's .6079275.... By the 100,000th prime, 1,299,709, it's .6079271....

By the millionth prime, 15,485,863, it is still characterized by .6079271..., so I'll leave it at that.

By the way the program for the above:
list
5 T=1
6 P=1
10 for I=1 to 1000000
15 P=nxtprm(P)
20 T=T*(1-1/(P*P))
30 if I/10000=int(I/10000) or I<11 then print I,P,T
40 next
OK
  Posted by Charlie on 2003-07-10 08:24:24
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information