3
$\begingroup$

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

Thank you in advance.

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 19, 2011 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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