The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.



In [1]:

    
def foo(n, m):
    return str(sum(i ** i for i in range(1, n + 1)))[-m:]



In [2]:

    
foo(10, 10)









    Out[2]:





'0405071317'



In [3]:

    
n = 1000
m = 10
%timeit foo(n, m)
foo(n, m)









    



100 loops, best of 3: 14.5 ms per loop






    Out[3]:





'9110846700'

I wonder if the third argument to pow() could help make the calculation faster by avoiding unnecessary calculations.



In [4]:

    
n = 1000
m = 10
%timeit n ** n
%timeit pow(n, n, 10**m)









    



10000 loops, best of 3: 37.4 µs per loop
1000000 loops, best of 3: 1.46 µs per loop



In [5]:

    
def foo(n, m):
    m10 = 10 ** m
    return str(sum(pow(i, i, m10) for i in range(1, n + 1)))[-m:]



In [6]:

    
foo(10, 10)









    Out[6]:





'405071317'



In [7]:

    
n = 1000
m = 10
%timeit foo(n, m)
foo(n, m)









    



100 loops, best of 3: 2.53 ms per loop






    Out[7]:





'9110846700'

Try using modulo instead of str()[-m:] to get last m digits



In [8]:

    
def foo(n, m):
    m10 = 10 ** m
    return sum(pow(i, i, m10) for i in range(1, n + 1)) % m10



In [9]:

    
foo(10, 10)









    Out[9]:





405071317



In [10]:

    
n = 1000
m = 10
%timeit foo(n, m)
foo(n, m)









    



100 loops, best of 3: 2.53 ms per loop






    Out[10]:





9110846700

Cell #1 has the straightforward brute force approach. It is correct.

Cell #8 does not show leading zeroes, so it is not a good solution.

Cell #5 does show leading zeroes, has reasonable readability, and is fast.