Project Euler Problem 48: Self Powers

The source code for this problem can be found here.

Problem Statement

The series, \(1^1 + 2^2 + 3^3 + \dots + 10^{10} = 10405071317\).

Find the last ten digits of the series, \(1^1 + 2^2 + 3^3 + \dots + 1000^{1000}\).

Solution Discussion

The major point to observe with this problem is that the size of the terms grows very quickly, too quickly to fit into memory given the limitations of today’s computers. This can be overcome by taking advantage of the fact that we only need to calculate the \(10\) least significant digits of the sum; that is:

\[\begin{split}&(1^1 + 2^2 + 3^3 + \dots + 1000^{1000}) \mod 10^{10} \\ &= (1^1 \mod 10^{10}) + (2^2 \mod 10^{10}) + (3^3 \mod 10^{10}) + \dots + (1000^{1000} \mod 10^{10}) \mod 10^{10}\end{split}\]

Each of these terms can be kept to \(10\) digits or less, which will fit into one \(64\)-bit word. These reduced terms can then be aggregated and reduced at each step to ensure that all values remain bounded by \(10^{10}\).

The key ingredient in this algorithm is modular exponentiation, that is, computing \(a^x \mod m\). Modular exponentiation is achieved with the square and multiply algorithm. It is also provided by Python’s pow built-in function by specifying the desired modulus as the optional third argument.

Solution Implementation

def solve():
    """ Compute the answer to Project Euler's problem #48 """
    target = 1000
    modulus = 10 ** 10  # will leave the least significant 10 digits
    terms = (pow(i, i, modulus) for i in range(1, target + 1))
    answer = sum(terms) % modulus
    return answer


expected_answer = 9110846700

solutions.problem48.solve()

Compute the answer to Project Euler’s problem #48