# What is the significance of the power of $3$ in the sequence of primes given by $\lfloor A^{3^n}\rfloor ?$

Mill's constant is a number such that $\lfloor A^{3^n}\rfloor$ is prime for all $n$. The existence of such an $A$ was proven in $1947$.

I know little about number theory, but I am curious as to why the power of $3$ is chosen in the exponent. It seems likely that this is purely because $3$ is the smallest and thus in a sense, simplest, odd prime - though this is total speculation on my part. I have two, somewhat related questions:

• If $p_k$ is the $k^{\text{th}}$ odd prime, does there exist $Q_k\in\mathbb{R}$ such that $\lfloor Q_k^{p_k^n}\rfloor$ is prime for all $n?$
• Why would a power of $2$ not work?$^*$ Or in other words, why is there no $Q$ such that $\lfloor Q^{2^n}\rfloor$ is prime for all $n?$

$^*$ I have made an assumption here which may be false, do no hesitate to correct if so.

The $\lfloor A^{3^n}\rfloor$ thing sounds impressive, but it's really not. It follows quickly from the (much more impressive) fact that for any sufficiently large integer $N$, there's always a prime between $N^3$ and $(N+1)^3$.

Given that fact, here's Mill's proof of his constant. It's only one page long, and doesn't use any difficult math. The idea is to restrict $A$ to a small interval, and make the interval smaller and smaller in a series of steps.

At each step, there's a certain range that $A^{3^n}$ can be in. For that step, choose a prime $p$ in that range, and then restrict $A$ to a slightly smaller interval so that everywhere in the new interval, $\lfloor A^{3^n}\rfloor$ equals $p$. Since the function $x^{3^n}$ grows so fast, you know that the new range for $A^{3^{(n+1)}}$ is so large that it must include a prime number, so you can keep going to the next step. That observation follows from the impressive fact above, and it's the reason for the "3". If you continue this process forever, you'll get more and more accurate values for $A$.

$\lfloor Q^{k^n}\rfloor$ always works if $k$ is at least 3. The same argument shows there must exist such a $Q$.
But $\lfloor Q^{2^n}\rfloor$ might not work. It depends on the following open conjecture: is there always a prime between $N^2$ and $(N+1)^2$? This is known as Legendre's conjecture, and it's thought to be extremely difficult.
• Expanding slightly: the core difference in complexity between the two is that the gap between $m=N^3$ and $(N+1)^3$ is $\Theta(m^{2/3})$, while the gap between $m=N^2$ and $(N+1)^2$ is $\Theta(m^{1/2})$. The existence of primes in intervals of the form $(m, m+m^\theta)$ is (roughly, if I'm remembering correctly) related to the behavior of the Riemann zeta function at $z=\theta+it$, and so the existence of primes in square-root-sized intervals is intimately connected with the Riemann hypothesis. Aug 23, 2013 at 1:00
• @Lopsy thanks to your explanation I was able to follow Mill's demonstration too! Playing with the demonstration intervals I think I might have found a way of encapsulating $[N,2N]$ primes into a Mill's like constant. If you had some time it would be fine if you could have a look because you understand very well the problem. It would be very appreciated! Just in case: math.stackexchange.com/questions/1807823/… Jun 1, 2016 at 23:52