An analogue to Knuth's up-arrows

79 Views Asked by At

For every prime $p$, $p\#$ is defined as $p\#=2\cdot 3\cdot 5\cdots p$, let us further define $p\#\#=2\#\cdot 3\#\cdot 5\#\cdots p\#$, $p\#\#\#=2\#\#\cdot 3\#\#\cdot 5\#\#\cdots p\#\#$ and so on.

What is the growth rate of $p\#\cdots\#$ with $n$ $\#$s ?

We have $p\#\approx \exp(p)$ for large $p$.

1

There are 1 best solutions below

1
On BEST ANSWER

Let $p_n$ be the $n$th prime. You've provided the approximation $p\#\approx\exp(p)$. It thus follows that

$$p_n\#\#=\prod_{k=1}^np_k\#\approx\prod_{k=1}^n\exp(p_k)$$

Since $p_n\approx n\log(n)$, it follows that

$$p_n\#\#\approx\prod_{k=1}^nk^k$$

Asymptotic expansions for this can be found in this answer. A very crude approximation is given then as

$$p_n\#\#\approx n^{n^2/2}$$

Repeating this again gives us

$$p_n\#\#\#\approx\prod_{k=1}^nk^{k^2/2}$$

which is approximately, by the same approach,

$$p_n\#\#\#\approx n^{n^3/6}$$

and in general$^\star$,

$$p_n\underbrace{\#\dots\#}_m\approx n^{n^m/m!}$$


$\star$ Note that

$$\prod_{k=1}^nk^{k^m/m!}=\exp\sum_{k=1}^n\frac{k^m}{m!}\ln(k)\approx\exp\int_0^n\frac{x^m}{m!}\ln(x)~\mathrm dx\approx\exp\left(\frac{n^{m+1}}{(m+1)!}\ln(n)\right)=n^{n^{m+1}/(m+1)!}$$