Conjecture: $\pi(x)\ge \pi\circ\pi(x)+\pi\circ\pi\circ\pi(x)+\cdots$

Solution 1:

Certainly $\pi(x) \le (2/3)x$ for all $x$, so the right-hand side satisfies $$ \pi(\pi(x)) + \pi(\pi(\pi(x))) + \pi(\pi(\pi(\pi(x)))) + \ldots \le \pi(\pi(x))\left(1+\frac{2}{3}+\frac{4}{9}+\ldots\right)=3\pi(\pi(x)). $$ Using the inequality $\pi(x) < 1.25506 (x / \ln x)$, then, we have $$ 3\pi(\pi(x))\le(1.25506\cdot 3 / \ln(\pi(x)))\pi(x) < \pi(x) $$ provided that $\ln(\pi(x)) > 3.76518$, or $\pi(x)\ge44$, or $x \ge p_{44}=191$. And a direct numerical check shows your inequality holds for $13\le x<191$.

Solution 2:

Actually, something more general can be proven:

$$n \geq \pi(n) + \pi(\pi(n))+ \pi(\pi(\pi(n))) + \cdots$$

First, note that $\pi(n) \leq \frac23n$ for all $n$. Also, note that $\pi(n) \leq \frac13n$ for $n \geq 35$.

Proof. $\pi(n) \leq \frac12n+1$ for all $n$ follows from the fact that two is the only even prime. This is smaller than $\frac23n$ for all $n\geq 6$. It can be checked manually for $n=1,2,3,4,5$.

For the second inequality, note that every prime not equal to $2,3$ is congruent to $1$ or $-1$ modulo $6$. Now note that $1, 25$ and $35$ do have this form, but are not prime. From this, we also have $\pi(n) \leq \frac13n$ for $n \geq 35$.

Now the main proof:

Let $f^k$ denote function iteration. We have for $n\geq35$ that $$\pi^k(n) = \pi^{k-1}(\pi(n)) \leq \pi^{k-1}\left(\frac13n\right) \leq \left(\frac23\right)^{k-1}\cdot \left(\frac13n\right)$$

Hence we have the inequality $$\sum_{i=1}^{\infty} \pi^i(n) \leq \sum_{i=1}^{\infty} \frac13\left(\frac23\right)^{i-1}n = \frac13n \sum_{i=1}^{\infty} \left(\frac23\right)^{i-1} = \frac13n \cdot \frac1{1-\frac23}=n$$

Now, substituting $n=\pi(x)$ gives the desired result for $x \geq 149$.

Another user already showed this for $13\leq x \leq 2000$, so this gives the result.