With $f(n) = n!$, what is the least $k$ such that $f^k(\text{googolplex}) > \text{Graham's number}$?

378 Views Asked by At

$\text{googolplex} = 10^{(10^{100})}$

Is $\text{googolplex}!$ greater than $\text{Graham's number}$? How would this be proven?

If $\text{googolplex}! \le \text{Graham's number}$, (which I expect) then how many cycles of $( \dots(((\text{googolplex}!)!)!) \dots)!$ would be needed to exceed $\text{Graham's number}$?

2

There are 2 best solutions below

6
On

Graham's number is way bigger.

Basically, any number you construct with a normal-looking number of normal-looking operators acting on a normal amount of normal-sized numbers (terms deliberately not clearly defined) will be far smaller than Graham's number, basically because you're not doing anywhere near enough recursion to approach the recursion done in defining Graham's number.

0
On

We derive a dramatic improvement over a comment that suspected even $k= 3\uparrow^{g_{63}-1}3$ is not enough iterations for $f^k(\text{googolplex}) > \text{Graham's number}$, where $f$ is the factorial function.

For convenience in writing Knuth's up-arrows, we use the operator notation $$[a]b = 3\uparrow^a b,$$ so Graham's number $(g_{64})$ is defined by the recursion $$g_0 = 4\\ g_{n+1} = [g_n]3.$$

We show that Graham's number can be written as an exactly specified number of iterations of the tetration operator $([2])$: $$\text{Graham's number } = [2]^t 1 $$ and therefore that $$\text{Graham's number } \gt f^{t-3}(\text{googolplex})$$ because $\ [2]^3 1 > \text{googolplex}\ $ and $\ [2]n > n!\ $ for all positive integers $n$.

Before proceeding to calculate $t$, we state some properties of the hyperoperators $[p]$. Associating from the right, these satisfy the following recursion for $a,b\in Z_{>0}$: $$[a]b = \begin{cases} 3 & \text{if } b=1\\ 3^b & \text{if }a=1\\ [a-1][a](b-1) & \text{otherwise} \end{cases}\tag{E0}$$

which implies the identities

$$\begin{align} [a]b &= [a-1]^b 1 &(a\ge 2,\ b \ge 1)\tag{E1}\\ [a]b &= [a-2]^{[a](b-1)}1 &(a\ge 3,\ b \ge 2)\tag{E2} \end{align}$$


Aside: $(E1)$ is obtained by repeatedly applying $(E0)$ to itself, as $$\begin{align}[a]b &= [a-1][a](b-1)\\ &= [a-1][a-1][a](b-2)\\ &\cdots\\ &= [a-1]^{(b-1)}[a] 1\\ &= [a-1]^{(b-1)}[a-1] 1\\ &= [a-1]^b 1 \end{align}$$ and $(E2)$ is obtained by applying $(E1)$ to $(E0)$ as

$$[a]b = [\underbrace{a-1}_{A}]\underbrace{[a](b-1)}_{B} = [A]B = [A-1]^B 1 = [a-2]^{[a](b-1)}1.$$


General result:

If $p\ge 4\ $ and $\ q \le p-3\ $ are positive integers with opposite parity, then $$[p]3 = [q]^t 1$$ where $$t=[q+2](b_j-1)\\ j={{p-q-1}\over{2}}$$ and $b_j$ is the last term in the very rapidly increasing sequence $b_1 < b_2 < \dots < b_j$, given by the recursion

$$\begin{align} b_1 &= [p-1][p-1]1\\ b_i &= [p-2i+1]^{[p-2i+3](b_{i-1}-1)-1}1\quad (1\lt i\le j).\\ \end{align}$$

Proof-sketch, using repeated application of the previous identity $E2$ until $[p]3$ is reduced to the form $[q]^t 1$: $$\begin{align} [p]3 &= [p-1]([p-1][p-1]1)\\ &= [a_1]b_1,\quad a_1 = p-1,\ b_1=[p-1][p-1]1\\ &= [a_1-2][a_1-2]^{[a_1](b_1-1)-1}1\\ &= [a_2]b_2,\quad a_2 = a_1 - 2=p-3,\ b_2 = [a_2]^{[a_1](b_1-1)-1}1\\ &= [a_2-2][a_2-2]^{[a_2](b_2-1)-1}1\\ &= [a_3]b_3,\quad a_3 = a_2 - 2=p-5,\ b_3 = [a_3]^{[a_2](b_2-1)-1}1\\ &...\\ &= [a_i-2]^{[a_i](b_i-1)},\quad a_i = a_{i-1} - 2=p-2i+1,\ b_i = [a_i]^{[a_{i-1}](b_{i-1}-1)-1}1\\ &...\\ &= [q]^{[q+2](b_j-1)}1,\quad q = a_j-2=p-2\cdot j-1\implies j={{p-q-1}\over{2}}\\ \end{align}$$ QED

Applying the above results to $p=g_{63}$ and $q=2$:

$$\text{Graham's number } = [2]^t 1 > f^{t-3}(\text{googolplex})$$ where $$t=[4](b_j-1)\\ j={{g_{63}-3}\over{2}}$$ and $b_j$ is the last term in the very long and rapidly increasing sequence $b_1 < b_2 < \dots < b_j$ given by the recursion $$\begin{align} b_1 &= [g_{63}-1][g_{63}-1]1\\ b_i &= [g_{63}-2i+1]^{[g_{63}-2i+3](b_{i-1}-1)-1}1\quad (1\lt i\le j).\\ \end{align}$$

NB: We have $t = [4](b_j-1) \gg b_i$ for each $b_i$ in the sequence $b_1 < b_2 < \dots < b_j$, where the number of terms is $j={{g_{63}-3}\over{2}}$, and already the second term is $$b_2 = [g_{63}-3]^{[g_{63}-1]([g_{63}-1]3-1)-1}1.$$ Making some extremely crude simplifications, we have for example $$k \le {[4]^{[6]^{[8]{\cdot^{\cdot^{\cdot^{[g_{63}-3]^Q 1}\cdot}\cdot}\cdot}1}1}1} \ \implies\ f^k (\text{googolplex}) \le \text{Graham's number}$$

where the topmost term is $Q = [g_{63}-1]([g_{63}-1]3-1)-1$ and the height of the "iteration tower" is ${g_{63}-3}\over 2$.