# $\pi(n)$ is always more than the sum of the prime indices of the factors of composite $n \geq 12$

Let $$n=p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \geq 12$$ be any composite integer.

Then it seems that this is true: $$\pi(n) > \sum_{i=1}^{k}{\pi(p_i)a_i}\ .$$

You get equality instead iff $$n$$ is prime.

I also assume that if it is true, it's a known result. Can anyone point me towards a resource discussing it if so? Alternatively, if I've made a mistake and/or this is a trivial result, please point out how.

Also, if true, I think Bertrand's Postulate immediately follows:

For prime $$p$$, it gives $$\pi(2p)>\pi(p)+1$$, implying at least one prime between $$p$$ and $$2p$$.

By the same token, $$\pi(3p)>\pi(p)+2$$, and $$\pi(p^2)>2 \pi(p)$$.

• The strict inequality is not true. For example, $\pi(6) = 3 = \pi(2) + \pi(3)$. Jul 28 '20 at 2:20
• What is $\pi(n)$? Jul 28 '20 at 2:21
• @AndréPorto The prime counting function – this is standard notation in number theory. Jul 28 '20 at 2:23
• The proposition seems reasonable in that for sufficiently large $p_i$, $p_i>\pi(p_i)$, so $p_i^{\alpha_i}>\pi(p_i)\alpha_i$ and products grow faster than sums. Jul 28 '20 at 2:29
• I just checked this by computer for $n \leq 10^5$. @KeithBackman is this enough for your argument to finish it off? Jul 28 '20 at 2:35

Suppose $$km=n$$ with $$6\le k\le m$$. A result of Rosser–Schoenfeld says that $$\pi(x) < 1.25506x/\log x$$ for $$x>1$$, so $$\pi(k)+\pi(m) \le 2\pi(m) < 2.51012m/\log m < 5.02024m/\log n,$$ since $$m\ge\sqrt n$$. On the other hand, another result of Rosser–Schoenfeld says that $$\pi(x) > x/\log x$$ for $$x>17$$. The fact that $$n\ge17$$ and $$k\ge6$$ now forces $$\pi(n) > n/\log n = km>\log n > 5.02024m/\log n > \pi(k)+\pi(m).$$ On the other hand, a result of Ramanujan says that $$\pi(2x) \ge \pi(x) + 2$$ and $$\pi(3x) \ge \pi(x) + 3$$ when $$x\ge6$$. Therefore when $$m\ge6$$, \begin{align*} \pi(2m) &> \pi(m) + 1 = \pi(m) + \pi(2) \\ \pi(4m) \ge \pi(3m) &> \pi(m) + 2 = \pi(2m) + \pi(3) \\ \pi(5m) &\ge \pi(4m) \ge \pi(2m)+2 > (\pi(m)+1)+2 = \pi(m) + \pi(5). \end{align*}

In other words, we have shown that $$\pi(k) + \pi(m) < \pi(km)$$ for $$k\ge2$$ and $$m\ge6$$.

This should be very close to proving the entire statement by induction on the number of prime factors (counting multiplicity).

As shorthand, let $$\sum_\pi(n)$$ denote the sum of prime indices of $$n$$ as described above.

For any $$k$$, we know $$\pi(p_k)=\sum_\pi(p_k)=k$$.

From Bertrand's postulate, we know that $$\pi(2^k) \geq \sum_\pi(2^k)=k$$.

Any intermediate $$n$$ such that $$\sum_\pi(n)=k$$ will fall in the range $$(p_k,2^k)$$ and thus have $$\pi(n) \geq k$$. This can be shown explicitly by starting with $$2^k$$ and repeatedly dividing by $$2$$ while increasing another factor to its next larger prime. Bertrand ensures that the next larger prime will always be less than the factor of $$2$$ we lost, and so the overall product must also decrease.

e.g. $$(1,1,1,1,1)\rightarrow (2,1,1,1)\rightarrow (2,2,1)\rightarrow (3,2)$$, using integer partition tuples to represent the products $$2^5=32$$, $$3\cdot 2^3=24$$, $$3^2\cdot 2=18$$, $$5\cdot 3=15$$, and the minimum we could have gone to here is $$(5)=p_5=11$$.

Thus we see that any $$n$$ where $$\sum_\pi(n)=k$$ must be in the range $$p_k \leq n \leq 2^k$$, and since $$\pi$$ is a monotonically increasing function, we know that any such intermediate $$n$$ will give $$\pi(p_k) \leq \pi(n) \leq \pi(2^k)$$. And again, since $$\sum_\pi(p_k)=k$$, any $$n>p_k$$ will have $$\pi(n)\geq k$$.

This should suffice to prove $$\pi(n) \geq \sum_\pi(n)$$ for all $$n\in\mathbb N$$, or equivalently, that $$\pi(ab)\geq \pi(a)+\pi(b)$$.

To get the bounded inequality given in the problem, I think it's a matter of how many special cases you want to address; the larger the lower bound for $$n$$, the larger the constant you can reliably add to the right side of this, i.e. for $$n\geq 12$$, you can use $$\pi(n) \geq \sum_\pi(n)+1$$. In other words, for any $$c$$, there's some $$N$$ such that for all $$n \geq N$$, you get $$\pi(n) \geq \sum_\pi(n)+c$$.

• I do see a problem here in that I'm not sure I've really proven that e.g. $p_5 < p_3 p_2$, since you can't make a direct monotonic path between them, which is all we can guarantee usefully with Bertrand. Jul 30 '20 at 8:53