Jump to content
BrainDen.com - Brain Teasers
  • 0
bonanova

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?

Share this post


Link to post
Share on other sites

16 answers to this question

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.

Edited by BMAD

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

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. :P

 

 

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

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

Share this post


Link to post
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 this post


Link to post
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.

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.

Share this post


Link to post
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.

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

Share this post


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

 

(sum over positive integers k

 

60.7927...%

Edited by BMAD
  • Upvote 1

Share this post


Link to post
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.
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. :P

Edited by bonanova

Share this post


Link to post
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...