# Finding the last two digits of a number

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?

• 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. – DonAntonio May 29 '17 at 7:07
• The last two digits of infinity are $42$. You'd better write the expression as a limit. – Yves Daoust May 29 '17 at 7:11
• @DonAntonio...It is actually $n={2017}^{{2018}^{{2019}^{{.}^{{.}^{.}}}}}$ and I too think this expression doesn't have any finite value. – user35508 May 29 '17 at 7:11
• @ProfessorVector: Interestingly, the last three digits are $666$. – Yves Daoust May 29 '17 at 7:18
• @YvesDaoust $42$ looks implausible for the final two digits of an odd number, but seems to to be very close – Henry May 29 '17 at 7:39

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$

• After fixing my answer, which is a generic method, I can now confirm the last digits are indeed $241$. – orlp May 29 '17 at 11:57
• 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. – Violapterin May 29 '17 at 17:32
• @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$ – Henry May 29 '17 at 19:04

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.

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