CODEWITHSUNDEEP
pythonpython-3.xmath
morteify
morteify

Reputation: 181

Finding unit digit of large powers

I need to find the last digit of large power. When I get simple x^n, I solve problem with this: pow(x, n, 10). But what should I do when I have such example: 103171^(14394^(221515^(441792^507709)))? I noticed the cyclicity of specific digits, but it's not enough. I am afraid I'm missing some important point. As an input of my main function last_digit I get list of numbers (lst), let's say [3, 4, 2]- this means I need to compute 3 ^ (4 ^ 2). I've got about 630 tests to pass and I can only make about 580 (most of them are randomly generated). Here's my code I've tried:

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

def power_rec(lst):
    remainder = pow(lst[-2], lst[-1], 4)
    if len(lst) == 2:
        first_num = int(str(lst[0])[-1])
        second_num = int(str(lst[1])[-1]) 
        return CYCLES[first_num][second_num - 1]
    lst = lst[:-2] + [ remainder ]
    return power_rec(lst)

def last_digit(lst):
    if len(lst) == 2:
        return pow(lst[0], lst[1], 10)
    if lst == []:
        return 1
    if len(lst) == 1:
        return int(str(lst[0])[-1])
    return power_rec(lst)

E.g. I cannot pass tests with inputs: [555913, 845991, 261716, 431426, 571315, 456986, 461380, 413475] or [2, 2, 101, 2].

I have to assume that 0 ^ 0 = 1 and that last_digit of an empty list equals to 1. I'd appreciate any helpful tips.

UPDATE. Found shortest solution:

def last_digit(lst):
    result = 1
    for num in lst[::-1]:
        result = pow(num, (result if result < 4 else result % 4 + 4) )

    return result % 10

Upvotes: 2

Views: 678

Answers (1)

Nemo
Nemo

Reputation: 71615

This is a pure math problem...

The last digit of any number is just that number modulo 10. So you are asking how to reduce numbers modulo 10 when they are a big cascade of exponents.

To do this, you can apply Euler's Theorem repeatedly. What it says (well, implies) is that to reduce a^b modulo n, you can reduce b modulo phi(n).

So, to reduce a^b modulo 10, you can start by reducing b modulo phi(10) = 4.

Here, b has the form c^d. To reduce c^d modulo 4, you can start by reducing d modulo phi(4) = 2. That's far enough to make this problem easy.

Let's take your example:

103171^(14394^(221515^(441792^507709))) modulo 10

Start by reducing (221515^(blahblah)) modulo 2. That's pretty clearly 1, so we are already down to:

103171^(14394^1) = 103171^14394 modulo 10

Next, just reduce 14394 modulo 4 to get 2. So we are down to:

103171^2 modulo 10

I think you can take it from there.

(Update)

I forgot that Euler's theorem only applies when a (the base) and n (the modulus) have no factors in common. Whoops.

So when trying to reduce 14394^(blahblah) modulo 4, we have to do it directly... 14394^(large power) is actually divisible by 4, so this is actually zero and the correct answer is 103171^0 = 1. (Which the other approach also gave but just by luck.)

For the example in your comment (7^(6^21)), we have a similar case. 6^21 is zero (mod 4), so the answer is 7^0 = 1.

12^(30^21) it is even trickier because 12 and 10 are not relatively prime. Here we will need to compute the value (mod 5) and (mod 2) and combine the two. But I am late for a meeting so I cannot finish this now :-)

Upvotes: 3

Related Questions