bonanova 84 Report post Posted April 27, 2015 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? Quote Share this post Link to post Share on other sites
0 BMAD 64 Report post Posted April 28, 2015 (edited) 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 Quote Share this post Link to post Share on other sites
0 dgreening 5 Report post Posted April 28, 2015 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. Iffor 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! Quote Share this post Link to post Share on other sites
0 Pickett 13 Report post Posted April 28, 2015 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. Quote Share this post Link to post Share on other sites
0 harey 8 Report post Posted April 28, 2015 100% loss if the bin contains even numbers starting at 4 Quote Share this post Link to post Share on other sites
0 phil1882 13 Report post Posted April 28, 2015 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. Quote Share this post Link to post Share on other sites
0 bonanova 84 Report post Posted April 28, 2015 Two numbers are relatively prime iff their GCF is 1. {6, 7} are relatively prime. {6, 8}, {6, 9} and {6, 10} are not. Quote Share this post Link to post Share on other sites
0 Rainman 14 Report post Posted April 29, 2015 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. Quote Share this post Link to post Share on other sites
0 gavinksong 11 Report post Posted April 29, 2015 Where did the bin come from? Suspecting that bonanza was trying swindle me out of my money, I would refuse the bet. Quote Share this post Link to post Share on other sites
0 BMAD 64 Report post Posted May 1, 2015 yeah I believe it is actually 6/pi^{2}. 1 Quote Share this post Link to post Share on other sites
0 Rainman 14 Report post Posted May 2, 2015 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^{2}. 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_{1} = 2, P_{2} = 3, P_{3} = 5, and so on: 1: set S = 0, i = 1 2: set S = S + (1-S)/P_{i}^{2} 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^{2}, as this would indicate a clear correlation between pi and the set of primes. Quote Share this post Link to post Share on other sites
0 phil1882 13 Report post Posted May 3, 2015 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) ... Quote Share this post Link to post Share on other sites
0 phil1882 13 Report post Posted May 3, 2015 if you really wanna see something bizarre, the Riemann zeta function tells us that the sequence 1 +2 +3 +4 +5 .... = -1/12. Quote Share this post Link to post Share on other sites
0 Quantum.Mechanic 0 Report post Posted May 5, 2015 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. Quote Share this post Link to post Share on other sites
0 bonanova 84 Report post Posted May 7, 2015 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^{2} = 0.607927101854..... Quote Share this post Link to post Share on other sites
0 BMAD 64 Report post Posted May 11, 2015 (edited) 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): n ^{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 n^{2}, or sum(mu(k)/k^{2}) (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...% Edited May 11, 2015 by BMAD 1 Quote Share this post Link to post Share on other sites
-1 bonanova 84 Report post Posted May 1, 2015 (edited) 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 Quote Share this post Link to post Share on other sites
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