12
$\begingroup$

The title text for xkcd #1162 describes a method for expressing extremely large numbers:

Knuth Paper-Stack Notation: Write down the number on pages. Stack them. If the stack is too tall to fit in the room, write down the number of pages it would take to write down the number. THAT number won't fit in the room? Repeat. When a stack fits, write the number of iterations on a card. Pin it to the stack.

The Question

What would the result be when this method is applied to Graham's number?

Some Values

Sheets of paper can fit about 4,000 digits on them, and roughly 25,000 pages can be stacked before reaching the ceiling.

$\endgroup$
12
$\begingroup$

What would the result be when this method is applied to Graham's number?

(This is very similar to an earlier question, "Logarithms of logarithms of Graham's number, is the result ever handy?".)

Answer: The method cannot be applied to Graham's number ($G$), because the number of iterations required would be too large to have its digits written on any card.

By the definition of $G$ and the properties of Knuth arrows, $$G \ = \ 3\uparrow^{g_{63}} 3 = 3\uparrow^{g_{63}-1}(3\uparrow^{g_{63}-1} 3) \ \ggg \ 3\uparrow^{2}(3\uparrow^{g_{63}-1} 3) \ \gt \ 10\uparrow^{2}\left( \frac{3\uparrow^{g_{63}-1} 3}{9}\right)$$ where $g_{63}$ is a number with an incomprehensibly large number of decimal digits. (The rightmost inequality is by application of a simple change-of-base inequality.)

In the present problem, the number of full pages occupied by the digits of a number x is $$f(x) \ = \ \left\lfloor \frac{\lfloor \log_{10} x \rfloor +1}{4000} \right\rfloor $$

and the number to be finally written on the card is the least number of iterations, say $n$, such that

$$f^n(G) \ \le \ 25000$$

However, it's easily verified that
$$ f(x) \ \gt \ \log_{10} \log_{10} x \quad (x \ge 10^{10^{10}}) $$

so for any number of iterations $k$ (until the tower is reduced to less than $10^{10^{10}}$),

$$f^k(G) \ \gt \ (\log_{10})^{2k}(G) \ \ggg \ 10\uparrow^{2}\left( \frac{3\uparrow^{g_{63}-1} 3}{9}-2k\right)\tag{*} $$

Therefore, long before the final iteration is reached, the number of iterations will become utterly "unwritable". For example, even for $k$ iterations, where $k$ is the "unwritable" number $$k = 3\uparrow^{g_{63}-2} 3$$ the intermediate result, $f^k(G)$, is still enormously larger than a tower of $10$s of height $$\frac{3\uparrow^{g_{63}-1} 3}{9}-2(3\uparrow^{g_{63}-2} 3) \ \ggg \ 3\uparrow^{g_{63}-2} 3$$ Note that $3\uparrow^{g_{63}-2} 3$ has only two less arrows than $G$ itself!

NB: Graham's number is extreme overkill for this conclusion. For example, the cartoon's method cannot be applied to any number $x$ greater than or equal to, say, $10\uparrow\uparrow{(10\uparrow\uparrow5)}$, because the lefthand inequality in (*) above (with $x$ replacing $G$) will then show that $f^k(x) \ \gt \ 10\uparrow\uparrow4$ even for $k > 10\uparrow\uparrow4$ iterations. ($10\uparrow\uparrow4$ is "unwritable" in the sense of having more decimal digits than will fit in the observable universe, assuming at least one Planck volume per digit.)

$\endgroup$
  • $\begingroup$ So, not only would you need to repeat this process for the note card, with a sticky note attached to the note card, but you would have to repeat the process for the sticky note, and like 63 more layers of iteration. $\endgroup$ – Foo Barrigno Mar 31 '14 at 13:22

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.