Problem Analysis
This problem layers two independent constraints over the integers: primality and digit-permutation equivalence. I am hunting for three n-digit primes that (i) form an arithmetic progression - 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.
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 canonical key: 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|3) scan over all triples; bucketing pairwise differences finds them in O(|S|2). To enumerate primes cheaply I use a Sieve of Sundaram. By the prime number theorem there are on the order of 10n/n primes below 10n, so the sieve dominates the asymptotic cost while the per-group permutation and bucketing work is negligible.
Solution Approach
Permutation Grouping with Difference Bucketing (Python and C, index 0)
Both files implement the same algorithm. I describe it once and call out language differences afterward.
Step 1 - Sieve the primes. I generate all primes below 10n with the Sieve of Sundaram. 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 10n-1.
Step 2 - Enumerate permutation families. 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.
Step 3 - Difference bucketing. 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 arithmetic progression 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.
Language differences. The Python solution leans on the standard library:
itertools.permutations
for permutation generation, a native
set
for membership and deduplication, and
collections.defaultdict(set)
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
binary search,
generates permutations with
Heap's algorithm,
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.