Project Euler Problem 48 Solution: Self Powers

Project Euler Problem 48 Statement

The series, $1^1 + 2^2 + 3^3 + \cdots + 10^{10} = 10405071317$.

Find the last ten digits of the series, $1^1 + 2^2 + 3^3 + \cdots + 1000^{1000}$.

Solution

For each number $n$, we sum $n^n \text{ mod } d$ using Python's built-in function pow(n, n, d). This function efficiently uses modular exponentiation, which is significantly faster than directly calculating the full number. For instance, $99^{99}$ is a massive 198 digit number, but modular arithmetic reduces it to manageable size by focusing on the last 10 digits.

The final modulo $d$ operation ensures we only retain the last 10 digits of the sum.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 48

HackerRank Project Euler 48 increases the limit to 1 ≤ N ≤ 2 × 10⁶.

Python Source Code

N = int(input())
d = 10**10    # last 10 digits of the series
print ((sum(pow(n, n, d) for n in range(1, N+1))) % d)

Last Word

It maintains correctness by using properties of modular arithmetic: (a × b) mod n = ((a mod n) × (b mod n)) mod n