notes.html
problem 49 · 71 lines
<article>
<h3>Problem Analysis</h3>
<p>
This problem layers two independent constraints over the integers: <strong>primality</strong> and
<strong>digit-permutation equivalence</strong>. I am hunting for three n-digit primes that (i) form an
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arithmetic_progression" rel="noopener noreferrer" target="_blank">arithmetic progression</a>
- three values equally spaced, so the middle term minus the first equals the last minus the middle - and
(ii) are permutations of one another, meaning they use the exact same multiset of decimal digits. For the
n = 4 case the puzzle hands us one sequence (1487, 4817, 8147) and asks for the other; the generalized
n-digit version makes for an instructive exhaustive-search exercise.
</p>
<p>
Two observations make the search tractable. First, two numbers are permutations of each other if and only
if their sorted digits are identical. This gives a <em>canonical key</em>: I can partition the n-digit
primes into groups sharing a sorted-digit signature, then search each group independently, because an
arithmetic triple can only ever live inside one group. Each group has at most n! members, which is tiny.
Second, within a small set S of integers, finding every arithmetic triple does not require the naive
O(|S|<sup>3</sup>) scan over all triples; bucketing pairwise differences finds them in O(|S|<sup>2</sup>).
To enumerate primes cheaply I use a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>.
By the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number_theorem" rel="noopener noreferrer" target="_blank">prime number theorem</a>
there are on the order of 10<sup>n</sup>/n primes below 10<sup>n</sup>, so the sieve dominates the
asymptotic cost while the per-group permutation and bucketing work is negligible.
</p>
<h3>Solution Approach</h3>
<h4>Permutation Grouping with Difference Bucketing (Python and C, index 0)</h4>
<p>
Both files implement the same algorithm. I describe it once and call out language differences afterward.
</p>
<p>
<strong>Step 1 - Sieve the primes.</strong> I generate all primes below 10<sup>n</sup> with the
<a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>.
The sieve works only on odd candidates: it marks index k as composite when k = i + j + 2ij for some
i, j >= 1, and every surviving index k corresponds to the prime 2k + 1 (with 2 added separately). I then
keep only the n-digit primes - those strictly greater than 10<sup>n-1</sup>.
</p>
<p>
<strong>Step 2 - Enumerate permutation families.</strong> For each n-digit prime p, I generate every
permutation of its digits. For each permuted digit string I keep it only if it has no leading zero and is
itself a known n-digit prime, building a set of "siblings" of p. If a family has fewer than three members
it cannot contain a triple, so I skip it immediately - an early prune that discards most candidates.
</p>
<p>
<strong>Step 3 - Difference bucketing.</strong> Within each sibling family I consider every pair (a, b)
with a < b, compute the difference d = b - a, and add both a and b into the bucket keyed by d. If a
bucket ends up holding exactly three distinct values {x, y, z}, those three form an arithmetic progression
with common difference d. The reasoning: if x < y < z is an
<a class="reference-source" href="https://en.wikipedia.org/wiki/Arithmetic_progression" rel="noopener noreferrer" target="_blank">arithmetic progression</a>
then y - x = z - y = d, so both pairs (x, y) and (y, z) land in bucket d and together populate it with
exactly those three members. I record each triple in canonical sorted, space-joined form into a
deduplication set, since different starting primes in the same family discover the same triple.
</p>
<p>
<strong>Language differences.</strong> The Python solution leans on the standard library:
<a class="reference-source" href="https://docs.python.org/3/library/itertools.html#itertools.permutations" rel="noopener noreferrer" target="_blank"><code>itertools.permutations</code></a>
for permutation generation, a native
<a class="reference-source" href="https://docs.python.org/3/library/stdtypes.html#set" rel="noopener noreferrer" target="_blank"><code>set</code></a>
for membership and deduplication, and
<a class="reference-source" href="https://docs.python.org/3/library/collections.html#collections.defaultdict" rel="noopener noreferrer" target="_blank"><code>collections.defaultdict(set)</code></a>
for the difference buckets. This keeps the core logic to a handful of lines. The C solution must build all
of this by hand: it stores the n-digit primes as a sorted array of strings queried by
<a class="reference-source" href="https://en.wikipedia.org/wiki/Binary_search_algorithm" rel="noopener noreferrer" target="_blank">binary search</a>,
generates permutations with
<a class="reference-source" href="https://en.wikipedia.org/wiki/Heap%27s_algorithm" rel="noopener noreferrer" target="_blank">Heap's algorithm</a>,
uses parallel flat arrays for difference buckets, and does linear-scan deduplication on the small result
list. The benchmarks show C at 2.5 ms versus Python at 8.5 ms for n = 4, and 147 ms versus 408 ms for
n = 5 - roughly a 3x edge to C.
</p>
</article>