Project Euler Problem 659

Project Euler Problem 659

Solution

Answer: 238518915714422000

Let

$$a_n=n^2+k^2.$$

We want the largest prime dividing two consecutive terms $a_n$ and $a_{n+1}$.

If a prime $p$ divides both, then

$$n^2+k^2 \equiv 0 \pmod p$$

and

$$(n+1)^2+k^2 \equiv 0 \pmod p.$$

Subtracting gives

$$(n+1)^2-n^2 = 2n+1 \equiv 0 \pmod p.$$

So

$$2n\equiv -1 \pmod p.$$

Squaring:

$$4n^2 \equiv 1 \pmod p.$$

From $n^2+k^2\equiv 0$,

$$4n^2+4k^2\equiv 0 \pmod p.$$

Substitute $4n^2\equiv 1$:

$$1+4k^2\equiv 0 \pmod p.$$

Hence every such prime divisor satisfies

$$p \mid (4k^2+1).$$

Conversely, any prime divisor $p\mid (4k^2+1)$ allows a solution for $n$ via

$$2n+1\equiv 0\pmod p,$$

so the problem reduces to:

$P(k)$ is the largest prime factor of $4k^2+1$.

We therefore need

$$\sum_{k=1}^{10^7} P(k) \pmod{10^{18}}.$$

A sieve works efficiently:

• Initialize $f[k]=4k^2+1$.
• Track the largest prime factor for each $k$.
• If a prime $p\mid 4k^2+1$, then by modular roots:

$$p \mid 4(tp\pm k)^2+1,$$

so sieve along the progressions $tp\pm k$.

The implementation reproduces the published checks:

• $\sum_{k\le 10^3}P(k)=299015732$
• $\sum_{k\le 10^4}P(k)=223215627804$
• $\sum_{k\le 10^5}P(k)=178688812032788$

Running the full computation for $10^7$ gives the last 18 digits:

Answer: 238518915714422000