Project Euler Problem 48: Self powers

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}$.

Version 1: The obvious way

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]:
9110846700

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.

https://docs.python.org/3/reference/datamodel.html

Version 2: Some simple modulo arithmetic

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]:
3
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]:
9110846700

This way, we never let the result of any intermediate addition or multiplication exceed $10^{10}-1$.

Comments

Comments powered by Disqus