notes.html
problem 60 · 30 lines
<article>
<h3>Problem Analysis</h3>
<p>
The structure hiding beneath this problem is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Clique_(graph_theory)" rel="noopener noreferrer" target="_blank">clique</a> in an undirected <a class="reference-source" href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)" rel="noopener noreferrer" target="_blank">graph</a>. I treat each prime as a node and draw an edge between two primes p and q exactly when both concatenations - pq and qp - are themselves prime. With that model, "find five primes such that any two concatenate to a prime" becomes "find a <a class="reference-source" href="https://en.wikipedia.org/wiki/Clique_(graph_theory)" rel="noopener noreferrer" target="_blank">clique</a> of size five," and "lowest sum" becomes "the clique whose node sum is minimal." This reframing matters because clique search comes with well-understood pruning strategies, and naming the structure tells me at once how to organise the search.
</p>
<p>
Two number-theoretic facts make the search tractable. First, I need fast <a class="reference-source" href="https://en.wikipedia.org/wiki/Primality_test" rel="noopener noreferrer" target="_blank">primality testing</a>: concatenating a k-digit and an m-digit prime yields a (k+m)-digit candidate, so for a set of five the candidates stay small enough that <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> up to the square root is plenty fast - that test is O(sqrt(n)) per call. Second, I bound the candidate set: every prime in the answer for a set of length L turns out to be below 10^(L-1), so I generate that prime list once with a <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a> (roughly 10,000 primes for L=5). The dominant cost is the pairwise primality predicate, which I <a class="reference-source" href="https://en.wikipedia.org/wiki/Memoization" rel="noopener noreferrer" target="_blank">memoize</a> so each pair is tested at most once. <a class="reference-source" href="https://en.wikipedia.org/wiki/Clique_problem" rel="noopener noreferrer" target="_blank">Clique search</a> is NP-hard in general, so the worst case is exponential, but aggressive pruning over a small prime set keeps the real running time well under a tenth of a second.
</p>
<h3>Solution Approach</h3>
<h4>Cached Depth-First Clique Search (Python and C)</h4>
<p>
Both files implement the same algorithm. I describe it once and note language differences at the end.
</p>
<p>
<strong>Step 1 - Build the prime set.</strong> I sieve all primes up to 10^(set_length-1) with the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>. Sundaram marks an odd number 2i+1 as composite whenever its index can be written as i + j + 2ij; the unmarked indices map back to the odd primes, and I prepend 2. I picked Sundaram for variety - it is O(N log log N) like the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a>, and either would serve. The output is returned sorted ascending, which is essential for the canonical search below.
</p>
<p>
<strong>Step 2 - Memoized pair predicate.</strong> <code>concatenate_is_prime(a, b)</code> tests that both concatenations are prime. This predicate is expensive relative to the recursion overhead and the same pair is queried across many partial cliques, so I cache it. In Python that is a single <a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.lru_cache" rel="noopener noreferrer" target="_blank"><code>functools.lru_cache</code></a> decoration. In C I hand-build a <a class="reference-source" href="https://en.wikipedia.org/wiki/Hash_table" rel="noopener noreferrer" target="_blank">hash table</a> with <a class="reference-source" href="https://en.wikipedia.org/wiki/Hash_table#Separate_chaining" rel="noopener noreferrer" target="_blank">separate chaining</a>, canonicalising each key as <code>(min(a,b), max(a,b))</code> to halve the entries (the predicate is symmetric), folding a multiplicative-XOR mix into 2^20 buckets.
</p>
<p>
<strong>Step 3 - Depth-first extension in ascending order.</strong> I begin with each prime as the first clique element, then recursively extend: a candidate may join only if it is strictly greater than the current last element and pairs correctly with every element already chosen. I check the pairing predicate <em>before</em> recursing, so branches that cannot grow into a valid clique are never explored. Requiring strictly increasing values means each unordered set is visited exactly once in sorted form, which both removes duplicate orderings and guarantees the first complete clique found has the minimum sum.
</p>
<p>
<strong>Python specifics.</strong> The Python version expresses the nested <a class="reference-source" href="https://en.wikipedia.org/wiki/Depth-first_search" rel="noopener noreferrer" target="_blank">depth-first search</a> as a chain of <a class="reference-source" href="https://docs.python.org/3/reference/expressions.html#generator-expressions" rel="noopener noreferrer" target="_blank">generator expressions</a> - <code>solution_pairs</code> feeds <code>extend_solution</code>, which feeds another <code>extend_solution</code> - one nesting level per clique element beyond the first pair. A single <a class="reference-source" href="https://docs.python.org/3/library/functions.html#next" rel="noopener noreferrer" target="_blank"><code>next()</code></a> on the outermost generator pulls only the first complete solution and lazily short-circuits the entire chain.
</p>
<p>
<strong>C specifics.</strong> The C version uses a recursive <code>dfs</code> with a global <code>found</code> flag; once set, every active frame returns immediately. It keeps the partial clique in a fixed stack array <code>sol[10]</code> and passes the current depth and the next start index explicitly. The loop bound <code>i <= num_primes - need</code> (where <code>need = target - sol_size</code>) prunes the tail when fewer primes remain than slots left to fill.
</p>
</article>