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

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

user_8395547 · Answer

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)

user_4238408 · Answer

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 either 2 or 0 with 2 occurs only when x2 mod 4 == 2 and (x3==1 or (any x4,...xn == 0) ).
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

user_10618540 · Answer

Working off of your sequences idea and fleshing it out, you'd want to create a dictionary that can map all relevant sequences.

mapping = {}
for i in range(1, 10):
    mapping[i] = [i]
    last_digit = i
    while True:
        last_digit *= i
        last_digit = last_digit%10
        if last_digit in mapping[i]:
            break
        else:
            mapping[i].append(last_digit)

print(mapping)

This produces Output: mapping

{1: [1],
 2: [2, 4, 8, 6],
 3: [3, 9, 7, 1],
 4: [4, 6],
 5: [5],
 6: [6],
 7: [7, 9, 3, 1],
 8: [8, 4, 2, 6],
 9: [9, 1]}

Now the real logic can start, The key takeaway is that the pattern repeats itself after the sequence is completed. So, it does not matter how big the power is, if you just use a modulo and figure out which position of the sequence it should occupy.

def last_digit_func(lst, mapping):
    if lst == []: #taken from OP
        return 1
    last_digit = lst[0] % 10
    if 0 in lst[1:]: #edge case 0 as a power
        return 1
    if last_digit == 0: #edge case 0 at start
        return last_digit

    for current_power in lst[1:]:
        if len(mapping[last_digit]) == 1:
            return last_digit
        ind = current_power % len(mapping[last_digit])
        ind -= 1 #zero indexing, but powers start from 1. 
        last_digit = mapping[last_digit][ind]
    return last_digit

test1 = [3, 4, 2]
print(last_digit_func(test1, mapping)) #prints 1

I verified this by calculating the powers in python.

test2 = [767456 , 981242]
print(last_digit_func(test2, mapping)) #prints 6

And i tried to verify this by running it in python....i now have instant regrets and my program is still trying to solve it out. Oh well :)

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

3 Answers