2
$\begingroup$

How to find rightmost $n$ decimal digits of Graham's number efficiently.

The last 500 digits are on the wiki/Graham's_number, but I want to know more.

PowerTowerMod seems to be able to do it but is not very efficient, is there a better way?

Block[
 {$RecursionLimit = Infinity},
 ResourceFunction["PowerTowerMod"][
  3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^3^\
3^3^3^3^3^3^3, 10^500]
]

And the recursion deadline is not very clear

$\endgroup$
  • $\begingroup$ @ciao well, then the problem is, why 600? $\endgroup$ – GalAster Dec 13 '19 at 2:59
  • 1
    $\begingroup$ The problem here is to find a better algorithm; that's not really a MMA problem. Maybe this question should really be asked on a different forum. $\endgroup$ – MarcoB Dec 13 '19 at 13:43
  • 3
    $\begingroup$ There are 16 million rightmost digits available online. Perhaps avail yourself of them. $\endgroup$ – rasher Dec 15 '19 at 18:12
1
$\begingroup$

As Wikipedia and the wikia state, a simple algorithm for computing the last $n$ digits is given by:

$$N(0)=3\\N(m+1)=3^{N(m)}\bmod10^{m+1}$$

Here, $N(m)$ is the last $m$ digits. This is the same algorithm given in Is this the correct way to compute the last $n$ digits of Graham's number?. Example python code:

def powmod(exp, mod, base = 3):

    # Assume base = 3 and mod = 10^m
    # and apply Euler's totient theorem

    exp %= mod * 2 // 5

    # Exponentiate by squaring
    res = 1

    while exp > 0:
        if exp % 2 == 1:
            res = res * base % mod
        base = base * base % mod
        exp //= 2
    return res

def lastdigits(m):
    res = 3
    for i in range(1, m+1):
        res = powmod(res, pow(10, i))
    return res

Try it online

$\endgroup$

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.