notes.html

problem 37 · 27 lines

<article>
<h3>Problem Analysis</h3>
<p>
    A <a class="reference-source" href="https://en.wikipedia.org/wiki/Truncatable_prime" rel="noopener noreferrer" target="_blank">truncatable prime</a> is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime number</a> that stays prime as you repeatedly strip digits from one end. Take 3797: it is prime, and so are 797, 97, and 7 (stripping from the left), as well as 379, 37, and 3 (stripping from the right). A number qualifies only if <em>every</em> prefix and <em>every</em> suffix of its decimal representation is also prime. The single-digit primes 2, 3, 5, and 7 are explicitly excluded, so every truncatable prime has at least two digits. The problem guarantees exactly eleven exist, which gives me a clean stopping condition for an open-ended search.
  </p>
<p>
    The observation that unlocks an efficient solution is that truncation is a <em>structural property of the digit string</em>, not an arithmetic relationship. If I keep a running set of every prime I have generated, stored as decimal strings, then testing a candidate reduces to slicing its string at each cut point and asking whether both pieces are already in the set. That converts an apparently expensive recursive primality check into a handful of average-O(1) set lookups. Because truncatable primes are sparse (all eleven lie below one million), a generate-and-test strategy works: stream primes in increasing order, store each one, and test each multi-digit prime until eleven qualify. Generating primes incrementally is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a> variant that runs in roughly O(n log log n) over the range scanned, while holding only about pi(sqrt(n)) entries in memory - where pi is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime-counting_function" rel="noopener noreferrer" target="_blank">prime-counting function</a> - rather than allocating a full boolean array up to an unknown bound.
  </p>
<h3>Solution Approach</h3>
<h4>Incremental Sieve with String-Set Membership Test (Python and C)</h4>
<p>
    Both files implement the same algorithm. I describe it once, then note the language-specific differences.
  </p>
<p>
<strong>Step 1 - Incremental prime generation.</strong> I cannot pre-size a classical <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a> because I do not know in advance how large the eleventh truncatable prime is. Instead I use the dict-based incremental sieve attributed to David Eppstein. A map called <code>composites</code> associates each upcoming composite number with one of its prime factors. The invariant is: by the time I examine candidate <code>n</code>, every composite below <code>n</code> already has an entry. If <code>n</code> is absent from the map, it is prime; I yield it and schedule its first crossing by recording <code>n*n -&gt; n</code>. If <code>n</code> is present, it is composite; I remove its entry, take its prime factor <code>p</code>, and advance to the next odd multiple of <code>p</code> not yet claimed by stepping in increments of <code>2*p</code>. Stepping by <code>2*p</code> keeps the stream on odd multiples and skips all even numbers, which after the initial <code>yield 2</code> can never be prime.
  </p>
<p>
<strong>Step 2 - Maintain the set of prime strings.</strong> The instant a prime is discovered, I convert it to its decimal string and insert it into a set. This is the data-representation decision that makes the whole approach fast: truncation is naturally a string operation, so I pay the integer-to-string conversion exactly once per prime and then work entirely in string space.
  </p>
<p>
<strong>Step 3 - Truncation test.</strong> For a prime string <code>s</code> of length <code>L</code>, I scan cut positions <code>i = 1 .. L-1</code>. At each cut, <code>s[:i]</code> is what remains after right-truncation and <code>s[i:]</code> is what remains after left-truncation. Both must already be in the prime-string set. Because primes are generated in increasing numerical order, and every prefix and suffix of a number is strictly smaller than the number itself, those smaller primes are guaranteed to have been seen and stored already - this ordering guarantee is what makes the membership test sound. The first failing cut rejects the candidate immediately. Single-digit primes are skipped with an explicit guard. Once eleven candidates pass, the loop stops and I return their sum.
  </p>
<p>
<strong>Language differences.</strong> The Python solution expresses the prime stream as a <a class="reference-source" href="https://docs.python.org/3/reference/expressions.html#yield-expressions" rel="noopener noreferrer" target="_blank">yield</a>-based generator and uses Python's built-in <code>dict</code> and <code>set</code>. Its truncation test uses a <code>not any(...)</code> idiom over a comprehension - readable and short-circuiting, though slightly heavier than a hand-written early-exit loop. The C solution re-implements both data structures from scratch: an <a class="reference-source" href="https://en.wikipedia.org/wiki/Open_addressing" rel="noopener noreferrer" target="_blank">open-addressing</a> hash table with linear probing for the integer composites map, and a second hash table of fixed-length character arrays for the prime-string set, hashed with the <a class="reference-source" href="http://www.cse.yorku.ca/~oz/hash.html" rel="noopener noreferrer" target="_blank">djb2</a> function. The C code also guards against integer overflow when computing <code>n*n</code> and handles hash deletion by re-inserting the displaced probe chain. These manual structures are the entire reason for the speed difference; the algorithm is byte-for-byte identical.
  </p>
</article>