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

  • 1
    $\begingroup$ The strict inequality is not true. For example, $\pi(6) = 3 = \pi(2) + \pi(3)$. $\endgroup$ Jul 28 '20 at 2:20
  • 1
    $\begingroup$ What is $\pi(n)$? $\endgroup$ Jul 28 '20 at 2:21
  • 2
    $\begingroup$ @AndréPorto The prime counting function – this is standard notation in number theory. $\endgroup$ Jul 28 '20 at 2:23
  • 3
    $\begingroup$ 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. $\endgroup$ Jul 28 '20 at 2:29
  • 1
    $\begingroup$ I just checked this by computer for $n \leq 10^5$. @KeithBackman is this enough for your argument to finish it off? $\endgroup$ Jul 28 '20 at 2:35

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


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

  • $\begingroup$ 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. $\endgroup$
    – Trevor
    Jul 30 '20 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.