MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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

Thank you in advance.

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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