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

Question

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)$.

---

(See my answer below for additional thoughts.)

Answer 1

Not quite complete answer:

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).

Answer 2

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$.