notes.html
problem 51 · 27 lines
<article>
<h3>Problem Analysis</h3>
<p>
The task is to find the smallest <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime number</a> that belongs to an "eight-prime family." A family is built by taking a number, choosing one digit <em>value</em> that appears in it, and replacing every occurrence of that value simultaneously with each of the digits 0 through 9. This yields up to ten candidate numbers; if eight of them are prime, the family qualifies. The crucial modelling insight is that I replace a digit <em>value</em> (for example, all the asterisk-marked 1s in <code>56**3</code>), not an arbitrary subset of positions. That distinction collapses what could otherwise be a search over all subsets of digit positions - exponential in the number of digits - into a tiny linear scan: for each prime I need only try a handful of digit values to replace.
</p>
<p>
A second observation prunes the search further. If a digit value <code>d</code> is the one being replaced, then the largest family that can start with <code>d</code> as its smallest member contains <code>10 - d</code> numbers - I can replace <code>d</code> with <code>d, d+1, ..., 9</code>. To reach a run of <code>prime_run</code> primes I therefore need <code>10 - d >= prime_run</code>, that is <code>d <= 10 - prime_run</code>. For an eight-prime family the replaced digit can only be 0, 1, or 2. I iterate primes in ascending order, so the first match is automatically the smallest, and for each prime I try only the permitted low replacement digits. The overall complexity is roughly O(P * D) where P is the count of primes below <code>10^num_digits</code> and D is the digit length - completely tractable for six-digit numbers.
</p>
<h3>Solution Approach</h3>
<h4>Sieve Generation Plus Digit-Replacement Enumeration (Python and C)</h4>
<p>
Both files implement the same three-phase algorithm and differ only in language idioms.
</p>
<p>
<strong>Phase 1 - prime generation via the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>.</strong> I produce every prime up to <code>10^num_digits</code>. The Sundaram sieve marks composite odd numbers: an odd value <code>2k+1</code> is composite exactly when <code>k = i + j + 2ij</code> for integers <code>1 <= i <= j</code>. Every unmarked index <code>i</code> then yields the prime <code>2i+1</code>, and I prepend <code>2</code> manually. I chose Sundaram as a compact alternative to the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a>; either gives a sorted prime list, which is all I need to scan in order.
</p>
<p>
<strong>Phase 2 - candidate enumeration.</strong> For each prime I convert it to its decimal digit string. I loop over each permitted replaced digit (characters <code>'0'</code> through <code>'0' + (10 - prime_run)</code>, exclusive). If the digit does not appear in the string I skip it - no replacement is possible. Otherwise I substitute every digit from the replaced value up to <code>'9'</code> into all occurrences, building a new number string. I discard any result with a leading zero (which would be a shorter number and not a valid same-length family member), and I count only results that are both prime and <code>>= prime</code>. Counting only forward - members at or above the current prime - ensures families are never double-counted: any smaller member would have triggered the match earlier in the ascending scan.
</p>
<p>
<strong>Phase 3 - primality check.</strong> Each candidate is tested with simple <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> up to its square root. Because I test only individual candidates - not a second full sieve - and the numbers are at most six digits, this is more than fast enough. When the forward count equals <code>prime_run</code>, I return the current prime immediately.
</p>
<p>
<strong>Language-specific differences.</strong> The Python version expresses the replacement family as a generator inside a tuple comprehension and uses <code>str(prime).replace(...)</code> for substitution - concise and idiomatic. The C version uses <code>snprintf</code> to stringify, builds the replaced string with a manual character loop, and uses <code>atoi</code> to convert back. C stores sieve primes in a heap-allocated array (via <code>calloc</code>/<code>malloc</code>) and frees them after use. The algorithm and pruning are identical; only the mechanics differ.
</p>
</article>