Compute the last (decimal) digit of x1 ^ (x2 ^ (x3 ^ (... ^ xn)))
This is more math than programming. Notice that all the sequences you listed has length either 1, 2, or 4. More precisely, x^4
always ends with either 0, 1, 5, 6
, as does x^(4k)
. So if you know x^(m mod 4) mod 10
, you know x^m mod 10
.
Now, to compute x2^(x3^(...^xn)) mod 4
. The story is very similar, x^2 mod 4
is ether 0
if x=2k
or 1
if x=2k+1
(why?). So
- is 0 if x2 == 0
- is 1 if x2 > 0 and x3 == 0
if
x2
is even, then it is either2
or0
with2
occurs only whenx2 mod 4 == 2 and (x3==1 or (any x4,...xn == 0) )
.if
x2
is odd, thenx2^2 mod 4 == 1
, so we get1
ifx3
is even elsex2 mod 4
.
Enough math, let's talk coding. There might be corner cases that I haven't cover, but it's should work for most cases.
def last_digit(lst):
if len(lst) == 0:
return 1
x = lst[0] % 10
if len(lst) == 1:
return x
# these number never change
if x in [0,1,5,6]:
return x
# now we care for x[1] ^ 4:
x1 = x[1] % 4
# only x[0] and x[1]
if len(lst) == 2 or x1==0:
return x[0] ** x1 % 10
# now that x[2] comes to the picture
if x1 % 2: # == 1
x1_pow_x2 = x1 if (x[2]%2) else 1
else:
x1_pow_x2 = 2 if (x1==2 and x[2]%2 == 1) else 0
# we almost done:
ret = x ** x1_pow_x2 % 10
# now, there's a catch here, if x[1]^(x[2]^...^x[n-1]) >= 4,
# we need to multiply ret with the last digit of x ** 4
if x[1] >=4 or (x[1] > 1 and x[2] > 1):
ret = (ret * x**4) % 10
return ret
x^n = x^(n%4) because the last digit always has a period of 4.
x ^2 ^3 ^4 ^5
1 1 1 1 1
2 4 8 6 2
3 9 7 1 3
4 6 4 6 4
5 5 5 5 5
6 6 6 6 6
7 9 3 1 7
8 4 2 6 8
9 1 9 1 9
As you can see, all 9 digits have a period of 4 so we can use %4 to make calculations easier.
There's also a pattern if we do this %4.
x ^0 ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9
1 1 1 1 1 1 1 1 1 1 1
2 1 2 0 0 0 0 0 0 0 0
3 1 3 1 3 1 3 1 3 1 3
4 1 0 0 0 0 0 0 0 0 0
5 1 1 1 1 1 1 1 1 1 1 (all %4)
6 1 2 0 0 0 0 0 0 0 0
7 1 3 1 3 1 3 1 3 1 3
8 1 0 0 0 0 0 0 0 0 0
9 1 1 1 1 1 1 1 1 1 1
As shown, there is a pattern for each x when n>1. Therefore, you can see that (x^n)%4 = (x^(n+4k))%4 when n>1. We can then prevent the issues that arises from n=0 and n=1 by adding 4 to n. This is because, if (x^n)%4 = (x^(n+4k))%4, then (x^n)%4 = (x^(n%4+4))%4 as well.
powers = [3, 9, 7, 1]
lastDigit = 1
for i in range(len(powers) - 1, -1, -1):
if lastDigit == 0:
lastDigit = 1
elif lastDigit == 1:
lastDigit = powers[i]
else:
lastDigit = powers[i]**(lastDigit%4+4)
print(lastDigit%10)