# order of primality of an integer

Hello,

let's define the notion of order of primality in such a way: $n$ is a prime of order $k$ if and only if $k$ is the smallest non negative integer such that $\pi^{(k)}(n)$ is not a prime number, where $\pi^{(0)}(n)=n$ and for all $m$, $\pi^{(m+1)}(n)=\pi(\pi^{(m)}(n))$. Now let's write $\pi_{k}(x)$ for the number of primes of order $k$ not exceeding $x$. It is quite easy to see that every non negative integer $n$ verifies the equality $n=\displaystyle{\sum_{k\geq 0}\pi_{k}(n)}$ and that $\pi(n)=n-\pi_{0}(n)$. Moreover, for all $(k,n)\in\mathbb{N}^{2}$, $\pi_{k+1}(n)\leq\pi_{k}(n)$.

My question is: is there a function $f$ such that for all $(k,n)\in\mathbb{N}^{2}$, $\pi_{k+1}(n)=f(\pi_{k}(n))+O(1)$?

-
In fact, it seems that for all $m\leq k$, $\pi_{k-m}(\pi^{m}(n))=\pi_{k}(n)$. Could someone prove this rigorously? – Sylvain JULIEN Mar 18 '11 at 17:22
This is Sloane's A078442/A049076. – Charles Mar 19 '11 at 4:42

I think your argument may be generalized to any order. If $m \in \mathbb{N}$, then $\pi^{(m)}(x)$ is the number of primes of order $\ge k$ not exceeding $x$. That is

$$\pi^{(m)}(x) = \sum_{k \ge m} \pi_k(x)$$

And we get

$$\pi_m(x) = \pi^{(m)}(x) - \pi^{(m+1)}(x)$$

Thus for $n \in \mathbb{N}$, we get

$$\pi_m(\pi^{(n)}(x)) = \pi^{(m)}(\pi^{(n)}(x)) - \pi^{(m+1)}(\pi^{(n)}(x)) = \pi^{(m+n)}(x) - \pi^{(m+n+1)}(x) = \pi_{m+n}(x)$$

-
I don't see that this uses any special properties of primes. You could ask the same questions (which might be interesting) for any increasing integer sequence such as multiples of 3 or third powers or $3^n$. The growth rates here should be similar to the sequence $n{\ln n}$ rounded up or down or to the nearest integer. – Aaron Meyerowitz Mar 19 '11 at 2:26