Relatively prime

[bonanova]

A huge bin contains distinctly numbered balls, and you choose two of them at random.

I give you 2 to 1 odds that the numbers will be relatively prime.

 

For example,

You pick 6 and 13. I win $1.

You pick 5 and 25. You win $2.

 

Do you take the bet?

[BMAD]

it looks like the probability of two numbers being relatively prime is almost 60%. If I win 2 dollars 40% of the time and lose $1 60% of the time then I should make 20 cents on average. right? If that is true, then i will play.

Edited April 28, 2015 by BMAD

[dgreening]

Yes, I would take the bet ... but I do not have a strong proof

 

Just based on odd and even numbers if we get 2 even numbers they are
relatively prime. So 1/4 of the time you would expect a positive pay off. If
for a moment we rule out any odd number as being
co-prime, we would get -1 three times out of four

The worst expected pay off [based on this poor assumption] would be

P*min = (1*(+2) + 3*(-1))/4 = -1/4

If just 1 out of 9 combinations involving an odd number were relatively
prime, the Pay off would  go to zero [making it a fair game].

 

[this is where things get shaky].

I have examined numbers up to 65 and found that if at least one number is
odd, the chances of the pair being relatively prime is closer to 2/9 which would
return a positive expected pay off.

I am sure that someone out there has an elegant solution, that I look forward
to seeing!

[Pickett]

So, if I am correct in assuming "relatively prime" simply means that one number is not evenly divisible by the other, then here are my initial thoughts:

 

You have a 1/n chance of first drawing a "1"...in which case, you will win automatically (1/1 chance)

You have a 1/n chance of first drawing a "2"...in which case, you will win if the second number is even OR a factor of 2 (aka: 1)

You have a 1/n chance of first drawing a "3"...in which case, you will win if the other number is a multiple of 3 OR a factor of 3 (aka: 1)

You have a 1/n chance of first drawing a "4"...in which case, you will win if the other number is a multiple of 4 OR a factor of 4 (aka: 1 or 2)

...

You have a 1/n chance of drawing "x"...in which case, you will win if the other number is a multiple of x OR a factor of x

 

So let FACT(x) = number of factors of number x...we can then write our chance of winning to be:

 

SUM (1/n * (1/x + FACT(X)/n)), x=1..n

Which clearly just get worse and worse the more balls there are in the bin...in which case, I would only take the bet if there were visibly "few" (less than 20 or so) balls in the bin.

 

Now, I suppose my above reasoning only holds if we assume all the numbers 1-n are in the bin...if you have completely random/arbitrary numbers...then, my reasoning probably completely falls through. Again, just my first thoughts. I am also curious to see what others come up with.

[harey]

100% loss

if the bin contains even numbers starting at 4

[phil1882]

i'd take the bet.

assuming an even distribution of numbers, say the numbers from 1 to 10,000.

you have a 1/4 chance of getting both diviable by 2, a 1/9 chance of both divisable by 3, a 1/25 chance of both diviable by 5, and so on.

the first one in of itself however gives you break even expected payout. the remaining ones increases it.

[bonanova]

Two numbers are relatively prime iff their GCF is 1.

{6, 7} are relatively prime.

{6, 8}, {6, 9} and {6, 10} are not.

[Rainman]

There's a 1/4 probability that both numbers are even. If they are not both even, there is still a 1/9 probability that they are both divisible by 3. Perhaps the key feature here is realizing that divisibility by one prime is independent of divisibility by other primes. Anyway, this yields a probability of 1/4+3/4*1/9 = 3/12+1/12 = 1/3 that 2 or 3 is a common prime factor. As there are more possible common prime factors, the probability of winning the bet is >1/3. So I'd take the bet.

[gavinksong]

Where did the bin come from?

 

Suspecting that bonanza was trying swindle me out of my money, I would refuse the bet.

[BMAD]

yeah I believe it is actually 6/pi².  

[Rainman]

Most of you got it.

BMAD made a close estimate of the probability, which is actually just slightly greater than 60% to be co-prime.

I'm marking her answer, therefore.

This time the skeptics missed a chance to win some coin.

 

Edit: Since the coprime probability is so close to 60% (slightly larger) I pondered making the odds 3:2,

forcing a calculation in order to be sure. It's not a simple calculation.

But I decided to be nice.

 

 

yeah I believe it is actually 6/pi².  

 

How do you arrive at this answer? If I'm not mistaken, the answer is approximated by running the following program indefinitely, given a full list of primes in order P₁ = 2, P₂ = 3, P₃ = 5, and so on:

 

1: set S = 0, i = 1

2: set S = S + (1-S)/P_i²

3: set i = i+1

4: return to step 2

 

As this program keeps going, S should tend to the desired probability. Not being a programmer, I haven't been able to run this for large numbers, but it seems to me that it would converge closer to 0.4 than 0.6. I would be very surprised if it converged at exactly 6/pi², as this would indicate a clear correlation between pi and the set of primes.

[phil1882]

the equation

1/1^2 +1/2^2 +1/3^2 ... is well known to be pi^2/6, and is equivalent to 1/(1-1/2^2) *1/(1-1/3^2) *1/(1-1/5^2) ...

[phil1882]

if you really wanna see something bizarre, the Riemann zeta function tells us that the sequence 1 +2 +3 +4 +5 .... = -1/12.

[Quantum.Mechanic]

Most of you got it.

BMAD made a close estimate of the probability, which is actually just slightly greater than 60% to be co-prime.

I'm marking her answer, therefore.

 

Just for fun, I programmed up a little script. Using a suitable underlying GMP library for Euler's totient function, it checked up to 10 million in 13 seconds, with a result of 60.793% distinct pairs relatively prime.

[bonanova]

Most of you got it.

BMAD made a close estimate of the probability, which is actually just slightly greater than 60% to be co-prime.

I'm marking her answer, therefore.

 

Just for fun, I programmed up a little script. Using a suitable underlying GMP library for Euler's totient function, it checked up to 10 million in 13 seconds, with a result of 60.793% distinct pairs relatively prime.

That checks with 6/pi² = 0.607927101854.....

[BMAD]

Suppose you pick two random numbers less than n, then 

• [n/2]² pairs are both divisible by 2. 
• [n/3]² pairs are both divisible by 3. 
• [n/5]² pairs are both divisible by 5. 
• ... 

(Here [x] is the greatest integer less than or equal to x, usually called the floor function.) So the number of relatively prime pairs less than or equal to n is (by the inclusion/exclusion principle): 

 

n ² - sum([n/p]²) + sum([n/pq]²) - sum([n/pqr]²) + ... 

 

here the sums are taken over the primes p,q,r,... less than n. Letting mu(x) be the möbius function this is 

so the desired constant is the limit as n goes to infinity of this sum divided by n², or sum(mu(k)/k²)    

 

(sum over positive integers k). 
 

But this series times the sum of the reciprocals of the squares is one, so the sum of this series, the desired limit, is 6/². This number is approximately sum(mu(k)[n/k]²)    

 

(sum over positive integers k) 

 

60.7927...%

Edited May 11, 2015 by BMAD

[bonanova]

Most of you got it.
BMAD made a close estimate of the probability, which is actually just slightly greater than 60% to be co-prime.
I'm marking her answer, therefore.

This time the skeptics missed a chance to win some coin.

 

Edit: Since the coprime probability is so close to 60% (slightly larger) I pondered making the odds 3:2,

forcing a calculation in order to be sure. It's not a simple calculation.

But I decided to be nice.

Edited May 1, 2015 by bonanova