Project Euler Problem 211

Solution

Answer: 1922364685

We seek all integers $0<n<64,000,000$ such that

$$\sigma_2(n)=\sum_{d\mid n} d^2$$

is a perfect square, and then sum all such $n$.

---

Mathematical analysis

1. Multiplicativity of $\sigma_2$

For any positive integer $n$ with prime factorization

$$n=\prod p_i^{a_i},$$

the divisor-square sum function is multiplicative:

$$\sigma_2(n)=\prod \left(1+p_i^2+p_i^4+\cdots+p_i^{2a_i}\right).$$

This follows because every divisor of $n$ is formed independently from the prime powers.

For a prime power:

$$\sigma_2(p^a)=1+p^2+p^4+\cdots+p^{2a} =\frac{p^{2(a+1)}-1}{p^2-1}.$$

So if we can compute $\sigma_2(n)$ efficiently for all $n<64\cdot10^6$, we simply test whether the result is a perfect square.

---

2. Efficient sieve computation

A direct factorization of every number up to $64$ million would be too slow in Python.

Instead, we use a divisor sieve.

Observe:

$$\sigma_2(n)=\sum_{d\mid n} d^2.$$

So we may initialize an array:

$$S[n]=0$$

and for every divisor $d$, add $d^2$ to all multiples of $d$.

Pseudo-structure:

for d in range(1, LIMIT):
    d2 = d*d
    for multiple in range(d, LIMIT, d):
        S[multiple] += d2

This is analogous to the sieve of Eratosthenes and runs in approximately

$$N\log N$$

time.

For $N=64,000,000$, this is large but feasible in optimized implementations (especially PyPy / low-level languages).

---

3. Perfect-square testing

For each $n$, after computing $\sigma_2(n)$, we test whether it is a square.

Using integer square root:

$$r = \lfloor \sqrt{\sigma_2(n)} \rfloor$$

and checking:

$$r^2 = \sigma_2(n).$$

In Python:

r = isqrt(value)
if r*r == value:
    ...

The math.isqrt function is exact and avoids floating-point errors.

---

Python implementation

from math import isqrt

LIMIT = 64_000_000

# sigma2[n] will contain σ₂(n)
sigma2 = [0] * LIMIT

# Divisor sieve:
# add d² to every multiple of d
for d in range(1, LIMIT):
    d2 = d * d
    for multiple in range(d, LIMIT, d):
        sigma2[multiple] += d2

# Sum all n for which σ₂(n) is a perfect square
answer = 0

for n in range(1, LIMIT):
    s = sigma2[n]
    r = isqrt(s)
    if r * r == s:
        answer += n

print(answer)

---

Code walkthrough

Array allocation

sigma2 = [0] * LIMIT

Creates storage for all values $\sigma_2(n)$.

---

Outer divisor loop

for d in range(1, LIMIT):

Treat $d$ as a divisor.

---

Compute $d^2$

d2 = d * d

We reuse this value repeatedly.

---

Add contribution to multiples

for multiple in range(d, LIMIT, d):
    sigma2[multiple] += d2

Every multiple of $d$ has $d$ as a divisor, so $d^2$ contributes to its divisor-square sum.

Thus after all loops:

$$\sigma2[n] = \sum_{d\mid n} d^2.$$

---

Perfect square check

r = isqrt(s)
if r * r == s:

Checks exactly whether $s$ is a square.

---

Small-example verification

For $n=10$:

Divisors are:

$$1,2,5,10$$

and

$$\sigma_2(10)=1^2+2^2+5^2+10^2 =1+4+25+100 =130.$$

Since $130$ is not a square, 10 is not counted.

For $n=1$:

$$\sigma_2(1)=1,$$

which is a perfect square, so 1 is included.

The sieve computes these correctly.

---

Final verification

• The computation uses exact integer arithmetic only.
• The sieve guarantees every divisor contribution is counted exactly once.
• isqrt ensures no floating-point inaccuracies.
• The result is known to be relatively sparse, so summing qualifying $n$ is efficient after the sieve.

The final computed value is:

Answer: 1922364685