Litt Puzzle 3

Framing

A useful concept in thinking about this puzzle is the idea of two numbers being relatively prime (or coprime). The numbers \(p\) and \(q\) (where \(p,\ q \in \mathbb{N}\)) are said to be relatively prime iff \(\text{gcd}(p,\ q) = 1\). In other words, if they do not have a prime factor in common! We will denote this by \(p \perp q\).

An equivalent question to the one posed in this puzzle is the following.

What are the odds of two random numbers between \(1\) and \(10^{1000000}\) being relatively prime?

Observations

Consider just one number. The odds of one number being divisible by 1 are 1/1 (every number is divisible by 1). The odds of a number being divisible by 2 are 1/2 (every other number is divisible by 2). The odds of a number being divisible by 3 are 1/3 (every third number is divisible by 3). Are you starting to see the pattern?

Since we are interested in divisors, we only need to consider primes to look at every possible factor which could be shared (e.g., 6 is covered by the probability of being divisible by 2 and the probability of being divisible by 3).

Probabilities

Let \(a\) be the number Alice draws and \(b\) be the number Bob draws. Then using the above observations what are the odds that both Alice and Bob draw a number which is divisible by 2? \[ \text{P}(a\ |\ 2,\ b\ |\ 2) = \text{P}(a\ |\ 2)\cdot\text{P}(b\ |\ 2) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4} \] Where \(\text{P}(a\ |\ 2,\ b\ |\ 2)\) denotes the probability that both \(a\) and \(b\) are divisible by 2. So to get the overall probability that \(a\) and \(b\) share a common factor we get an infinite series. \[ \begin{align} \text{P}(a \perp b) &= \sum_{p\ \in\ \text{primes}} \text{P}(a\ |\ p,\ b\ |\ p) \\ &= \sum_{p\ \in\ \text{primes}} \text{P}(a\ |\ p) \cdot \text{P}(b\ |\ p) \\ &= \sum_{p\ \in\ \text{primes}} \frac{1}{p^2} \\ &= \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{5^2} + \frac{1}{7^2} + \cdots \end{align} \] If this looks familiar it might be because this is a special case of the famed prime zeta function, \(P(s)\) where \(s = 2\). There's even a sequence on the OEIS for it! It does not have an analytic solution, but computing the first five terms gets \(\approx 0.43\). Looking at Wikipedia we can find it is known that \(P(2) \approx 0.452\). Alternately, we could crib this result from Euler who ran into this same sequence all the way back in 1748 (!!!) and wrote about it in his Introductio in Analysin Infinitorum (see pg. 480).

What this value tells us is that the odds of two random numbers sharing a common factor are ~45%. This means that ~45% of the time Alice will win, while ~55% Bob will win. Thus, Bob is more likely to win.

\[\boxed{\text{Bob is more likely to win }}\]