Compute the last (decimal) digit of x1 ^ (x2 ^ (x3 ^ (... ^ xn))) [duplicate]

Question

I need to find the unit digit of x1 ^ (x2 ^ (x3 ^ (... ^ xn))) from integers passed into the function as a list. For example the input [3, 4, 2] would return 1 because 3 ^ (4 ^ 2) = 3 ^ 16 = 43046721 the last digit of which is 1. The function needs to be efficient as possible because obviously trying to calculate 767456 ^ 981242 is not very quick.

I have tried a few methods but I think the best way to solve this is using sequences. For example any number ending in a 1, when raised to a power, will always end in 1. For 2, the resulting number will end in either 2, 4, 6 or 8. If a number is raised to a power, the last digit of the resulting number will follow a pattern based on the last digit of the exponent:

1: Sequence is 1

2: Sequence is 2, 4, 8, 6

3: Sequence is 3, 9, 7, 1

4: Sequence is 4, 6

5: Sequence is 5

6: Sequence is 6

7: Sequence is 7, 9, 3, 1

8: Sequence is 8, 4, 2, 6

9: Sequence is 9, 1

0: Sequence is 0

I think the easiest way to calculate the overall last digit is to work backwards through the list and calculate the last digit of each calculation one at a time until I get back to the start but I am not sure how to do this? If anyone could help or suggest another method that is equally or more efficient than that would be appreciated.

I have this code so far but it does not work for very large numbers

def last_digit(lst):
    if lst == []:
        return 1

    total = lst[len(lst)-2] ** lst[len(lst)-1]
    for n in reversed(range(len(lst)-2)):
        total = pow(lst[n], total)

    return total%10

Edit: 0 ^ 0 should be assumed to be 1

Answer 1

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)

Answer 2

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

1. is 0 if x2 == 0
2. is 1 if x2 > 0 and x3 == 0

3. if x2 is even, then it is either 2 or 0 with 2 occurs only when x2 mod 4 == 2 and (x3==1 or (any x4,...xn == 0) ).

4. if x2 is odd, then x2^2 mod 4 == 1, so we get 1 if x3 is even else x2 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