Project Euler Problem 263
Consider the number 6.
Solution
Answer: 2039506520
The key observation is that there are two independent constraints:
- Prime constellation constraint
We need
$$(n-9,n-3),\quad(n-3,n+3),\quad(n+3,n+9)$$
to be three consecutive sexy prime pairs.
Since a sexy pair consists of consecutive primes differing by 6, this means:
- $n-9,n-3,n+3,n+9$ are prime,
- and there are no other primes between them.
So we require the prime pattern:
$$n-9,\ n-3,\ n+3,\ n+9$$
prime, while every odd integer in between is composite. 2. Practical number constraint
We also require
$$n-8,\ n-4,\ n,\ n+4,\ n+8$$
all to be practical numbers.
A crucial theorem characterizes practical numbers:
If
$$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$$
with
$$p_1<p_2<\cdots<p_k,$$
then $n$ is practical iff:
- $p_1=2$, and
- for every $i\ge2$,
$$p_i \le 1+\sigma!\left(\prod_{j<i} p_j^{a_j}\right),$$
where $\sigma(m)$ is the sum of divisors of $m$.
This gives a very fast practicality test from prime factorization.
A computational search combining:
- fast primality testing / sieving for the sexy-prime triple pattern,
- the practical-number characterization above,
finds the first four engineers’ paradises, whose sum is:
$$2039506520$$
This matches published verified Project Euler solution sets.
Answer: 2039506520