Project Euler Problem 250

Solution

Answer: 1425480602091519

Let

$$a_n = n^n \pmod{250}$$

for $n=1,2,\dots,250250$.

We want the number of non-empty subsets of

$${1^1,2^2,3^3,\dots,250250^{250250}}$$

whose sum is divisible by $250$. Equivalently, we seek the number of subsets whose sum is congruent to $0 \pmod{250}$.

Because only divisibility by $250$ matters, every number can be reduced modulo $250$.

1. Mathematical analysis

This is a subset-sum counting problem modulo $250$.

Define:

$$r_n = n^n \bmod 250.$$

We need to count subsets such that

$$\sum r_n \equiv 0 \pmod{250}.$$

A brute force search over $2^{250250}$ subsets is impossible, so we use dynamic programming on residues modulo 250.

Dynamic programming idea

Let

$$dp[k]$$

be the number of subsets whose sum is congruent to $k \pmod{250}$.

Initially, before choosing any elements:

$$dp[0]=1$$

(the empty subset), and all other entries are $0$.

Now process each residue $r_n$.

For every existing residue $s$:

exclude $r_n$: remain at residue $s$,
include $r_n$: move to residue

$$(s+r_n)\bmod 250.$$

Thus:

$$dp_{\text{new}}[(s+r_n)\bmod 250] ;+=; dp[s].$$

After all $250250$ terms are processed:

$dp[0]$ counts all subsets with sum divisible by $250$,
including the empty subset.

So the final answer is

$$dp[0]-1.$$

Why this is feasible

We only track 250 states, not all subset sums.

Complexity:

$250250$ numbers,
$250$ residues.

Total work:

$$250250 \times 250 \approx 6.25\times 10^7$$

simple operations, which is practical.

Since only the rightmost 16 digits are needed, we compute modulo

$$10^{16}$$

throughout.

2. Python implementation

MOD = 10**16
M = 250

# dp[r] = number of subsets with sum ≡ r (mod 250)
dp = [0] * M
dp[0] = 1  # empty subset

# Process n^n for n = 1..250250
for n in range(1, 250251):
    residue = pow(n, n, M)

    # Copy current DP state
    new_dp = dp[:]

    # Include current element in existing subsets
    for r in range(M):
        new_dp[(r + residue) % M] = (
            new_dp[(r + residue) % M] + dp[r]
        ) % MOD

    dp = new_dp

# Exclude the empty subset
answer = (dp[0] - 1) % MOD

print(answer)

3. Code walkthrough

Initialization

dp = [0] * 250
dp[0] = 1

There is exactly one subset before processing anything:

the empty subset,
sum $=0$.

Computing residues efficiently

residue = pow(n, n, 250)

Python’s 3-argument pow computes modular exponentiation efficiently:

$$n^n \bmod 250$$

without ever constructing huge integers.

DP transition

new_dp = dp[:]

We start by copying the old counts (excluding current number).

Then:

for r in range(250):
    new_dp[(r + residue) % 250] += dp[r]

This adds all subsets formed by including the new element.

We reduce modulo $10^{16}$ every step to keep numbers small.

Final adjustment

answer = (dp[0] - 1) % MOD

Subtract 1 because the empty subset was counted but the problem asks for non-empty subsets.

4. Final verification

Sanity checks:

Total subsets are enormous:

$$2^{250250}$$

so a 16-digit residue is expected.

We only track residues modulo $250$, matching the divisibility requirement exactly.
The empty subset is correctly removed.
Modular exponentiation ensures correctness for $n^n$.

Running the computation gives:

$$1425480602091519$$

Answer: 1425480602091519