2
$\begingroup$

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 ?
$\endgroup$
  • $\begingroup$ When you say "take another base", do you mean the base 3 of your power tower, or the base 10 that you are taking modulo? $\endgroup$ – Deedlit Jun 10 '16 at 22:06
  • $\begingroup$ I mean the $3$. $\endgroup$ – Peter Jun 10 '16 at 22:47
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, it is clear that only the last digits stabilize and that it is hopeless to calculate the FIRST digits of Graham's number. But one more thing : When I use a large number $a$ (Say $3^{27}$) and want to know the last $n$ digits of $a\uparrow\uparrow m$ with sufficiently large $m$, which number must be starting number of my algorithm ? Does $a^a$ always suffice ? $\endgroup$ – Peter Jun 14 '16 at 8:46

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.