Is this the correct way to compute the last $n$ digits of Graham's number?

Question

For the following question, all what is needed to know about Graham's number is that it is a power tower with many many many $3's$

Consider the following pseudocode :

input n

Start with $s=1$ and $p=7$ (the last digit of $3^3$)

Repeat

$s=s+1$

$p=3^p$ modulo $10^s$

Until $s=n$

output p

Questions :

• Does this algorithm return the $n$ last digits of Graham's number ?
• If I take another base and $p$ happens to get smaller than $s$. Do I have to add $\lambda(10^s)$ to $p$ ?
• Can I calculate the $n$ last digits of Graham's number (or another tetrated number) easier ?

Answer 1

Yes, this algorithm will return the last $n$ digits of Graham's number, and as far as I know it is the simplest way of doing so.

As for when $p$ gets smaller than $s$, you don't have to worry if the base of your power tower is relatively prime to 10. However, if your base does contain factors of 2 or 5, then you could theoretically have a problem if $p < s$; say if the base were 2, then if $p < s$ the next number $2^p$ would not be divisible by $2^s$ as it should be. However, it seems to me that this will never happen; if your base is divisible by 2, then each calculation of $p$ will result in a number divisible by $2^s$, and therefore will not be less than $s$. Similarly for when the base is divisible by 5. So even in such cases, you don't need to worry.

Answer 2

Your algorithm produces the first $n$ digits of OEIS sequence A133613, but only a small proportion of the digits of Graham's number are given by this sequence; that is, your algorithm produces the rightmost $n$ digits of Graham's number only if $n$ is not too big. (But even the "small proportion" corresponds to a number whose size is literally "out of this world".)

Let $T_k=b\uparrow\uparrow k$ with integers $b\ge 2\ (b\neq 10),\ k\ge 3$. The interesting phenomenon is that, for fixed $b$, a certain number of rightmost decimal digits of $T_{k+1}$ are the same as those of $T_k$, and this number of "stabilized" digits grows steadily as $k$ increases. However, the growth rate of the number of stabilized digits is miniscule compared to the super-exponential growth rate of the total number of digits, so for any given $T_k$ -- e.g., Graham's number -- the vast majority of its digits are not stabilized.

For $b=3$, the infinite sequence of stabilized digits is the above-linked OEIS sequence. Similar digit sequences for other values of $b$ are cross-referenced in the OEIS article.