8

I am seeking a simple way to solve the following problem. It is an easy problem, but I don't like the way I solve the problem. I listed two sets of numbers and counted one by one first and then find the probability. It works for this problem. But if the problem changes a little, such as change 9 to 1000, my method will not work.

Two different integers are randomly selected from the set of integers greater than 2 and less than 9. What is the probability that they have no common prime factor?

learning
  • 1,749
  • Euler's totient function might be useful here (not sure as I'm only vaguely familiar with this function). – Jared Jun 15 '16 at 19:00
  • 2
    According to a theorem by Dirichlet, two arbitrary integers are relatively prime with probability $6/\pi^2$ (the reciprocal of the sum of the reciprocals of squared integers); but I don't see how to make that relevant to a bounded set of integers. – Anton Sherwood Jun 21 '16 at 23:39
  • You could list all the squarefree numbers up to 500 and then find the number of pairs that have each as a common factor and then use the principle of inclusion and exclusion; alternatively you could list just the primes and for each prime in order find the number of numbers that have that prime as a common factor but none of the previous primes using recursion, which does the same number of calculations (I think) but with smaller numbers – alphacapture Jun 22 '16 at 01:07
  • The event "both have no common prime factor" is equivalent to the event "both have no common factor" because if they have a common non-prime factor, they also have a common prime factor too because the non-prime factor can be obviously decomposed in the product of prime factors. So is this what you're asking for? Or you're asking the probability that they are relatively prime? – user52227 Mar 15 '17 at 12:17

1 Answers1

1

There's no exact formula for this, at least not any simple one.

However, we might be able reduce the casework slightly. Let's consider the numbers on the closed interval [4,30]. (That is, inclusive of 4 and 30).

Clearly, if 2 numbers have a common prime factor, they will both be divisible by 2,3,5,7,11,13,17,19,23,or 29. We can break this down and find all combinations pretty quickly now.

29 - 1 combination (29-29)

23 - 1 combination (23-23)

19 - 1 combination (19-19)

17 - 1 combination (17-17)

13 - 4 combinations (13-13),(13-26),(26-13),(26-26)

11 - 4 combinations (11-11),(11-22),(22-11),(22-22)

7 - 16 combinations (7-7),(7-14),(7-21),(7-28),

(14-7),(14-14),(14-21),(14-28),

(21-7),(21-14),(21-21),(21-28)

(28-7),(28-14),(28-21),(28-28)

You may have noticed that, in general, the number of combinations is (floor(30/num))^2, or 30/num rounded down, and then squared.

Consider when the number is 7. In this case, there are 4 numbers to be concerned about - every multiple of seven below 30. Hence the floor(30/num) part of the formula. Then we square it because we choose a number from this set twice.

With this formula we can continue down.

5 is found to have 6^2 = 36 pairs.

3 is a bit different because there is a minimum boundary we have set of 4. However, there is no need to panic. We notice that the numbers we have to choose from are 3,6,9,12,15... so we can just use the formula from before, ignoring the 3 this time. That is, as the formula would have given us those 10 numbers before, subtracting the 3, we will only have 9 numbers to consider, and 81 possible pairs.

We can update our formula to include the minimum boundary: (floor(30/num)-floor(4/num))^2

Finally we end with 2, which has (15-2)^2 = 169 possible pairs.

Adding up these pairs, we get 169+81+36+16+4+4+1+1+1+1 = 314 pairs. [This number is coincidentally pi - ish, so it seems like a good time to sneak in the fact that two numbers from 1 to infinity have a 6/(π^2) chance to be coprime (have no common prime factor).]

Anyways, since we know that there are a total of (30-4+1) = 27 numbers on the interval [5,30], we know there are 27^2 = 729 numbers to choose from and the chance that any 2 numbers have a common prime factor is 314/729. Similarly, the chance that they don't is 1-314/729=415/729.

Let's use this on your problem: We're looking for the numbers between [3,8].

(floor(8/num)-floor(3/num))^2 when num = 2,3,5,7

7:(1-0)^2=1

5:(1-0)^2=1

3:(2-0)^2=4

2:(4-1)^2=9

(1+1+4+9)/((8-3+1)^2) = 5/12

1-5/12 = 7/12, which should be the answer.

Alex Li
  • 538