BrainDen.com - Brain Teasers
• 0

# Relatively prime

## Question

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?

## Recommended Posts

• 0

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.

##### Share on other sites

• 0

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!

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

100% loss

if the bin contains even numbers starting at 4

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

Two numbers are relatively prime iff their GCF is 1.

{6, 7} are relatively prime.

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

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

Where did the bin come from?

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

##### Share on other sites

• 0

yeah I believe it is actually 6/pi2.

##### Share on other sites

• 0

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.

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/pi2.

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 P1 = 2, P2 = 3, P3 = 5, and so on:

1: set S = 0, i = 1

2: set S = S + (1-S)/Pi2

3: set i = i+1

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/pi2, as this would indicate a clear correlation between pi and the set of primes.

##### Share on other sites

• 0

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) ...

##### Share on other sites

• 0

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

##### Share on other sites

• 0

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.

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.

##### Share on other sites

• 0

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.

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/pi2 = 0.607927101854.....

##### Share on other sites

• 0

Suppose you pick two random numbers less than n, then

• [n/2]2 pairs are both divisible by 2.
• [n/3]2 pairs are both divisible by 3.
• [n/5]2 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):

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

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 n2, or sum(mu(k)/k2)

(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/2. This number is approximately sum(mu(k)[n/k]2)

(sum over positive integers k

60.7927...%

##### Share on other sites

• -1

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.

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 by bonanova

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.