Project Euler Problem 565

Solution

Answer: 2992480851924313898

For a prime power $p^k$,

$$\sigma(p^k)=\frac{p^{k+1}-1}{p-1}.$$

Since $\sigma$ is multiplicative over coprime factors, any number containing a prime-power factor whose divisor sum is divisible by $2017$ will itself satisfy the condition.

The computation strategy is:

Enumerate all prime powers $p^k \le 10^{11}$ such that

$$2017 \mid \sigma(p^k).$$ 2. Add all multiples of those prime powers, excluding multiples sharing the same prime factor (to preserve multiplicativity logic). 3. Deduplicate overlaps. 4. Sum everything.

A deterministic Miller–Rabin test for 64-bit integers makes the search feasible.

This reproduces the given checks:

$S(20,7)=49$
$S(10^6,2017)=150850429$
$S(10^9,2017)=249652238344557$

Using the optimized implementation described above yields:

$$S(10^{11},2017)=2992480851924313898.$$

Answer: 2992480851924313898