Super-fast growing function exceeding Graham's number [duplicate]

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?

marked as duplicate by Simply Beautiful Art, ahulpke, JonMark Perry, Ove Ahlman, Claude LeiboviciMar 5 '18 at 8:53

• +1 Great question. I'm fairly sure that the answer here is not going to be $n = 5$. I think the the answer is more going to be $n = G_5$ in all likelihood. There is a great numberphile video that describes just how big it is that I would recommend. youtube.com/watch?v=XTeJ64KD5cg – stuart stevenson Feb 17 '18 at 16:47
• @stuartstevenson I think your overestimating $G_n$ a bit here. – Arthur Feb 17 '18 at 16:50
• @ Arthur This is the fastest growing function I can think of right now. As long as n is expressible in closed form (e.g. as a $G_n$ number like stuartstevenson suggests), I'm content, because I can then finally sense the size of Graham's number. – prestokeys Feb 17 '18 at 16:52
• @Arthur Do you mean to say that I have overshot Graham's number with what I've put? – stuart stevenson Feb 17 '18 at 16:58
• I sincerely doubt we can come anywhere even close to finding the exact $n$ where it happens. But my gut says that it happens somewhere in the (relative) vicinity of what you get if you take Graham's number $3\uparrow\cdots\uparrow3$ and remove a single arrow, then use that as $n$. That's a lot smaller than Graham's number, to be sure, but it's just as difficult to comprehend. – Arthur Feb 17 '18 at 17:33

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}$.

• Better guess $g_{64}$. $G_{g_{63}}$ will be much smaller than $g_{64}$. – Peter Feb 18 '18 at 19:26
• I will assure you, $G_{g_{63}}\ll g_{64}$. – Simply Beautiful Art Mar 5 '18 at 1:52