Detailed mathematical approach

Problem Summary

We must use the digits \(1,2,\dots,9\) exactly once in total, split them into several decimal integers, and require every resulting integer to be prime. The goal is to count how many sets of primes are possible, so the collection \(\{23,461,5879\}\) is the same set regardless of the order in which its members are discovered.

The brute-force view is enormous: every ordered string of distinct digits might be one block in the partition, and a full solution must somehow organize all compatible prime blocks into unordered covers of \(\{1,\dots,9\}\). The implementations solve this by separating the problem into two layers: first generate every prime whose digits are distinct and taken from \(1\) through \(9\), then count exact covers of the digit set with a memoized recurrence.

Mathematical Approach

The decisive mathematical objects are the family of admissible prime blocks and a recurrence on the remaining digit set. Once those are identified, the whole problem becomes a small exact-cover dynamic program on \(2^9\) masks.

The Candidate Prime Family

Let \(\mathcal{P}\) be the set of all primes whose decimal expansion uses distinct digits drawn from \(\{1,\dots,9\}\). For each \(p\in\mathcal{P}\), let \(D(p)\subseteq\{1,\dots,9\}\) be the set of digits appearing in \(p\).

Every valid pandigital prime set is therefore a collection \(\{p_1,\dots,p_r\}\subseteq\mathcal{P}\) such that

$D(p_1)\sqcup D(p_2)\sqcup\cdots\sqcup D(p_r)=\{1,\dots,9\},$

where \(\sqcup\) denotes disjoint union. So the original problem is equivalent to counting all exact covers of the digit set by digit-disjoint members of \(\mathcal{P}\).

The recursive generator used in the implementations produces \(\mathcal{P}\) directly: start from the empty string, append one unused digit at a time, and whenever the current prefix is prime, store it as an admissible block. Because every ordered sequence of distinct digits is reached exactly once, every possible prime block appears exactly once in this search tree.

The Set-Counting Recurrence

For any subset \(S\subseteq\{1,\dots,9\}\), define \(F(S)\) to be the number of pandigital prime sets that use exactly the digits in \(S\). The target is \(F(\{1,\dots,9\})\), and the empty set has the natural base value

$F(\varnothing)=1,$

because there is exactly one way to cover no digits: choose no more primes.

Now let \(m(S)=\min S\), the smallest remaining digit. In any valid partition of \(S\), exactly one prime block contains that digit. This gives the recurrence

$F(S)=\sum_{\substack{p\in\mathcal{P}\\ D(p)\subseteq S\\ m(S)\in D(p)}} F\bigl(S\setminus D(p)\bigr).$

This is the key invariant behind the code. It removes duplicate counting without imposing any ordering on prime values: every unordered prime set has a unique first step, namely the block that contains the smallest still-uncovered digit. The implementations realize the same idea with a bitmask and its least significant set bit.

Why This Counts Sets Rather Than Sequences

Suppose a valid solution is the set \(\{p_1,\dots,p_r\}\). If we tried to build it by freely choosing the next block, the same set would appear in \(r!\) different orders. The anchor rule avoids that completely. At the top level, the chosen block must be the unique one containing digit \(1\). After removing that block, the next chosen block must be the unique one containing the smallest digit not yet used, and so on.

So every valid set determines exactly one path through the recurrence, and every path clearly reconstructs a valid set of digit-disjoint primes. That proves a bijection between solutions and recursion paths.

The Search Space Is Large but Fixed

The prime generator explores every non-empty ordered string of distinct digits from \(1\) through \(9\). The exact number of such prefixes is

$\sum_{k=1}^{9} P(9,k)=\sum_{k=1}^{9}\frac{9!}{(9-k)!}=986409.$

Only a small fraction survive the primality test; for the full problem the candidate list contains 43089 admissible primes. Also, no 9-digit candidate can survive, because every permutation of \(1,\dots,9\) has digit sum \(45\) and is therefore divisible by \(9\). Once the candidate list is known, the counting phase has only \(2^9=512\) remaining-digit states.

Worked Example: Digits \(1,2,3,4\)

The smaller instance on digits \(\{1,2,3,4\}\) is useful because the same recurrence already shows the whole mechanism. Here the smallest remaining digit is always the anchor digit \(1\) at the top level. The admissible prime blocks containing \(1\) are

$13,\ 31,\ 41,\ 241,\ 421,\ 431,\ 1423,\ 2143,\ 2341,\ 4231.$

The first two leave the digit set \(\{2,4\}\), which has no prime cover, so those branches contribute \(0\). The others give

$\begin{aligned} F(\{1,2,3,4\})={}&F(\{2,3\})+F(\{3\})+F(\{3\})+F(\{2\}) \\ &+F(\varnothing)+F(\varnothing)+F(\varnothing)+F(\varnothing). \end{aligned}$

Now \(F(\{3\})=1\) because \(\{3\}\) itself is prime, \(F(\{2\})=1\), and

$F(\{2,3\})=F(\{3\})+F(\varnothing)=2,$

coming from the covers \(\{2,3\}\) and \(\{23\}\). Therefore

$F(\{1,2,3,4\})=2+1+1+1+1+1+1+1=9.$

The nine corresponding sets are \(\{2,3,41\}\), \(\{23,41\}\), \(\{3,241\}\), \(\{3,421\}\), \(\{2,431\}\), \(\{1423\}\), \(\{2143\}\), \(\{2341\}\), and \(\{4231\}\). This is exactly the checkpoint used by the parameterized implementation before it runs the full \(1\) through \(9\) case.

How the Code Works

Generating the Prime Blocks

The C++, Python, and Java implementations first enumerate digit strings recursively. Starting from value \(0\) and an empty used-digit mask, they append one unused digit to the right, forming a new decimal prefix. Whenever that prefix is prime, the implementation stores the pair consisting of the prime value and the mask of digits used by that value. The recursion then continues, because a prime prefix can still be extended into a longer prime built from additional unused digits.

After generation, the candidate list is normalized to unique pairs before the counting stage. Conceptually, this list is just the finite set \(\mathcal{P}\) together with the digit set \(D(p)\) attached to each member.

Memoized Counting on Masks

The second phase replaces digit subsets by 9-bit masks. A mask represents the digits that still need to be covered. The empty mask returns \(1\). For any non-empty mask, the implementation extracts its least significant set bit, which is the smallest remaining digit, and scans the stored prime blocks. A block contributes only if its digit mask is a subset of the remaining mask and also contains the anchor bit.

Whenever those two conditions hold, the code removes that block's digits from the remaining mask and recurses. The result is memoized by mask, so each remaining-digit state is solved once. This is a direct bit-level implementation of the recurrence for \(F(S)\) above.

Primality Testing in the Three Languages

The C++ and Java implementations use straightforward trial division up to \(\sqrt{n}\). That is sufficient here because every candidate is less than \(10^9\), so \(\sqrt{n}\lt 31623\). The Python implementation uses a library primality routine, but the surrounding combinatorics and the mask recurrence are the same in all three languages.

Complexity Analysis

Candidate generation visits exactly 986409 non-empty digit prefixes. If we write \(T_{\mathrm{prime}}(x)\) for the cost of one primality test at magnitude \(x\), the generation phase is

$O\!\left(\sum_{k=1}^{9} P(9,k)\cdot T_{\mathrm{prime}}(10^k)\right).$

In the concrete implementations, trial division makes \(T_{\mathrm{prime}}(10^k)=O(10^{k/2})\) in C++ and Java, while Python delegates this step to its primality library.

After that, the dynamic program has only 512 memo states. The stored candidate list has 43089 prime blocks, and each state performs a linear scan through that list with constant-time mask tests. So the counting phase is \(O(512\cdot 43089)\) simple compatibility checks for the full problem, with memory \(O(512+43089)\).

More generally, if the digit set were \(\{1,\dots,n\}\), the same method would use \(2^n\) memo states and enumerate \(\sum_{k=1}^{n} P(n,k)\) candidate prefixes. For \(n=9\), that fixed search space is small enough that this exact-cover approach is entirely practical.

Footnotes and References

1. Problem page: Project Euler 118
2. Prime number: Wikipedia - Prime number
3. Pandigital number: Wikipedia - Pandigital number
4. Backtracking: Wikipedia - Backtracking
5. Dynamic programming: Wikipedia - Dynamic programming
6. Trial division: Wikipedia - Trial division