11
$\begingroup$

I came across this problem. I have to find the last two digits ,and if I can , the last three digits of this number (which I believe is Infinity.)

$$n={2017}^{({2018)}^{{(2019)}^{{(•)}^{{(•)}^{(•)}}}}}$$ I started by computing $n \pmod {10} $ and which I think is $$7^{2k} \equiv 1 {\pmod {10}}$$ where $k$ is even ...

Next , I tried calculating $n{\pmod {100}}$ and I believe the answer is either $21,41,61,81$ but I don't know for sure..It was lot of trial and error...

So Could you please check my answer and ,if wrong, provide me a hint in the right direction?

$\endgroup$
  • $\begingroup$ If you're tying to ask what is $\;n^{2017^{2018^{\ldots}}}\;$ then the expression is undefined unless one can reasonably define infinite powers...and I don't think that'll be easy. $\endgroup$ – DonAntonio May 29 '17 at 7:07
  • 8
    $\begingroup$ The last two digits of infinity are $42$. You'd better write the expression as a limit. $\endgroup$ – Yves Daoust May 29 '17 at 7:11
  • $\begingroup$ @DonAntonio...It is actually $n={2017}^{{2018}^{{2019}^{{.}^{{.}^{.}}}}}$ and I too think this expression doesn't have any finite value. $\endgroup$ – user35508 May 29 '17 at 7:11
  • 1
    $\begingroup$ @ProfessorVector: Interestingly, the last three digits are $666$. $\endgroup$ – Yves Daoust May 29 '17 at 7:18
  • 4
    $\begingroup$ @YvesDaoust $42$ looks implausible for the final two digits of an odd number, but seems to to be very close $\endgroup$ – Henry May 29 '17 at 7:39
19
$\begingroup$

Let's assume the power tower is finite but includes at least the $2020$ term and possibly many more

We can say:

  • $2020^n$ is even, i.e. of the form $2m$ when $n\ge 1$
  • $2019^{2m}$ is of the form $4l+1$, as are all squares of odd numbers
  • $2018^{4l+1}$ is of the form $100k+68$ when $l \ge 1$
  • $2017^{100k+68}$ is of the form $1000j+241$

suggesting the final three digits are $241$

$\endgroup$
  • $\begingroup$ After fixing my answer, which is a generic method, I can now confirm the last digits are indeed $241$. $\endgroup$ – orlp May 29 '17 at 11:57
  • 1
    $\begingroup$ True, but how can you not start with 2021, 2022, and ..... and show that you always arrive consistent result, 241? The case is not closed. $\endgroup$ – Violapterin May 29 '17 at 17:32
  • $\begingroup$ @Aminopterin I have based my proof on $2020$ being even and any (finite positive) power of $2020$ being even. That is always true, and the rest of the demonstration follows. And that fact is needed: the last three digits of $2017^{2018^{2019}}$ are $361$ $\endgroup$ – Henry May 29 '17 at 19:04
11
$\begingroup$

I will show how to generally evaluate $a_1^{\,a_2^{\,\cdots}} \bmod m$, recursively.

  1. If $(a_1 \bmod m) \leq 1$, we have $a_1^{\,a_2^{\,\cdots}} \equiv a_1 \mod m$.

  2. Otherwise, if $\gcd(a_1, m) = 1$, we have $a_1^{\,a_2^{\,\cdots}} \equiv a_1^{\,a_2^{\,\cdots} \bmod \phi(m)}\mod m$. Recursively evaluate $r = a_2^{\,a_3^{\,\cdots}} \bmod \phi(m)$, and then calculate $a_1^r \bmod m$.

  3. Otherwise, factorize $m$ into primes. If $m$ is a prime power $p^k$, but $\gcd(a_1, p^k) \neq 1$, then $\gcd(a_1, p^k) = p^i$. Write $a'_1 = a_1/p^i$, then we have $a_1^{\,a_2^{\,\cdots}} \equiv a_1'^{\,a_2^{\,\cdots}}\cdot(p^i)^{\,a_2^{\,\cdots}} \mod p^k$.

    We recursively evaluate $r \equiv a_1'^{\,a_2^{\,\cdots}} \equiv a_1'^{\,a_2^{\,\cdots}\bmod \phi(p^k)} \equiv a_1'^{\,a_2^{\,\cdots}\bmod p^k - p^{k-1}} \mod p^k$.

    $s \equiv (p^i)^{\,a_2^{\,\cdots}} \equiv p^{i\,a_2^{\,\cdots}} \bmod p^k$ is different from the rest. If $i\,a_2^{\,a_3^{\,\cdots}} \geq k$ then $s = 0$, otherwise we simply need to evaluate bigger and bigger prefixes of $a$. If either the power tower gets too big, or we reach a $0$ or $1$, we stop, evaluate the power tower and find $s$. This is always a finite process, the tower will not be longer than $1 + \log_2k$ (this is even a bad upper bound, the real one is the tetra-logarithm).

    Then we find $st \bmod m$ and we're done.

  4. Recursively evaluate $a_1^{\,a_2^{\,\cdots}} \bmod p^k$ for each $p,k$ in the factorization of $m$. Then use the Chinese remainder theorem to find $a_1^{\,a_2^{\,\cdots}} \bmod m$.

Note that for any sequence $a$, and any modulus $m$, this terminates, as at every recursive step $m$ decreases, and $m$ is finite. Even when $a$ is infinite.


An implementation in Python using sympy (using zero based indexing for $a$):

from math import gcd, log
from sympy.ntheory import totient, factorint
from sympy.ntheory.modular import crt

def evaltowermax(l, k):
    r = 1
    for e in l[::-1]:
        # Prevent evaluation of large powers, 0.1 to account for errors.
        if log(e)*r - 0.1 > log(k):
            r = k
            break
        r = e**r
    return r

def modulartower(af, m, n=0):
    a = af(n); g = gcd(a, m)
    if a % m <= 1: return a % m
    if g == 1: return pow(a, modulartower(af, totient(m), n + 1), m)

    f = factorint(m)
    if len(f) == 1: # Prime power.
        p, i = factorint(g).popitem()
        k = f[p]

        tower = [af(ti) for ti in range(n, n + k.bit_length() + 1)]
        s = pow(p, i * evaltowermax(tower, k), m)
        if s == 0: return 0
        aprimef = lambda l: a // p**i if l == n else af(l)
        t = modulartower(aprimef, p**k - p**(k-1), n)
        return s*t % m

    m = [p**k for p, k in f.items()]
    r = [modulartower(af, p**k, n) for p, k in f.items()]
    return crt(m, r)[0]

print(modulartower(lambda n: 2017 + n, 10**20))

This computes the last 20 digits of $2017^{2018^{\cdots}}$ in an instant as $77345043177395978241$.


Simplified algorithm due to user Feersum:

  1. If $(a_1 \bmod m) \leq 1$, we have $a_1^{\,a_2^{\,\cdots}} \equiv a_1 \mod m$.

  2. Otherwise, factor $m$ into primes $p_i$. We calculate $\displaystyle x = \prod_{\gcd(p_i, a) = 1} p_i$ and $y = m/x$.

    Then, we compute $a_1^{\,a_2^{\,\cdots}}\bmod x$ and $a_1^{\,a_2^{\,\cdots}}\bmod y$ and use the Chinese remainder theorem to find $a_1^{\,a_2^{\,\cdots}}\bmod xy = a_1^{\,a_2^{\,\cdots}}\bmod m$.

    Since $a_1$ and $x$ are coprime we have $a_1^{\,a_2^{\,\cdots}}\equiv a_1^{\,a_2^{\,\cdots} \bmod \phi(x)} \mod x$. We recursively compute $r = a_2^{\,a_3^{\,\cdots}} \bmod \phi(x)$ and then compute $a_1^r \mod x$ directly.

    $a_1$ and $y$ is a bit interesting, as $y$ only consists of primes that are found in the decomposition of $a_1$. So for a large enough $k$ we have $a_1^k \equiv 0 \mod y$. For an infinite sequence $a$ without $0$ or $1$ elements, this is always the case. If an infinite sequence contains $0$ or $1$ elements or the sequence is finite, we must evaluate the prime tower $a_1^{\,a_2^{\,\cdots}}\bmod y$, luckily we only need to evaluate $\log_2 y + 1$ steps at worst.

$\endgroup$
  • $\begingroup$ @user35508 I fixed my answer. $\endgroup$ – orlp May 29 '17 at 11:57

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.