Graham's Number - Rightmost Decimal Digits

Rightmost Decimal Digits

Graham's number is a "power tower" of the form 3↑↑n (with a very large value of n), so its rightmost decimal digits must satisfy certain properties common to all such towers. One of these properties is that all such towers of height greater than d (say), have the same sequence of d rightmost decimal digits. This is a special case of a more general property: The d rightmost decimal digits of all such towers of height greater than d+2, are independent of the topmost "3" in the tower; i.e., the topmost "3" can be changed to any other nonnegative integer without affecting the d rightmost digits.

The following table illustrates, for a few values of d, how this happens. For a given height of tower and number of digits d, the full range of d-digit numbers (10d of them) does not occur; instead, a certain smaller subset of values repeats itself in a cycle. The length of the cycle and some of the values (in parentheses) are shown in each cell of this table:

Number of different possible values of 3↑3↑…3↑x when all but the rightmost d decimal digits are ignored

Number of digits (d)	3↑x	3↑3↑x	3↑3↑3↑x	3↑3↑3↑3↑x	3↑3↑3↑3↑3↑x
1	4 (1,3,9,7)	2 (3,7)	1 (7)	1 (7)	1 (7)
2	20 (01,03,…,87,…,67)	4 (03,27,83,87)	2 (27,87)	1 (87)	1 (87)
3	100 (001,003,…,387,…,667)	20 (003,027,…387,…,587)	4 (027,987,227,387)	2 (987,387)	1 (387)

The particular rightmost d digits that are ultimately shared by all sufficiently tall towers of 3s are in bold text, and can be seen developing as the tower height increases. For any fixed number of digits d (row in the table), the number of values possible for 33↑…3↑x mod 10d, as x ranges over all nonnegative integers, is seen to decrease steadily as the height increases, until eventually reducing the "possibility set" to a single number (colored cells) when the height exceeds d+2.

A simple algorithm for computing these digits may be described as follows: let x = 3, then iterate, d times, the assignment x = 3x mod 10d. Except for omitting any leading 0s, the final value assigned to x (as a base-ten numeral) is then composed of the d rightmost decimal digits of 3↑↑n, for all n > d. (If the final value of x has fewer than d digits, then the required number of leading 0s must be added.)

Let k be the numerousness of these stable digits, which satisfy the congruence relation G(mod 10k)≡(mod 10k).

k=t-1, where G(t):=3↑↑t. It follows that, g₆₃ ≪ k ≪ g₆₄.

The algorithm above produces the following 500 rightmost decimal digits of Graham's number (or of any tower of more than 500 3s):

…02425950695064738395657479136519351798334535362521 43003540126026771622672160419810652263169355188780 38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080 25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887 17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387.