Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The prime numbers are positive integers that have no multiplicative structure. One method for counting the number of primes contained in a positive integer is sieving. As an example, for the integer ${10}$, we begin with the first prime ${2}$, and cross out all its multiples ${4,6,8,10}$. Then we proceed to the next number not crossed out namely ${3}$, and cross out all its multiples ${6,9}$, and add back the product of the two primes ${6}$ because we don't want to cross out any number more than once. We are left with the set ${2,3,5,7}$ and the counting function $\pi(x)=4$.

So far, so good. But what if we want to do something crazy like count the prime number of prime numbers? We can do that! Just map the primes counted ${2,3,5,7} \rightarrow {1,2,3,4}$ and perform the sieve again. Circle the 2, cross out the 4, circle the 3. The super-prime counting function calls the prime counting function twice i.e. $\pi(\pi(10))=\pi(4)=3$.

We can call this prime counting function again and again until we eventually arrive at zero for any integer in some finite number of steps. Let's use indices to keep track of the number of calls. For this example, we have $\pi_1(10)=4, \pi_2(10)=3, \pi_3(10)=2, \pi_4(10)=1, \pi_5(10)=0$ as expected.

Let's use another example of x=210 to show that the numbers don't always behave in such a regular way.

$\pi_1(210)=46, \pi_2(210)=14, \pi_3(210)=6, \pi_4(210)=3, \pi_5(210)=2, \pi_6(210)=1, \pi_7(210)=0$.

So much for the positive finite integers. But what about all the primes taken together? Owing to Euclid, we know that there exist an infinite number of primes, so $\pi(\inf)=\inf$. What of the higher order primes? Assuming the axiom of choice holds, we can use our mapping function again to produce all the integers from all the prime numbers. Once we have all the integers again, we call the sieve function again to get the super-primes. Any higher order prime function will produce a set as large as the integers, so $\pi_2(\inf)=\inf$. All the positive integers converge to ${0}$ in finite steps, but the set of all positive integers never converge for any finite number of function calls, so $\pi_n(\inf)=\inf$ for any positive integer n. This is a way of showing that you jump into infinities all at once!

Here's my question: if we are allowed to call the prime number function $\pi(x)$ an infinite number of times, will the set of positive integers converge to a finite number? In other words, is $\pi_\inf(\inf)=0$?

share|improve this question

3 Answers 3

The problem as stated ignores a lot of the structure in the prime counting function $\pi(x)$. For example, the map from the primes to the integers ${2, 3, 5, 7} \rightarrow {1, 2, 3, 4}$ is the actual number of primes in each number. Using this can have some advantages.

In the example of x=210, we don't require a number of maps to reduce the integer to 0. We only require one map, namely the prime counting function mapped to itself. Instead of this:

$\pi_1(210)=46, \pi_2(210)=14, \pi_3(210)=6, \pi_4(210)=3, \pi_5(210)=2, \pi_6(210)=1, \pi_7(210)=0$,

we can simply write this:

$\pi(210)=46, \pi(46)=14, \pi(14)=6, \pi(6)=3, \pi(3)=2, \pi(2)=1, \pi(1)=0$.

Since we already know there are an infinite number of primes, then $\pi(x) \rightarrow \pi(x)$ already includes $\pi_\inf(x)$. In order to answer whether the value of $\pi_\inf(\inf)=0$, we only have to take the limit of $\pi(x)$ as $x \rightarrow \inf$. Indeed, according to the prime number theorem, the prime counting function tends to the logarithmic integral as x tends to infinity, and the logarithmic integral tends to infinity as x tends to infinity. Therefore, the prime counting function does not converge.

share|improve this answer

Since we have $\pi(x) \approx \frac x{\ln (x)}\gt \sqrt x$ for $x \ge 4$, we can say $\pi(4)=2, \pi_2(4^2) \ge 2, \pi_3(4^{2^2})\ge 2, \pi_n(4^{2\uparrow \uparrow(n-1)})\ge 2$ so there are numbers that take arbitrarily many applications of $\pi$ to get to zero. The $\uparrow \uparrow$ is Knuth's up-arrow notation

share|improve this answer

The number of applications of $\pi$ required to bring a number to 0 is unbounded because A007097, the first number requiring $n$ applications of $\pi$ to reach 1, is infinite.

share|improve this answer
    
I couldn't understand a thing on that site. Could you elaborate? From a simple understanding of the definition, it seems like $\pi(2)=1, \pi(1)=0$ because 2 is the first prime... –  bwkaplan Mar 26 at 1:33
    
@bwkaplan: $\pi(2)=1,\ \pi(\pi(3))=1,\ \pi(\pi(\pi(5)))=1,$ $\pi(\pi(\pi(\pi(11))))=1,$ etc. –  Charles Mar 26 at 1:35

Your Answer

 
discard

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.