Super-fast growing function exceeding Graham's number

Question

If we define $G_0 = 10^{100}$, and $G_n = 10^{G_{n-1}}$ (hence $G_0$ is a googol, $G_1$ is a googolplex, $G_2$ is a googolplexian), for what first value of n will $G_n$ exceed Graham's number?

Answer 1

Well, let's take a look at the definition of Graham's number.

$$g_n = \begin{cases} 3\uparrow\uparrow\uparrow\uparrow 3, &n=1\\ 3\uparrow^{g_{n-1}}3, &n\geq 2,n\in\mathbb{N}\end{cases}$$

Specifically, Graham's number is $g_{64}$. To clarify, the up arrows are Knuth's up-arrow notation:

$$a\uparrow^nb = \begin{cases} a^b, &n=1\\ 1, &n\geq1,b=0\\ a\uparrow^{n-1}(a\uparrow^n(b-1)), &\mathrm{otherwise}\end{cases}$$

A shortcut I will also use is tetration notation: ${^33}=3^{3^{3}}$. So let's look at some examples of the values of the numbers on the way to Graham's number, like $g_1$:

$$\begin{align}g_1 &= 3\uparrow\uparrow\uparrow\uparrow3\\ &= 3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow\uparrow2)\\ &=3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow\uparrow1))\\ &=3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow3))\\ &=3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow(3\uparrow\uparrow(3\uparrow\uparrow\uparrow2)))\\ &=3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow(3\uparrow\uparrow(3\uparrow\uparrow(3\uparrow\uparrow\uparrow1))))\\ &=3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow(3\uparrow\uparrow(3\uparrow\uparrow3)))\\ &=3\uparrow\uparrow\uparrow\left(3\uparrow\uparrow\uparrow\left(3\uparrow\uparrow3^{3^{3}}\right)\right)\\ &=3\uparrow\uparrow\uparrow\left(3\uparrow\uparrow\uparrow{^{3^{3^{3}}}3}\right)\end{align}$$

Now, I'm not going to bother reducing it further, because the reduction of $\left(3\uparrow\uparrow\uparrow{^{3^{3^{3}}}3}\right)$ requires over ${^{7625597484987}3}$ iterations. That is, 3 raised to itself 7625597484987 times. This is nested four additional times- so you find 3 raised to itself 7625597484987 times, take 3 and raise it to itself that many times, and repeat this process twice more, to get the number of iterations required to reduce this fully.

To note, your function is roughly equivalent to $10\uparrow\uparrow n$, or to raise 10 to the power of itself n times. As you can tell, it's vastly dominated even by $g_1$; any $n$ such that your function even comes close to $g_{64}$ will probably be impossible to write in any closed notation, much like Graham's number itself.

If I had to put an approximate guess as to what the value of n would be, I would put it at either $g_{63}$ or $g_{62}$.