2
$\begingroup$

I'm wondering whether there's a known way to compare the exponential factorial of n versus the tetration of a fixed number $($ e.g., $3$, since it appears in Graham's number $)$ with the same number of terms.

Here's an example: Find the smallest n such that $n^{!}$ is greater than $^{n-1}3$.

Both of these terms have the same number of exponents $($we ignore $1$ in the factorial exponential, thus $n-1$ terms$)$. A first computation shows that the tetration of $3$ grows much faster:

$4^{!} = 262144,~$ while $~^{3}3 = 3^{27} \approx 7.62 \cdot 10^{12}$

$5^{!} = 5^{262144} \approx 10^{183230},~$ while $~^{4}3 = 3^{3^{27}} \approx 10^{3.6 \cdot 10^{12}}$

Afterwards, numerical evaluation becomes more difficult, but what appears to be clear is that until the basis for the exponent in the exponential factorial becomes much, much larger, the tetration of $3$ will keep growing insanely faster, simply due to the higher last exponent.

Is this a known problem ?

$\endgroup$
  • $\begingroup$ This is somewhat related: on Googology wiki they say that the exponential factorial satisfies the bound $n^! \leq ^{n-1}n$, although I don't have a proper reference. $\endgroup$ – A.P. Nov 20 '15 at 21:22
  • $\begingroup$ To ease up the computation, repeatedly apply logarithm. $\endgroup$ – Lucian Nov 20 '15 at 21:38
  • $\begingroup$ That does not help at all. After two stages, you end up with ln(ln(ln(....ln(X + b))...), which you can only approximate. X is still huge, but you have transform the sum to make progress, otherwise you're stuck. You can use the identity ln(X+a) = ln(X(1 + a/X)) = ln X + ln(1+a/X), it's not very helpful unless you decide to ignore ln(1+a/X) for X huge, which does not work at all. Applying this logic will tell you that no matter what n grows to, tetration will always win. $\endgroup$ – Olivier Dec 4 '15 at 21:20
  • $\begingroup$ as for $n^{!} \le ^{n-1}n$, it seems totally obvious. You have two towers of the same height, on the left side decreasing from $n$ to 2, on the right side constant at $n$, thus for any $n\ge2$, the inequality will always hold. $\endgroup$ – Olivier Dec 4 '15 at 21:26
  • $\begingroup$ We can derive a very loose minimum bound from the early results. We observe that $3^{27}$ is already much greater than $4^{!}$, and thus can determine what would be the base exponent needed to match the next level of tetration, i.e find $n$ such that $n^{4^{!}}\ge3^{3^{27}}$. $n^Y \ge 3^X \equiv ln(n) \ge (X ln(3)/Y)$. With approximate values for $X \approx 7.62*10^{12}$ and $Y=262144$, we get $N \ge e^{31157912.84...}$. With any smaller $n$, the next level of tetration will be larger. So a very low minimum bound for n is $10^{13879415}$. $\endgroup$ – Olivier Dec 4 '15 at 22:10
6
$\begingroup$

In fact, for no $n$ do we have $n^!$ greater than $^{n-1} 3$. For the following, we will use $\log$ to mean logarithm base 3.

We will prove by induction that $(n+2)^{n^!} < \ ^n 3$ for $n \ge 2$.

Base cases: $4^{2^1} = 16 < 27 = \ ^23$.

$5^{3^!} = 5^9 < 3^{27} = \ ^33$

$6^{4^!} = 6^{4^9} < 3^{2* 4^9} < 3^{3^{27}} = \ ^4 3$

Inductive step: Suppose that $(n+2)^{n^!} < \ ^n 3$ for some $n \ge 4$. Then

$\log\log ((n+3)^{(n+1)^!}) = \log((n+1)^! \log (n+3)) = \log((n+1)^!) + \log\log(n+3) = n^! \log(n+1) + \log \log (n+3)$.

Now, I claim that $n^! \log(n+1) + \log \log (n+3) < n^! \log(n+2)$. After rearranging, this is equivalent to $n^! > \frac {\log\log(n+3)}{\log(n+2) - \log(n+1)}$. But in fact

$\frac{\log\log(n+3)}{\log(n+2) - \log(n+1)} = \frac{\log\log(n+3)}{\log(1 + \frac{1}{n+1})} = \frac{\log\log(n+3)}{\frac{\ln(1+\frac{1}{n+1})}{\ln(3)}} < \frac{\log\log(n+3)}{\frac{1}{(n+2)\ln(3)}} = (n+2)\ln(3) \log\log(n+3) < n^9 \le n^!$.

(The last two inequalities follow because $n \ge 4$.)

So

$\log\log ((n+3)^{(n+1)^!}) < n^! \log(n+2) = \log((n+2)^{n^!}) < \log(^n 3) = \ ^{n-1} 3$

$(n+3)^{(n+1)^!} < \ ^{n+1} 3$, as desired.

So for $n \ge 3$, $n^! < (n+1)^{(n-1)^!} < \ ^{n-1} 3$, and of course one can verify this is true for $n = 2$ as well.

Going in the other direction, obviously $n^! > \ ^{n-2} 3$ for $n \ge 2$, since each term of the first tower is greater or equal to each term of the second, with equality in just one case. So for all $n \ge 2$ we have

$^{n-2} 3 < n^! < \ ^{n-1} 3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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