Detailed mathematical approach

Problem Summary

The code searches for special integers called engineers' paradises. A candidate \(n\) must satisfy two independent conditions:

1. four consecutive primes centered around \(n\) must form a prime chain with gap 6, and

2. the five numbers \(n-8, n-4, n, n+4, n+8\) must all be practical numbers.

The solver finds the first \(k\) such paradises and sums them.

Mathematical Approach

1. The Prime-Window Filter

The first filter is purely prime-based. The program keeps a sliding window of four consecutive primes \(p_0,p_1,p_2,p_3\) and checks

$p_1-p_0=p_2-p_1=p_3-p_2=6.$

If this holds, then the four primes are exactly

$p_0,\ p_0+6,\ p_0+12,\ p_0+18,$

so the candidate center is

$n=p_0+9.$

Equivalently, the prime pattern is centered at

$n-9,\ n-3,\ n+3,\ n+9.$

This is the expensive combinatorial pattern the code looks for first, because only such windows can possibly produce a paradise.

A concrete miniature example is the first prime window with this shape:

$251,\ 257,\ 263,\ 269.$

It yields the center

$n=251+9=260.$

The practical-number stage then checks

$252,\ 256,\ 260,\ 264,\ 268.$

The first four values are practical, but 268 is not, so 260 is rejected. This shows the full logic of the search: the prime window is only a necessary condition, and the five local practical tests decide whether the candidate is really a paradise.

2. Practical Numbers

A positive integer \(m\) is practical if every integer from \(1\) to \(m\) can be written as a sum of distinct divisors of \(m\).

The code only needs the practical-number test for five nearby values around a candidate \(n\):

$n-8,\ n-4,\ n,\ n+4,\ n+8.$

This is why the candidate must satisfy \(n\ge 9\): otherwise \(n-8\) would be non-positive.

3. Stewart-Sierpiński Criterion

Let a number have prime factorization

$N=\prod_{i=1}^{r} q_i^{a_i},\qquad 2=q_1<q_2<\cdots<q_r.$

Define the prefix product

$A_i=\prod_{j=1}^{i} q_j^{a_j},$

and its divisor sum

$S_i=\sigma(A_i).$

The Stewart-Sierpiński theorem says that \(N\) is practical if and only if \(q_1=2\) and

$q_{i+1}\le S_i+1\qquad(1\le i<r).$

In words: once the first prime factor is 2, every next prime factor must not jump too far beyond the divisor-sum coverage already built by the prefix.

4. Why the Criterion Is Easy to Check Incrementally

The code does not recompute \(\sigma(A_i)\) from scratch at every step. It factors the number in increasing prime order and maintains a running prefix value.

For a prime power,

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

So after factoring \(N\), the solver only needs to multiply the current prefix by \(\sigma(q_i^{a_i})\) and compare the next prime with \(S_i+1\).

A simple worked example shows the idea:

$12=2^2\cdot 3.$

For the prefix \(2^2\),

$S_1=\sigma(2^2)=1+2+4=7,$

and the next prime factor is \(3\), which satisfies \(3\le 7+1\). So 12 is practical.

By contrast,

$14=2\cdot 7$

fails because the prefix after \(2\) is \(S_1=3\), but \(7>3+1\). So 14 is not practical.

5. Why a Brute-Force Cross-Check Exists

The implementation also includes a reference test for practical numbers. It enumerates all divisors, runs a subset-sum style reachability DP, and verifies that every value from 1 to \(n\) is reachable as a sum of distinct divisors.

This slow method is used only for verification on small inputs. The program checks that the Stewart-Sierpiński criterion and the brute-force definition agree for every \(n\le 400\).

This checkpoint is stronger than a casual spot-check. It compares the exact implementation of is_practical against the definition itself for every integer in the whole range \(1\le n\le 400\), so mistakes in factor handling, divisor generation, or subset-sum reachability are caught before the large search starts.

6. Segmented Prime Generation

Prime generation is split into two layers.

First, the code computes all base primes up to \(\sqrt{\text{limit}+9}\) with an ordinary sieve. Those primes are used both for segmented sieving and for factoring candidate numbers.

Then the search range \([3,\text{limit}+9]\) is processed in segments. Each segment stores only odd numbers, so the sieve memory stays small. Segment batches can be processed in parallel, but the primes inside each batch are still handled in increasing order so the sliding window stays correct.

7. The Paradise Search

The function find_paradises reads the prime stream and maintains a deque of the last four primes. Whenever the last four primes satisfy the gap-6 pattern, the code forms the candidate

$n=p_0+9$

and then tests the five practical-number conditions.

If they all pass, the candidate is recorded, added to the running sum, and printed as a found paradise.

The code stops once it has found the requested number of paradises. The first two known values are used as checkpoints:

$219869980,\qquad 312501820.$

8. Candidate Validation and Threading

Threading is used only for segmented sieve batches. Candidate validation itself is kept ordered and deterministic because the prime-window scan is sequential. The helper choose_thread_count caps the number of workers by the workload and the hardware.

This separation is important: the sieve can be parallelized safely, while the window scan must preserve prime order.

How the Code Works

The solver parses options such as --limit, --target, --segment, --threads, --single-thread, and --skip-checkpoints. It builds the base-prime list once, runs the practical-number cross-check up to 400 unless disabled, and then calls find_paradises.

The practical test is implemented in is_practical. The brute-force reference is is_practical_bruteforce. The segmented sieve lives in sieve_segment. The final search loop is a four-prime sliding window in find_paradises.

One subtle detail is that segment batches may be sieved in parallel, but the lambda process_prime still consumes the resulting prime lists in increasing segment order. That preserves the meaning of “four consecutive primes”, which would be broken by an unordered merge.

At the end, the program prints the sum of the first requested paradises and also reports elapsed time.

Complexity Analysis

The ordinary sieve up to \(\sqrt{\text{limit}+9}\) is tiny compared with the full search. The segmented sieve is close to

$O(L\log\log L)$

for limit \(L\), while using only segment-sized working memory. The practical-number test for a candidate factors five nearby numbers and applies the multiplicative criterion, so candidate checks are sparse and relatively cheap.

The brute-force practical-number check is much slower, but it runs only on the small checkpoint range \(1\le n\le 400\). That makes it a safe validator without affecting the main asymptotics.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=263
2. Practical numbers: Wikipedia - Practical number
3. Stewart-Sierpiński theorem: Wikipedia - Characterization of practical numbers
4. Segmented sieve: Wikipedia - Segmented sieve
5. Prime factorization and divisor sums: Wikipedia - Divisor function