There is a simple way

Number Theory Level 4

What is the value of the sum below?

$\sum_{p \text{ prime}} \frac{1}{p} \underset{q < p}{\prod_{ q \text{ prime}}} \frac{q-1}{q}$

Clarification: When no $q$ satisfies the conditions in the product, i.e. when $p = 2$ , suppose the product is $1$

Maybe try this next: Is there a simple way?

The answer is 1.

2 solutions

Mark Hennings
Aug 15, 2019

By a similar argument (again, all sums and products are over the primes) to that used in the later question , although we need a little care to handle the convergence, we have $\sum_p \frac{1}{p} \prod_{q<p} \frac{q-1}{q} \; = \; 1 - \prod_p\left(1 - \frac{1}{p}\right)$ Since $\sum_p p^{-1}$ diverges, standard infinite product theory tells us that $\prod_p \big(1 - p^{-1}\big) = 0$ , This means that the answer is $\boxed{1}$ .

Pedro Cardoso
Aug 15, 2019

Suppose you're looking at the set of all natural numbers. The probability of picking a multiple of $2$ is $\frac{1}{2}$ . The probability of picking a multiple of $2$ or a multiple of $3$ is equal to the probability of picking a multiple of $2$ plus the probability of picking a pultiple of $3$ that isn't also a multiple of $2$ . And that is

$\frac{1}{2} + \frac{1}{3}\left( 1 - \frac{1}{2} \right)$

This means the probability of picking a multiple of $2$ or $3$ or $5$ or $7$ and so on, for every prime is:

$\frac{1}{2} + \frac{1}{3}\left( 1 - \frac{1}{2} \right) + \frac{1}{5}\left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) + \frac{1}{7}\left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \left( 1 - \frac{1}{5} \right) + ...$

But this is equal to the sum in the problem, always adding the probability that you pick a number multiple of some prime, that isn't also a multiple of any of the primes you have added before.

And that is the same as the probability of picking any number, which is equal to $\boxed{1}$

I get the idea but, strictly speaking, we cannot have a uniform distribution on an infinite set. If you want to use a probabilistic approach, you need to do something a little different.

You could define a distribution on the prime numbers. Start at 1 and walk to the right. When you reach a prime number p, stop there with probability (1/p). Then your expansion above would simply be the sum of the point probabilities for each prime. The soundness of each individual probability would imply that the sum would have to equal 1.

More rigor might be needed. But at least it's a start.

Richard Desper - 1 year, 10 months ago

Thinking some more, I think defining the probability with a walk to the right to solve this problem might require circular reasoning: This depends on saying that you will always eventually stop, and I think there could be a chance you never stop at all. For example, say you start at 1 and walk to the right, and everytime you reach a natural number $n$ , you stop with probability $\frac{1}{10^n}$ doesn't this mean the probability that you stop at all is less than the sum below? $\sum_{n = 1}^{\infty} \frac{1}{10^n} = \frac{1}{9}$ If this is the case, the walk to the right only guarantees the sum is $\leq 1$ .

Pedro Cardoso - 1 year, 10 months ago

I'll repost this since I accidentally replied to my own solution:

I see. That is a very clever way of looking at it. The idea of probability of picking a multiple of a prime $p$ I was thinking about is $P(p) = \lim_{n \rightarrow \infty } \frac{\text{\# of multiples of } p \text{ less than } n}{n}$ I think this definition works fine, but I agree that more rigor is needed, to show that the probability of picking a multiple of a prime $p$ that isn't a multiple of another prime $q$ is $P(p)(1-P(q))$ , for example.

Pedro Cardoso - 1 year, 10 months ago

You could also treat the sum as the following. What is the probability that for a random positive integer, it is divisible by some prime (1/p) though it is not divisible by any prime less that such prime(the product of (q-1)/q for all q less than p? This would obviously be 1 as every number has a smallest prime in its prime factorization. Same thing with the second problem. What is the probability that a random positive integer is divisible by a square of a prime(1/p^2) and not divisible by the square of any prime less than such prime(again its the product of (q^2-1)/q for all q less than p)? This time, our statement can be rewritten as "What is the probability that a random number is divisible by the square of any prime". The odds of choosing a number that is NOT divisible by the square of any prime is just (1-1/p^2) for all p prime. This just boils down into 6/(pi^2) and the answer would be 1-6/(pi^2) via complementary counting.

Razzi Masroor - 1 year, 4 months ago

There is a simple way

The answer is 1.

2 solutions

0 pending reports