I did some math: average prime powers among counting numbers

In the past few days, I’ve seen a couple of good little math problems posted on Twitter. I follow a number of mathematicians, including James Tanton (@jamestanton), who pretty regularly posts math problems that are sometimes easy enough that I have a fair chance of solving them (though he almost never provides any solutions, so it’s sometimes hard to tell if I’ve gotten it right). A couple of days ago, he asked a simple question:

What is the average power of a given prime p among the prime factorizations of the counting numbers?

— James Tanton (@jamestanton) April 26, 2017

This is not a terribly difficult problem to solve as long as you can sum a particular doubly-infinite series, but summing that series is probably the most interesting part of the problem.

I’d like to think I could have figured it out on my own, but I’ll never know, because before I tried to solve the problem, I watched the discussion another mathematician had with his two sons about the problem during their family math night. I love the idea of having family math night discussions, and I am particularly impressed with his children’s willingness to give some real thought to tackling this problem. His sons can’t be very old (they don’t look old enough to me to be in high school yet), and yet one of them immediately had the critical insight of how to sum the series. I have a feeling that without his suggestion, I might have struggled for awhile before coming up with the solution myself.

The question asks for the “average” power of a given prime p among the counting numbers. A prime p is a factor in every pth counting number—which means that it is not a factor in $\frac{\left(p-1\right)}{p}$ of the counting numbers, in which the power of p is 0 (there's a subtlety here about measuring proportions of the infinite set of counting numbers, but think of looking at the proportion of the first n counting numbers that have a factor p, then taking the limit as n approaches infinity). Of the 1/p counting numbers that have p as a factor, you can divide by p and recover the counting numbers. So $\frac{\left(p-1\right)}{p}$ of these numbers have no further p factors, and $\frac{\left(p-1\right)}{p}·\frac{1}{p}$ of the counting numbers have a power of p equal to 1. Divide the remaining numbers again by p, and the argument continues: $\frac{\left(p-1\right)}{p}·\frac{1}{p^2}$ of the counting numbers have a power of p equal to 2, $\frac{\left(p-1\right)}{p}·\frac{1}{p^3}$ have a power of p equal to 3, and $\frac{\left(p-1\right)}{p}·\frac{1}{p^n}$ have a power of p equal to n. Muliplying the proportions by all of the possible powers (all of the counting numbers) yields the average power of p among all of the counting numbers:

$$\text{Average power of}p=\frac{\left(p-1\right)}{p}\sum _{n=1}^{\infty }\left(n·\frac{1}{p^n}\right)$$

It’s easy enough to sum just the geometric series $\frac{1}{p^n}$ , but in this series, the terms are scaled by n: so there is one term $\frac{1}{p}$ , two $\frac{1}{p^2}$ terms, three $\frac{1}{p^3}$ terms, etc. The challenge is to see that this means there are an infinite number of ordinary geometric sequences: one that starts with $\frac{1}{p}$ , then another starting at $\frac{1}{p^2}$ , and another starting at $\frac{1}{p^3}$ , and so on. In the third video on the family-math-night page linked above, the older son comes up with a brilliant way of seeing this structure—by re-writing the series with each power on its own line, and then grouping terms vertically:

$$\sum _{n=1}^{\infty }\left(n·\frac{1}{p^n}\right)=\frac{1}{p}+2·\frac{1}{p^2}+3·\frac{1}{p^3}+4·\frac{1}{p^4}+···$$

$$\begin{array}{cccc}=\frac{1}{p}& & & \\ +\frac{1}{p^2}& +\frac{1}{p^2}& & \\ +\frac{1}{p^3}& +\frac{1}{p^3}& +\frac{1}{p^3}& \\ +\frac{1}{p^4}& +\frac{1}{p^4}& +\frac{1}{p^4}& +\frac{1}{p^4}+···\end{array}$$

$$=\left(\begin{array}{c}\frac{1}{p}\\ +\frac{1}{p^2}\\ +\frac{1}{p^3}\\ +\frac{1}{p^4}\\ +···\end{array}\right)+\left(\begin{array}{c}\\ \frac{1}{p^2}\\ +\frac{1}{p^3}\\ +\frac{1}{p^4}\\ +···\end{array}\right)+\left(\begin{array}{c}\\ \\ \frac{1}{p^3}\\ +\frac{1}{p^4}\\ +···\end{array}\right)+\left(\begin{array}{c}\\ \\ \\ \frac{1}{p^4}\\ +···\end{array}\right)+···$$

This kind of insight is beautiful—and it is, at bottom, why I enjoy working through math problems. Most of the time I just struggle, but every now and then, my brain reorients and I find the blade to cut through the Gordian knot. It’s a wonderful feeling.

So (ignoring for a moment the $\frac{\left(p-1\right)}{p}$ factor in front of the summation) we have a series of series: the first, which starts with $\frac{1}{p}$ , sums to $\frac{1}{\left(p-1\right)}$ . The second is the same series as the first, with all of the terms multiplied by $\frac{1}{p}$ . The third is the same as the first multiplied by $\frac{1}{p^2}$ . The fourth is the first multiplied by $\frac{1}{p^3}$ , etc. So the series of geometric series sums to… a geometric series:

$$\frac{1}{\left(p-1\right)}\sum _{n=0}^{\infty }\frac{1}{p^n}$$

… with the sum taken over the whole numbers n (starting with 0, because the first term is 1, once the $\frac{1}{\left(p-1\right)}$ is factored out), which is equal to $\frac{p}{{\left(p-1\right)}^2}$ . But we previously had a factor of $\frac{\left(p-1\right)}{p}$ that we ignored. Putting that back in, we have:

$$\text{Average power of}p=\frac{\left(p-1\right)}{p}·\frac{p}{{\left(p-1\right)}^2}=\frac{1}{\left(p-1\right)}$$

This is a nice little result in itself: among the counting numbers, larger primes occur less frequently, of course, but they appear regularly—and one expects each to have, on average, a factor of $p^{\frac{1}{\left(p-1\right)}}$ in any given counting number. A few days after posting this question, though, Tanton asked a follow-up question:

From yesterday, 2^(1)*3^(1/2)*5^(1/4)*7^(1/6)*11^(1/10)*13^(1/12)*... is the most average prime factorization. Is this number finite or inf?

— James Tanton (@jamestanton) April 27, 2017

Consider the product of $p^{\frac{1}{\left(p-1\right)}}$ over all of the primes—that is, construct the number that has the “average” power of every prime. Is this construction finite or infinite?

$$P=\prod _{p\in \text{primes}}\left(p^{\frac{1}{\left(p-1\right)}}\right)\text{. Is}P\text{finite or infinite?}$$

The answer should be obvious—the “average” counting number had better not be finite—but the fun is in proving it, and in this case, the solution may depend on a rather interesting result of Euler (as so many problems often do). But this result of Euler’s is interesting in part because his “proof” was rather questionable. To add to the intrigue, Paul Erdős also gave a separate proof of the same result.

Here’s how I approached the problem. I don’t like dealing with infinite products—the way my brain is wired, I find it much easier to deal with sums (though I imagine many real mathematicians wouldn’t trouble themselves much about the difference). So I took the logarithm of the product:

$$\ln \left(P\right)=\sum _{p\in \text{primes}}\left(\frac{1}{\left(p-1\right)}·\ln \left(p\right)\right)$$

I don’t like logarithms much, either, so I want get rid of them if possible. Because I think the product is infinite, I’m going to get rid of ln(p) by considering a lower bound. For all primes p > 2, ln(p) > ln(2), so:

$$\ln \left(P\right)=\sum _{p\in \text{primes}}\left(\frac{1}{\left(p-1\right)}·\ln \left(p\right)\right)>\sum _{p\in \text{primes}}\left(\frac{1}{\left(p-1\right)}·\ln \left(2\right)\right)$$

$$=\ln \left(2\right)\sum _{p\in \text{primes}}\frac{1}{\left(p-1\right)}>\ln \left(2\right)\sum _{p\in \text{primes}}\frac{1}{p}$$

If the right-hand side is infinite, then so is the left-hand side. The question is whether the sum of the reciprocals of the primes diverges. I know that the harmonic series diverges (slowly!), but the prime reciprocals is a rather sparse subsequence of the harmonics. If it diverges, it must do so incredibly slowly. But diverge it does, so the product considered above is infinite.

According to Wikipedia, Euler gave a questionable proof that the sum of the prime reciprocals does, in fact, diverge. But I like Erdős’s proof by contradiction given on the same page, which considers the number of counting numbers less than or equal to x that are products of the first k primes. Erdős forms both lower and upper bounds, and shows that if the sum of prime reciprocals converges those two bounds contradict each other. It is not a difficult proof to follow, but it is hardly an obvious proof—there is real brilliance in the set-up, and I could never have come up with it myself.

Working through problems like these really makes me want to attend the math camp for adults that Tanton posted about on Friday:

Math Camp for adults! https://t.co/tjmwuhfGZD Woohoo!

— James Tanton (@jamestanton) April 29, 2017

I probably can’t make it, since I don’t have much vacation at work, but I sure wish I could!