Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 291: Panaitopol Primes

Project Euler Problem 291 Solution

EulerSolve provides an optimized solution for Project Euler Problem 291, Panaitopol Primes, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We must count the prime values of $Q_n=2n^2+2n+1=n^2+(n+1)^2$ under the bound $Q_n \lt \text{LIMIT}=5\cdot 10^{15}$. Testing each value independently would be far too slow, so the solution uses a sieve specialized to this quadratic family. Mathematical Approach 1. Bounding the index range The sequence is strictly increasing for $n\ge 1$, so it is enough to search indices $1\le n\le m,\qquad m=\max\{n: 2n^2+2n+1\lt \text{LIMIT}\}.$ Solving the quadratic inequality gives the approximation $m\approx \left\lfloor \frac{\sqrt{2\cdot \text{LIMIT}-1}-1}{2}\right\rfloor,$ and the code then adjusts by a couple of integer checks to respect the strict inequality. 2. Why every sequence prime generates two residue classes Assume $p=Q_i$ is prime. Then, modulo $p$, $Q_n-Q_i=2(n-i)(n+i+1).$ Since $Q_i\equiv 0 \pmod p$, we obtain $Q_n\equiv 0\pmod p \iff 2(n-i)(n+i+1)\equiv 0\pmod p.$ Because $p$ is odd, $2$ is invertible modulo $p$, so the only roots are $\boxed{n\equiv i\pmod p \quad \text{or}\quad n\equiv -i-1\pmod p.}$ The second class is the same symmetry as $Q_{-n-1}=Q_n.$ 3. Worked example of the residue classes Take $i=1$....

Detailed mathematical approach

Problem Summary

We must count the prime values of

$Q_n=2n^2+2n+1=n^2+(n+1)^2$

under the bound $Q_n \lt \text{LIMIT}=5\cdot 10^{15}$. Testing each value independently would be far too slow, so the solution uses a sieve specialized to this quadratic family.

Mathematical Approach

1. Bounding the index range

The sequence is strictly increasing for $n\ge 1$, so it is enough to search indices

$1\le n\le m,\qquad m=\max\{n: 2n^2+2n+1\lt \text{LIMIT}\}.$

Solving the quadratic inequality gives the approximation

$m\approx \left\lfloor \frac{\sqrt{2\cdot \text{LIMIT}-1}-1}{2}\right\rfloor,$

and the code then adjusts by a couple of integer checks to respect the strict inequality.

2. Why every sequence prime generates two residue classes

Assume $p=Q_i$ is prime. Then, modulo $p$,

$Q_n-Q_i=2(n-i)(n+i+1).$

Since $Q_i\equiv 0 \pmod p$, we obtain

$Q_n\equiv 0\pmod p \iff 2(n-i)(n+i+1)\equiv 0\pmod p.$

Because $p$ is odd, $2$ is invertible modulo $p$, so the only roots are

$\boxed{n\equiv i\pmod p \quad \text{or}\quad n\equiv -i-1\pmod p.}$

The second class is the same symmetry as

$Q_{-n-1}=Q_n.$

3. Worked example of the residue classes

Take $i=1$. Then $Q_1=5$, so any term divisible by $5$ must satisfy

$n\equiv 1 \pmod 5 \quad \text{or}\quad n\equiv -2\equiv 3 \pmod 5.$

Indeed,

$Q_1=5,\qquad Q_3=25,\qquad Q_6=85,\qquad Q_8=145,$

and all of them are divisible by $5$. This is exactly what the sieve marks: not arbitrary indices, but two arithmetic progressions per prime factor.

4. The residual-factor sieve invariant

The code initializes an array

$V_n=Q_n.$

When it reaches index $i$, all prime factors already discovered earlier have already been divided out from every affected $V_n$. So the current residual $V_i$ is either $1$ or a new prime factor that still has to be propagated.

This is why the program can safely use

$p:=V_i$

as the next sieving factor. It then walks through the two progressions

$n=i+kp,\qquad n\equiv -i-1\pmod p,$

marks those indices as composite, and repeatedly divides $p$ out of their residual values. The repeated division is important: for example $Q_3=25$ must lose both powers of $5$, not just one.

5. Why an unmarked index is prime

If index $i$ is still unmarked when visited, no earlier prime factor has hit it. Therefore the original number $Q_i$ has no smaller prime divisor coming from the sequence sieve, so $Q_i$ itself is prime and contributes to the answer. This is why the code increments the count exactly when composite[i] == 0.

6. A useful number-theoretic side fact

From

$4Q_n-1=(2n+1)^2$

we get

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

for every odd prime divisor $p\mid Q_n$. So $-1$ is a quadratic residue modulo $p$, which implies $p\equiv 1\pmod 4$. This explains why the prime divisors of the family are highly structured.

7. Checkpoints

The implementation checks the sieve against brute force on smaller limits:

$\text{solve}(1000)=10,\qquad \text{solve}(10^6)=175.$

After those validations it computes the required value

$\text{solve}(5\cdot 10^{15})=4037526.$

How the Code Works

The program first computes the maximum valid index $m$, initializes values[n] = Q_n, and keeps a boolean composite array. Then it scans $i=1,2,\dots,m$. If composite[i] is false, it counts $Q_i$ as prime. Regardless of that flag, it looks at the current residual values[i]; if it is greater than $1$, that residual is propagated through the two arithmetic progressions determined by $i$ modulo that factor, and the factor is removed from every hit.

Complexity Analysis

Memory usage is $O(m)$, where $m\approx \sqrt{\text{LIMIT}/2}$. The running time is sieve-like: each discovered factor updates two progressions of step $p$, so the total work is vastly smaller than performing an independent primality test on every $Q_n$. In practice this turns a prohibitively large quadratic-polynomial search into a manageable structured sieve.