The series, $1^1 + 2^2 + 3^3 + ... + 10^{10} = 10405071317$.
Find the last ten digits of the series, $1^1 + 2^2 + 3^3 + ... + 1000^{1000}$.
In [1]:
from six.moves import map, range, reduce
In [2]:
sum(map(lambda k: k**k, range(1, 1000+1))) % 10**10
Out[2]:
This leaves much to be desired since we have to compute a integer with at least $10^{3000}$ digits only to truncate off $10^{3000} - 10^{10} = 10^{10} (10^{2990} - 1)$ digits. Note that in most other languages such as Java, we would have had to resort to some library like BigInteger to perform this computation. In Python, all numbers are represented by a (theoretically) infinite number of bits:
Integers (int)
These represent numbers in an unlimited range, subject to available (virtual) memory only. For the purpose of shift and mask operations, a binary representation is assumed, and negative numbers are represented in a variant of 2’s complement which gives the illusion of an infinite string of sign bits extending to the left.
We're asked to find $1^1 + 2^2 + 3^3 + ... + 1000^{1000} \mod 10^{10}$. Note that
$$a + b \mod n = (a \mod n) + (b \mod n)$$
and that
$$a \cdot b \mod n = (a \mod n) \cdot (b \mod n)$$
so we can implement modulo sum and prod functions.
In [3]:
def prod_mod(nums, m):
"Multiply all nums modulo m"
return reduce(lambda p, q: (p*q)%m, map(lambda n: n%m, nums))
In [4]:
from itertools import repeat
pow_mod = lambda n, p, m: prod_mod(repeat(n, p), m)
In [5]:
pow_mod(3, 3, 8)
Out[5]:
In [6]:
sum_mod = lambda nums, m: reduce(lambda p, q: (p+q)%m, map(lambda n: n%m, nums))
In [7]:
sum_mod(map(lambda k: pow_mod(k, k, 10**10), range(1, 1000+1)), 10**10)
Out[7]:
This way, we never let the result of any intermediate addition or multiplication exceed $10^{10}-1$.