Probably relatively prime
What is the probability that two randomly chosen positive integers are relatively prime?
Two numbers are relatively prime if they have no common factors.
Two numbers are relatively prime if they have no common factors.
Labels: mathschallenge
posted by Chris at
5:03 PM
10 Comments:
if the 2 random numbers are from 0 to infinity,then the chances are infinitly aproching zero.
how smart i'am me.I spelled my own name wrong.
The probability that the two numbers have 2 as a common factor (i.e. both even) is 1/4, so the probability that they don't is (1 - 1/4).
Likewise the prob that 3 is not a common factor is (1 - 1/9).
And so on through the primes, i.e. the required probability is:
Prod (1 - p.i) where p.i is the i-th prime, for i = 1 to n.
The value of the n-th prime would, I think, be the highest prime below half the larger of the two random numbers.
Although it may seem paradoxical, the probability of a random integer having a given prime factor is not zero.
Here's a major kick start: The probabilty of randomly choosing an integer and it having a prime factor p is approximately 1/p. (Think about it!)
Kmigthmare, LOL. How's the couch holding up?
Wiz, that is an extremely good start - I'm stunned at how far you got. You've made a slip when introducting the product over primes though (you forgot to square p.i). How did you deduce the basic probability formula, P(p) = 1/p?
Because you stopped so abrubptly, I'll hazard a guess that you don't know about the Riemann Zeta function or Euclid's product formula. Do a Google with "euler product formula" and follow the Wikipedia link. If you haven't come across this stuff before, then your jaw will drop in sheer amazement when you see what your expression is equivalent to. You'll be able to finish the solution in a mere moments after that.
Chris, I'm way out of my depth here!
Following your Wikipedia links through Euler, Riemann, zeta functions, etc, I find a formula which says the answer is 1 / sum (1/i^2) for i = 1 to infinity.
This comes to 0.607927101...
This is apparently equal to 6/pi^2.
But I can't claim any credit for something of which I have very little understanding!
In language that I can understand, there is roughly a 60% chance that two numbers chosen at random will have no common factors.
Hi Wiz. You don't seem to be out of your depth. I think you have done brilliantly well. Do you see why I think that Euler's product formula is amazing?
You have obtained the desired result: 6/π² ≈ 60.1%. I think that's quite cool. Who ordered the circle?
Zeta(s) has 0's at s = -2, -4, -6 ... (the so-called trivial zeroes) and another set that all seem to lie on the line s = 1/2, but are otherwise more or less random. The first 10^13 roots have been checked. Prove that all the roots lie on s = 1/2 and you'll have fame and fortune ($1,000,000 from the Clay Institute for starters) rained upon you.
I forgot to mention that the particular result:
Zeta(2) = 1 + 1/(2^2) + 1/(3^2) + 1/(4^2) + ... = π²/6 is known as the Basel problem. Even the Bernoulli's were unable to find that result.
Hi Wiz, I'm a twerp. I see you did explain why P(p) = 1/p. That's exactly the way I see it too. Don't undersell yourself, I fancy that not many people would have thought of that for themselves. Notice that you're the only person who did it.
Post a Comment
Links to this post:
Create a Link
<< Home