Detailed mathematical approach

Problem Summary

An even integer \(n\) is called admissible when it is either a power of \(2\) or, equivalently for even numbers, its distinct prime factors form a consecutive prefix of the prime list \(2,3,5,7,\ldots\). For every admissible \(n < 10^9\), define \(M(n)\) as the smallest integer \(m>1\) such that \(n+m\) is prime. The task is to sum the distinct values of \(M(n)\).

Mathematical Approach

1. Exact shape of admissible numbers

Because \(n\) is even, the first prime \(2\) must appear. If the distinct prime factors are consecutive, then every admissible number has the form

$n = 2^{a_1} 3^{a_2} 5^{a_3} \cdots p_k^{a_k}, \qquad a_i \ge 1.$

The special case "power of \(2\)" is simply the case \(k=1\). So admissible numbers are described completely by choosing a prime prefix and choosing a positive exponent for each prime in that prefix.

This already gives a strong bound on the search space. The product of the first nine primes is

$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870 < 10^9,$

while including the next prime gives

$223092870 \cdot 29 = 6469693230 > 10^9.$

Therefore no admissible number below \(10^9\) can contain \(29\) or any later prime as a distinct factor. The code keeps a slightly longer fixed prime list, but recursion automatically prunes everything beyond the limit.

2. Why the DFS generation is exact

The recursive generator works on the ordered prime list \((2,3,5,7,\ldots)\). Suppose we are currently at prime \(p_i\) with a partial product built from the earlier prefix. The loop repeatedly multiplies by \(p_i\):

$\text{current},\ \text{current}\cdot p_i,\ \text{current}\cdot p_i^2,\ \text{current}\cdot p_i^3,\ldots$

as long as the product stays below the limit. Every time at least one copy of \(p_i\) has been chosen, the recursion may continue to the next prime \(p_{i+1}\).

This does exactly what we need:

Positive exponents. Once a prime is included, it appears with exponent at least \(1\).

Consecutive prefix only. The recursion may move from \(p_i\) to \(p_{i+1}\) only after choosing \(p_i\), so later primes can never appear while skipping an earlier one.

No duplicates. Each exponent vector \((a_1,\ldots,a_k)\) corresponds to one unique recursion path.

So the DFS enumerates every admissible number once and only once, without scanning all even integers up to \(10^9\).

3. Why the pseudo-Fortunate search starts at \(3\)

By definition, \(M(n)\) is the smallest integer \(m>1\) such that \(n+m\) is prime. Since every admissible \(n\) is even, any prime larger than \(2\) has to be odd, so \(m\) must be odd as well. Therefore the candidates are exactly

$m = 3,5,7,9,\ldots$

and the code tests them in increasing order until \(n+m\) is prime.

For example, \(16\) is admissible because it is a power of \(2\). We cannot use \(m=1\) because the definition requires \(m>1\). Then

$16+3 = 19,$

which is prime, so

$M(16)=3.$

Likewise, \(630 = 2\cdot 3^2\cdot 5\cdot 7\) is admissible because its distinct primes are \(2,3,5,7\). Testing odd values gives

$630+3=633,\ 630+5=635,\ 630+7=637,\ 630+9=639,$

all composite, while

$630+11=641$

is prime, hence

$M(630)=11.$

4. Why we need a set of pseudo-Fortunate values

The problem asks for the sum of distinct values \(M(n)\), not the sum over all admissible \(n\). Different admissible numbers can share the same pseudo-Fortunate value, so the implementation inserts each result into a set first:

$\mathcal{M} = \{M(n) : n \text{ admissible},\ n < 10^9\}.$

The final answer is then

$\sum_{m \in \mathcal{M}} m.$

This is mathematically important: without deduplication we would answer a different question.

5. Primality testing is the main inner operation

After admissible numbers have been generated, the expensive repeated task is to test whether \(n+m\) is prime. The code uses deterministic Miller-Rabin for 64-bit integers, so each test is exact in this range and still very fast. That makes the straightforward odd-step search practical.

6. Checkpoints and interpretation

The implementation verifies itself with three simple checks:

$M(16)=3,\qquad M(630)=11,\qquad \text{solve}(10000)=\text{solve\_bruteforce}(10000).$

The first two confirm the pseudo-Fortunate search itself. The third compares the efficient DFS enumeration against a brute-force admissibility test on a smaller limit, which is a strong check that the generator is complete and duplicate-free.

How the Code Works

prime_prefix() provides a fixed initial segment of the prime list. generate_admissible(...) performs the DFS over exponent choices and stores every admissible product in a set. For each stored \(n\), pseudo_fortunate(n) checks odd \(m=3,5,7,\ldots\) until \(n+m\) is prime. These \(M(n)\) values are inserted into another set, and the program sums that set at the end.

Complexity Analysis

Let \(A\) be the number of admissible numbers below the limit, and let \(T(n)\) be the number of odd candidates tested before finding \(M(n)\). Then the total running time is roughly

$O\!\left(A + \sum_{n \in \text{admissible}} T(n)\cdot C_{\text{prime}}\right),$

where \(C_{\text{prime}}\) is the cost of one primality test. Memory usage is \(O(A + |\mathcal{M}|)\) for the two sets. The crucial gain comes from generating only admissible numbers rather than scanning all even numbers up to \(10^9\).

Further Reading

1. Problem page: https://projecteuler.net/problem=293
2. Primorials and prime prefixes: https://en.wikipedia.org/wiki/Primorial
3. Miller-Rabin primality test: https://en.wikipedia.org/wiki/Miller-Rabin_primality_test