Using Knuth's up-arrow notation, Graham's number $G$ is defined as $$ G=g_{64},\,\,\, \text{ where }g_1=3\uparrow\uparrow\uparrow\uparrow 3 \text{ and } g_n=3\uparrow^{g_{n-1}}3. $$ I was wondering if it's possible to know what is the power of two, $H$, that is closest to $G$.

My initial idea was to construct it in a similar way, that is, $$ H=h_{64},\,\,\, \text{ where }h_1=2\uparrow\uparrow\uparrow\uparrow 2 \text{ and } h_n=2\uparrow^{h_{n-1}}2, $$ which is a power of two. However, something tells me it should be a bigger number. For instance, is it true that $h_{65}>G$?


Unfortunately, any up-arrow of $2$'s expands as $$ 2 \uparrow^n 2 = \underbrace{2 \uparrow^{n-1} \dots \uparrow^{n-1} 2}_{\text{2 times}} = 2 \uparrow^{n-1} 2 $$ and so eventually we just get to $2 \uparrow 2 = 2^2 = 2\cdot 2 = 2 + 2 = 4$. So your definition of $h_{64}$ is not all that big: we just get $H = h_{64} = 4$.

(Graham and Rothschild's original paper starts with $h_1 = 2 \uparrow^{12} 3$ and then iterates $h_n = 2 \uparrow^{h_{n-1}} 3$, ending with $h_7$, to get the upper bound they need. Putting a $3$ at the end avoids the cancellation we see in $2 \uparrow^n 2$. But this $h_7$ is actually much smaller than $G$.)

There is not likely to be a great expression for the closest power of $2$ to $G$. The sequence $g_1, g_2, g_3, \dots$ grows so quickly that it is not too misleading to say that $G$ and $2^G$ are "basically the same" - they are very close on the scale that we're considering! We definitely have $2^{g_{63}} < G < 2^{g_{64}}$, and the second inequality is much closer than the first.


In a sense, one might say something such as


in the sense that if we tried to write the left side as $10^x$, $x$ would have to differ from $100$ by about $10^{-100}$, which is extremely insignificant.

In the same manner, one might say things such as


in the sense that this is basically the closest way we can write the result compactly.

Following this line of thought, we would then have


for sufficiently large values of $k$, and by induction, the reasonable interpretation of

$$2^G\approx G$$

meaning that $G$ is the "closest" we can get to $\operatorname{lg}(G)$ by using digits and uparrows in a compact form.


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.