# Graham's number closest power of two

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

$$10^{100}+1\approx10^{100}$$

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

$$2^{2\uparrow\uparrow10^{100}}=2\uparrow\uparrow(10^{100}+1)\approx2\uparrow\uparrow10^{100}$$

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

$$2\uparrow^n2\uparrow^{n+1}k\approx2\uparrow^{n+1}k$$

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.