2

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
Improve this question
4
  • Why can't you just find the power then convert it to a string then slice the string? I.e., last_digit = str(answer)[-1]? Or is the problem in calculating the large power? Commented Jul 19, 2018 at 16:52
  • Right, maybe I should have mention this, but I can't do that. Numbers are too big, and exponential function grows too fast. This task is being solved through the web browser, but even my laptop locally can't handle such big powers. Commented Jul 19, 2018 at 16:58
  • I see...so there's a specific time limitation here. I guess I assumed that this was just a homework problem you could solve any way. Commented Jul 19, 2018 at 16:59
  • Use pow(a, b, c). Modular Exponentiation in Python, Modular Exponentiation Commented Jul 19, 2018 at 17:29

1 Answer 1

Reset to default
3

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 :-)

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you for your response, It makes things clearer. While I'm definetely closer to the solution (more tests passed) I still have problem. Trying to apply your logic to 7 ^ (6 ^ 21) I get 9, while it shoud return 1. Same thing for 12 ^ (30 ^ 21): get 4 instead of 6.
@morteify: Yup. I have usually used with Euler's formula for (much) larger numbers, where the values are generally relatively prime. Kind of forgot that was a requirement. Answer updated
Thanks for your dedication, I learned a couple new things, but I already found shortest (not sure if best) solution. If you were interested I've updated my first post.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.