Problem 118: Pandigital Prime Sets

Project Euler Problem 118 Solution

EulerSolve provides an optimized solution for Project Euler Problem 118, Pandigital Prime Sets, with C++, Python, Java, and a step-by-step mathematical explanation.

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$....

Detailed mathematical approach

Problem Summary

Each of the nine digits $1,2,\dots,9$ must be used exactly once; there is no digit $0$. We split the digits into groups, put the digits of every group into some order, and read each group as a decimal integer. In the statement's example $\{2,5,47,89,631\}$ the five numbers together use every digit exactly once, and all of them are prime. We must count the distinct sets of primes that can be formed in this way. A set has no order: $\{631,89,47,5,2\}$ is the example set again, while $\{2,5,47,89,613\}$ is a different set, because $613$ is a different prime. ^[1] Written one after another, the primes of a valid set form a nine-digit number with each of the digits $1$ to $9$ exactly once, a zeroless pandigital number, which explains the title. ^[2] Apart from the example, the statement gives no checkpoint value.

The whole solution in one sentence: list every prime whose digits are different and nonzero together with the set of digits it uses, then count the ways to cover the nine digits with these digit sets, always deciding first which prime holds the smallest digit not yet covered, so that every set of primes is built in exactly one way.

Mathematical Approach

We count small cases by hand, find two school rules that decide most cases at a glance, turn the count into a sum over the ways to split the digits into groups, and evaluate that sum with a short recursion that remembers its results.

1. Fewer digits first

Let $F_k$ be the number of sets for the digits $1$ to $k$ only, so that the problem asks for $F_9$. For small $k$ we ask which number contains the digit $1$, because some number has to contain it.

$k=1$: the only possible number is $1$, which is not prime, so $F_1=0$.
$k=2$: the digit $1$ lies in $1$, $12$ or $21$. The first is not prime, $12$ is even and $21=3\cdot7$, so $F_2=0$.
$k=3$: the digit $1$ lies in one of the primes $13$ and $31$, or in a number that fails: $1$, $12$, $21$, or an arrangement of $1,2,3$, which is always a multiple of $3$, as Section 3 explains. After $13$ or $31$ the digit $2$ is left, and $2$ is prime. So $F_3=2$, with the sets $\{2,13\}$ and $\{2,31\}$.
$k=4$: there are nine sets, $\{1423\}$, $\{2143\}$, $\{2341\}$, $\{4231\}$, $\{3,241\}$, $\{3,421\}$, $\{2,431\}$, $\{23,41\}$ and $\{2,3,41\}$. Section 7 derives this list systematically.

A computer continues the table: for $k=1,2,\dots,8$ the counts are

$0,\ 0,\ 2,\ 9,\ 24,\ 77,\ 1205,\ 4076.$

Two things stand out. Sets made of a single prime occur for $k=4$, the four primes above, and for $k=7$, where $534$ of the $1205$ sets consist of one seven-digit prime, but for no other $k\le8$. And the counts grow quickly but irregularly, so instead of a formula we need a good way to count.

2. Counting arrangements directly

Any set of primes can be written as a row of the nine digits with cuts between some neighbours, for example $2|5|47|89|631$. Conversely, an ordering of the nine digits together with a choice of cuts gives a list of numbers. An ordering of all nine digits is a permutation, and there are $9!=362880$ of them; ^[3] each of the $8$ gaps between neighbouring digits is cut or not, which gives $2^8=256$ choices. A direct search therefore looks at $92897280$ rows with cuts and keeps those in which every piece is prime.

This search finds every set many times. A set of $r$ primes can be written in $r!$ orders, the number of ways to line up $r$ different objects, and each order gives a different row with cuts; the example set with its five primes appears $5!=120$ times. Since $r$ differs from set to set, no single division repairs the count: for the digits $1$ to $4$, $18$ of the $192$ rows with cuts have only prime pieces, $\{2,3,41\}$ appears in $3!=6$ of them and $\{23,41\}$ in two, but there are only $9$ sets. A simple remedy is to keep only the rows whose pieces increase from left to right, such as $2|5|47|89|631$, because every set has exactly one increasing order. This search serves as an independent check at the end of this article.

3. Two divisibility rules

The first rule is about the digit sum. The number $10$ leaves the remainder $1$ after division by $3$, so $100=10\cdot10$, $1000$ and every other power of ten leave the remainder $1$ as well. A number such as $631=6\cdot100+3\cdot10+1$ therefore leaves the same remainder after division by $3$ as $6+3+1=10$, namely $1$. In general a number and the sum of its digits leave the same remainder after division by $3$, and also after division by $9$, since $10$ leaves the remainder $1$ after division by $9$ too. ^[4] The digit sum does not depend on the order of the digits. So if the digits of a group add up to a multiple of $3$, then every number formed from that group is a multiple of $3$, and it can be prime only if it is $3$ itself.

The digits $1$ to $9$ add up to $45=5\cdot9$, so a number that uses all nine digits is a multiple of $9$ and never prime: every valid set has at least two primes. The same happens for the digits $1$ to $k$ whenever $1+2+\dots+k$ is a multiple of $3$. For $k=1,\dots,9$ these sums are $1,3,6,10,15,21,28,36,45$, and only $1$, $10$ and $28$ are not multiples of $3$; for $k=1$ the only number is $1$, which is not prime. This is exactly why the single-prime sets of Section 1 appear only for $k=4$ and $k=7$.

The second rule is about the last digit. A number with at least two digits that ends in $2$, $4$, $6$ or $8$ is even and larger than $2$, and one that ends in $5$ is a multiple of $5$ larger than $5$. ^[4] So a prime with at least two digits ends in $1$, $3$, $7$ or $9$, and a group of two or more digits taken only from $2,4,5,6,8$ never forms a prime, whatever the order.

4. Only the digit set of a prime matters

For a nonempty set $S$ of digits, let $c(S)$ be the number of primes whose digits are exactly the elements of $S$, each used once. For the subsets of $\{1,2,3,4\}$:

$c(\{2\})=c(\{3\})=1$, from the primes $2$ and $3$;
$c(\{1,3\})=2$, from $13$ and $31$; $c(\{1,4\})=1$, from $41$; $c(\{2,3\})=1$, from $23$; $c(\{3,4\})=1$, from $43$;
$c(\{1,2,4\})=2$, from $241$ and $421$, and $c(\{1,3,4\})=1$, from $431$;
$c(\{1,2,3,4\})=4$, from $1423$, $2143$, $2341$ and $4231$;
$c(S)=0$ for the other six sets: $1$ and $4$ are not prime, the digits of $\{1,2\}$, $\{1,2,3\}$ and $\{2,3,4\}$ add up to $3$, $6$ and $9$, and $\{2,4\}$ only gives the even numbers $24$ and $42$.

We call a digit set live if $c(S)\gt0$ and dead otherwise. Of the $2^9-1=511$ nonempty subsets of the nine digits, a computer finds $308$ live ones, and the rules of Section 3 explain almost all of the $203$ dead ones: of the $175$ subsets whose digit sum is divisible by $3$, all except $\{3\}$ are dead; another $18$ consist of at least two digits from $2,4,5,6,8$; and the single digits $1$, $4$ and $8$ are not prime. Only $8$ dead sets escape these rules; one of them is $\{4,9\}$, because $49=7^2$ and $94$ is even.

In total $43089$ primes have different nonzero digits. The largest value of $c$ is $c(\{1,2,3,4,5,6,7,9\})=4333$, but each of these primes leaves only the digit $8$, which is not prime; only $25337$ of the $43089$ primes occur in at least one valid set.

5. From sets of primes to splits of the digits

A partition of a set splits it into nonempty groups, called blocks, so that every element lies in exactly one block. ^[5] For example, $\{1,3,6\}$, $\{2\}$, $\{4,7\}$, $\{5\}$, $\{8,9\}$ is a partition of the nine digits. A valid set of primes gives a partition: the digit sets of its primes are nonempty, no digit occurs twice, and every digit occurs. In addition, it picks for every block $T$ one of the $c(T)$ primes with exactly the digits of $T$. Conversely, a partition with one such prime for each block gives a valid set, and different choices give different sets, because a set determines its partition and the prime in each block. The primes of a valid set have disjoint digits, so they are automatically different numbers. Therefore

$$F_9=\sum_{\pi}\ \prod_{T\in\pi}c(T),$$

where $\pi$ runs over all partitions of $\{1,\dots,9\}$ and $T$ over the blocks of $\pi$. For the partition above, the product is $c(\{1,3,6\})\cdot1\cdot1\cdot1\cdot1=3$, because $163$, $613$ and $631$ are the three primes with the digits $1$, $3$ and $6$: besides the example, the sets $\{2,5,47,89,163\}$ and $\{2,5,47,89,613\}$ belong to the same partition.

The number of partitions of a set of $n$ elements is the Bell number $B_n$. The first ones, for $n=0,1,\dots,9$, are $1,1,2,5,15,52,203,877,4140,21147$. ^[6] So the sum has $21147$ terms, but only $832$ of them are not zero, because a single dead block makes the whole product $0$. For the digits $1$ to $4$, only $5$ of the $15$ partitions survive: $\{1,2,3,4\}$ with the product $4$; $\{1,2,4\},\{3\}$ with $2\cdot1=2$; $\{1,3,4\},\{2\}$ with $1$; $\{1,4\},\{2,3\}$ with $1$; and $\{1,4\},\{2\},\{3\}$ with $1$. Indeed $4+2+1+1+1=9$.

6. The anchor rule

Listing all partitions works here, but there is a neater way to organise the sum. For a set $S$ of digits, let $F(S)$ be the number of sets of primes that use exactly the digits of $S$, each once; by Section 5 it is the sum of the products of $c(T)$ over the partitions of $S$. We put $F(\varnothing)=1$: the empty set of digits is covered in exactly one way, by choosing no prime at all. Now look at the smallest digit $a$ of a nonempty set $S$, which we call the anchor. In every partition of $S$, exactly one block $T$ contains $a$, and the other blocks form a partition of what is left, $S\setminus T$. So

$$F(S)=\sum_{\substack{T\subseteq S\\ a\in T}}c(T)\,F(S\setminus T).$$

In words: the prime that contains the anchor is chosen first, in $c(T)$ ways for each possible digit set $T$, and the rest is a smaller problem of the same kind. Every set of primes is produced exactly once, because the order of the choices is forced: first the prime that contains the smallest digit, then the prime that contains the smallest digit not yet used, and so on. For the statement's example the steps are $631$, which contains $1$; then $2$; then $47$, which contains $4$, the smallest digit left; then $5$; and finally $89$. Without the anchor rule, a set of $r$ primes would be produced $r!$ times, once in every order.

When every $c(T)$ equals $1$, the recurrence counts all partitions, and it becomes the classical recurrence of the Bell numbers,

$$B_{n+1}=\sum_{j=0}^{n}\binom{n}{j}B_j,$$

proved in the same way: the block of the first element leaves $j$ of the other $n$ elements, which can be chosen in $\binom nj$ ways and split into blocks in $B_j$ ways. ^[7] Our problem is also an exact cover problem: from a collection of digit sets, choose some that contain every digit exactly once. Knuth's Algorithm X finds all solutions of such a problem by a depth-first search that repeatedly picks an element not yet covered, by any fixed rule, and tries every set that covers it; ^[8] the anchor rule is the rule "take the smallest digit not yet covered".

7. Worked example: the digits 1 to 4

For $S=\{1,2,3,4\}$ the anchor is $1$, and $T$ runs over the eight subsets that contain $1$. Three of them are dead, namely $\{1\}$, $\{1,2\}$ and $\{1,2,3\}$, so five terms remain:

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

The smaller values come from the same rule. $F(\{3\})=F(\{2\})=1$, since $3$ and $2$ are prime. For $\{2,3\}$ the anchor is $2$: either one prime holds both digits, which is $23$, or the prime $2$ is followed by $F(\{3\})=1$; so $F(\{2,3\})=1+1=2$, from the sets $\{23\}$ and $\{2,3\}$. For $\{2,4\}$ the anchor $2$ lies either in $24$ or $42$, both even, or in the prime $2$, which leaves $\{4\}$ with $F(\{4\})=0$; so $F(\{2,4\})=0$. With the values of $c$ from Section 4,

$$\begin{aligned}F(\{1,2,3,4\})&=2\cdot0+1\cdot2+2\cdot1\\&\quad+1\cdot1+4\cdot1=9.\end{aligned}$$

The five terms are the nine sets of Section 1. The primes $13$ and $31$ lead to the dead end $\{2,4\}$; $41$ gives $\{23,41\}$ and $\{2,3,41\}$; $241$ and $421$ give $\{3,241\}$ and $\{3,421\}$; $431$ gives $\{2,431\}$; and the four primes with all four digits are sets on their own. This value is also the checkpoint of the C++ program.

8. Remembering results

Different paths of the recursion often arrive at the same remaining set. After $631$ and $2$ the set $\{4,5,7,8,9\}$ is left, and the same set is left after $613$ and $2$, after $163$ and $2$, or after $61$ and $23$. Its value should be computed only once. Breaking a problem into smaller subproblems of the same kind and storing the solution of every subproblem in a table, so that it is looked up instead of computed again, is called dynamic programming; the storing is called memoisation. ^[9]

The remaining set is all that has to be remembered, because the primes that can still be chosen depend only on the digits left, not on the primes chosen before. Its size alone would not do: $F(\{1,2\})=0$, but $F(\{1,3\})=2$. A rule such as "choose the primes in increasing order" would also have to remember the last prime chosen; the anchor rule needs nothing beyond the remaining set.

There are only $2^9=512$ subsets of the digits, so the table is tiny. Starting from all nine digits, the recursion actually reaches only $209$ nonempty remaining sets. For instance, the only reachable set that still contains the digit $1$ is the full set, because the first prime chosen always contains $1$.

9. Digit sets as bit patterns

A computer stores a set of digits as a number whose binary digits say which digits are present: the digit $d$ contributes $2^{d-1}$. So $\{1,3,6\}$ becomes $1+4+32=37$, written $100101$ in binary, and the set of all nine digits becomes $511=2^9-1$. Set operations then take one or two operations on these numbers:

$T$ is a subset of $S$ exactly when the bitwise AND of the two masks equals the mask of $T$;
if $T\subseteq S$, the mask of $S\setminus T$ is the bitwise exclusive or of the two masks; without the subset test, the exclusive or would switch on the digits of $T$ that are not in $S$;
the anchor is the lowest binary $1$ of the mask, and the expression s & -s keeps exactly that bit of a mask s.

The last trick works because of how computers store negative numbers, in two's complement: $-s$ is obtained by flipping every binary digit of $s$ and adding $1$. ^[10] Flipping turns the zeros below the lowest $1$ of $s$ into ones and that $1$ into a zero; adding $1$ turns those ones back into zeros and carries into the zero, which becomes a $1$ again, and the carry stops there. So $-s$ agrees with $s$ up to and including its lowest $1$ and is flipped above it, and the AND keeps only the lowest $1$. ^[11] For $S=\{2,4,5\}$ the mask is $26=11010_2$, and the AND of $26$ and $-26$ is $2=10_2$, the bit of the digit $2$.

In the example of Section 6 the primes $631$, $2$, $47$, $5$ and $89$ have the masks $37$, $2$, $72$, $16$ and $384$. Starting from $511$, removing these masks one after another by exclusive or leaves $474$, $472$, $400$, $384$ and finally $0$.

10. Generating the candidate primes

The primes and their digit sets come from a search over all strings of different nonzero digits. Starting from the empty string, we append one unused digit at a time, like a family tree in which the children of a string are the strings that extend it by one digit. The search follows one branch to its end before it returns and tries the next digit; this way of visiting a tree is a depth-first search, the scheme behind backtracking. ^[12] There are $9\cdot8\cdots(10-k)=9!/(9-k)!$ strings of length $k$, ^[3] that is,

$9,\ 72,\ 504,\ 3024,\ 15120,$
$60480,\ 181440,\ 362880,\ 362880$

for $k=1,\dots,9$, and $986409$ in total. Every string is reached exactly once, along the path of its own beginnings, and different strings are different numbers, since there is no digit $0$ that could hide at the front; so no prime is listed twice. The search abandons no branch, unlike most backtracking searches, and primality could not guide it: a string that is not prime can grow into a prime, as $4$ grows into $41$, and a prime can grow into a multiple of $3$, as $23$ grows into $231=3\cdot7\cdot11$. The strings of length $9$ could be skipped, since by Section 3 none of them is prime, but the programs test them anyway. The numbers of primes among the strings of length $1$ to $8$ are $4$, $20$, $83$, $395$, $1610$, $5045$, $12850$ and $23082$, which gives the $43089$ primes of Section 4.

11. Testing primality by trial division

To decide whether a candidate $n$ is prime, the C++ and Java programs use trial division. If $n=ab$ with $1\lt a\le b$, then $a\cdot a\le a\cdot b=n$, so a composite number always has a divisor $a\gt1$ with $a^2\le n$, and its smallest such divisor is prime. It is therefore enough to try the divisor $2$ and then the odd numbers $3,5,7,\dots$ as long as their square does not exceed $n$. ^[13] A divisor whose square equals $n$ is tried as well, so that $49=7^2$ is caught at $7$, and the square is compared with $n$ in whole numbers, so no rounded square root is involved. Odd numbers like $9$ are tried needlessly, since a candidate divisible by $9$ would already have been rejected at $3$, but this does no harm.

A prime has to be tried all the way up to its square root: the largest candidate prime, $98765431$, needs the $4968$ odd divisors from $3$ to $9937$. Most other candidates stop at once: $754825$ of the $943320$ candidates that are not prime, among them all $362880$ nine-digit strings, are even or multiples of $3$. Besides the tests for evenness, the $986409$ candidates need $124862951$ trial divisions, and $99923266$ of them, about $80\%$, are spent on the $43089$ primes. The Python program uses SymPy's isprime instead, which first looks for small factors and then applies tests that are exact in their range, among them deterministic Miller–Rabin tests; its documentation guarantees the answer for numbers below $2^{64}$. ^[14]

12. How large can a set be?

By Section 3 every set has at least two primes, and two can be enough: a one-digit prime $q$ together with a prime made of the other eight digits. Their digit sum $45-q$ is a multiple of $3$ for $q=3$, so $q$ is $2$, $5$ or $7$; with $4192$, $4097$ and $3194$ such eight-digit primes, $11483$ sets have this shape.

At the other end, a set has at most six primes. Its one-digit primes come from $2,3,5,7$, and each of its longer primes ends in $1$, $3$, $7$ or $9$ by Section 3, every one in a different digit. Each of the digits $3$ and $7$ is used once, either as a one-digit prime or somewhere in a longer prime, so the number of longer primes plus the number of one-digit primes among $3$ and $7$ is at most $4$, the size of $\{1,3,7,9\}$. Adding the one-digit primes $2$ and $5$ gives at most $6$. Exactly five sets reach this bound:

$\{2,3,5,7,89,461\}$, $\{2,3,5,7,89,641\}$, $\{2,3,5,41,67,89\}$, $\{2,3,5,47,61,89\}$ and $\{2,5,7,43,61,89\}$.

In each of them $2$ and $5$ stand alone, and each of $1,3,7,9$ is a one-digit prime or the last digit of a longer prime, as equality requires.

13. Pitfalls

A digit set may hold several primes, as $\{1,3,6\}$ holds $163$, $613$ and $631$: counting partitions into live blocks alone, or keeping only one prime per digit set, undercounts.
The number $1$ is not prime, so the digit $1$, like $4$, $6$, $8$ and $9$, always sits inside a longer prime.
The empty remainder must count as one way, $F(\varnothing)=1$; with $0$ there, every count would be $0$.

How the Code Works

The C++ program ^[15] works in two phases, the search of Section 10 and the recursion of Section 6. main first reads the options with parse_arguments: --max-digit=k restricts the digits to $1,\dots,k$ for $1\le k\le9$, with $9$ as the default, and --skip-checkpoints skips the self-check; any other argument, or a value such as $0$ or $10$, ends the program with exit status $1$. Only a number too large for an int is not reliably rejected, because parse_int_after_prefix accumulates the digits without an overflow check. Unless it is skipped, run_checkpoints verifies that the count for the digits $1$ to $4$ is $9$, the value of Section 7, and the program stops with exit status $2$ if it is not. Finally the program prints count_sets(max_digit).

count_sets first calls generate_primes_rec. Its arguments are the set of used digits as a bit mask, used_mask, and the number formed so far, value. If value is positive and prime, the pair of value and mask is stored as a PrimeEntry; then the function calls itself once for every unused digit d, with the bit of d added to the mask and the value value * 10 + d. The values are unsigned 32-bit integers, which is enough because no string exceeds $987654321\lt2^{32}$. is_prime is the trial division of Section 11; it compares $p^2$ with $n$ in 64-bit arithmetic, so the square cannot overflow for any 32-bit input. The list is then sorted, and duplicate entries are erased with std::unique. By Section 10 there are none: the list has $43089$ entries before and after this step, which is only a safeguard.

The counting phase is the recursion of Section 6 on the bit masks of Section 9. The table memo has $2^k$ cells of 64-bit integers, all set to $-1$, which means "not computed yet"; a computed value can be $0$, as for $\{2,4\}$, so $0$ could not serve as this mark. The recursive lambda dfs receives the mask remaining_mask of the digits still to be covered. It returns $1$ for the empty mask, which is $F(\varnothing)=1$, and the stored value if there is one. Otherwise it computes the anchor bit remaining_mask & -remaining_mask and scans the whole list of primes: an entry is skipped if its mask does not contain the anchor bit or is not contained in the remaining mask, and otherwise the value of dfs for remaining_mask ^ e.mask is added. Every prime with the digit set $T$ is one of the $c(T)$ terms of Section 6, so the scan adds $c(T)\,F(S\setminus T)$ for every $T$ without building a table of $c$. The lambda calls itself through its first parameter, self.

The Python program follows the same plan for the digits $1$ to $9$, without options or checkpoint; it imports permutations without using it. Its primality test is SymPy's isprime. It removes duplicates by converting the list into a set before sorting, stores the results of dfs in a dictionary, and takes the anchor as remaining & (-remaining). This works for Python's unbounded integers too, because Python computes bitwise operations as if numbers were written in two's complement with infinitely many sign bits. ^[16] Its recursions are at most ten calls deep, so Python's recursion limit is no concern. The Java program mirrors the C++ program for the digits $1$ to $9$: isPrime is the same trial division with the square computed as a long, gen collects arrays {value, mask}, and duplicates are removed with a HashSet of the keys ((long)e[0]<<16)|e[1], built from the value e[0] and the mask e[1]. The cast to long makes the shift 64-bit, so the whole value sits above the nine bits of the mask and different pairs get different keys; a 32-bit shift would keep only the last $16$ bits of the value, and the primes $153427$ and $743251$, which use the same digits and differ by $9\cdot2^{16}$, would collide. The list is not sorted, which does not affect the count. Its dfs stores the results in an array of $512$ long values. In all three languages the candidates fit into 32-bit integers. The counts are 64-bit integers, or Python's unbounded ones, far more than needed: every set of primes gives at least one row with cuts of its digits, and no digit set has more than the $92897280$ rows of Section 2.

Complexity and Verification

The first phase dominates. It visits the $986409$ strings of Section 10 and tests every one of them; one trial division test costs at most about $\sqrt n/2$ divisions, and the measured total is the $124862951$ divisions of Section 11. The counting phase handles $209$ remaining sets; for each of them it scans all $43089$ entries, $9005601$ scans in all, and the recursion makes $44957$ calls, most of which return at once, because the remaining set is empty or its value is already stored. Memory is the list of $43089$ pairs and the memo: $512$ cells in C++ and Java, a dictionary that ends up with $209$ entries in Python. On a desktop computer the C++ program takes about $0.1$ seconds, the Java program about $0.15$ seconds including the start of the virtual machine, and the Python program about one second, $0.7$ seconds of which go into the search for primes.

A grouped version with a table of $c(T)$ would need, for each remaining set $S$, only the $2^{|S|-1}$ subsets $T\subseteq S$ that contain the anchor, $2568$ terms over the $209$ sets that the recursion meets. Over all $511$ nonempty sets it would be $(3^9-1)/2=9841$ terms: a pair $T\subseteq S$ puts each digit outside $S$, in $T$ or in $S\setminus T$, which gives $3^9$ pairs, and for every nonempty $S$ half of its subsets contain the anchor. For nine digits the difference does not matter; for $k$ digits the number of strings to test grows like $k!$ and the table like $2^k$, so the method suits small digit sets.

The C++ program checks itself on the digits $1$ to $4$ before the main count. For this article, all three programs were run and print the same number. With --max-digit=k the C++ program gives the values $0,0,2,9,24,77,1205,4076$ of Section 1 for $k=1,\dots,8$. Four independent computations, which share no code with the solutions, agree with the programs for every $k\le9$: the direct search of Section 2 over all permutations and cuts with increasing pieces, using a sieve of Eratosthenes, which finds all primes up to a bound by crossing out the multiples of every prime; ^[17] the sum over all partitions of Section 5; a backtracking search that picks primes in increasing order; and a count that takes the primes one at a time and decides for each whether to use it, keeping for every set of digits the number of ways to cover it with the primes seen so far; each new prime adds the entry of every set disjoint from its digits to that of their union. For nine digits the direct search runs over all $92897280$ rows with cuts with a sieve up to $987654321$, and the partition sum over all $21147$ partitions; the partition sum also gives the same $F(S)$ as the recursion for all $512$ subsets $S$ of the digits, not only for $\{1,\dots,k\}$. A separately written deterministic Miller–Rabin test agrees with SymPy's isprime on all $986409$ candidates, and the statistics of Sections 4, 10 and 12 come from these computations.

Footnotes and References

The references below supply the background facts used above; the correspondence with partitions, the anchor recurrence, the dead digit sets and the bound of six primes are derived in this article.

Project Euler 118 — Pandigital Prime Sets. The official statement: using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed, and in the example {2, 5, 47, 89, 631} all elements are prime. The task asks how many distinct sets containing each of the digits one through nine exactly once contain only prime elements.
Wikipedia — Pandigital number. A pandigital number contains each digit of its base at least once; a number that contains each of the digits 1 to 9 but no 0, such as 923456781, is called a zeroless pandigital number.
Wikipedia — Permutation. The number of permutations of n distinct objects is n!. A k-permutation of n is an ordered arrangement of k elements chosen from n, and there are n(n − 1)⋯(n − k + 1) = n!/(n − k)! of them.
Wikipedia — Divisibility rule. A number is divisible by 2 if its last digit is even, by 5 if its last digit is 0 or 5, and by 3 or 9 if the sum of its digits is; the article derives the digit-sum rule from the fact that all powers of 10 are congruent to 1 modulo 3.
Wikipedia — Partition of a set. A partition of a set X is a set of nonempty subsets of X, called blocks, parts or cells, such that every element of X lies in exactly one of them. The number of partitions of an n-element set is the Bell number Bₙ.
OEIS A000110 — Bell or exponential numbers. The number of ways to partition a set of n labelled elements; the sequence begins 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, so a set of nine elements has 21147 partitions.
Wikipedia — Bell number. The Bell numbers count the partitions of a set and satisfy B₍ₙ₊₁₎ = Σ C(n, k) Bₖ over k = 0, …, n, which the article explains by removing the block that contains the first element.
Wikipedia — Knuth's Algorithm X. Algorithm X finds all solutions of an exact cover problem by a depth-first search: it chooses a column of a 0–1 matrix deterministically and then tries every row with a 1 in that column. Any systematic rule for choosing the column finds all solutions.
Wikipedia — Dynamic programming. Dynamic programming simplifies a complicated problem by breaking it down into simpler sub-problems in a recursive manner. Their solutions can be memoised, that is, stored in a table that is checked before a sub-problem is solved.
Wikipedia — Two's complement. The negative of a number in two's complement is obtained by inverting all bits and adding 1. A shortcut gives the same result: copy the bits from the least significant end up to and including the first 1, and flip all remaining bits.
Wikipedia — Find first set. The expression x & −x clears all but the least significant 1 bit of x, that is, it isolates the lowest set bit.
Wikipedia — Backtracking. Backtracking builds candidates for the solutions step by step and abandons a partial candidate as soon as it cannot be completed to a valid solution; it traverses the tree of partial candidates recursively, from the root down, in depth-first order.
Wikipedia — Trial division. Trial division need not test divisors beyond the square root of n, because a composite number has at least one factor not larger than its square root; multiples of divisors already tested, such as 4 after 2, cannot divide when those divisors did not.
SymPy — isprime. isprime(n) first looks for trivial factors, uses bisection search on its sieve when the sieve is large enough, and for small numbers performs deterministic Miller–Rabin tests with bases known to have no counterexamples in their range; for n < 2⁶⁴ the answer is definitive.
C++ — Euler118.cpp. The linked immutable C++ revision contains parse_arguments, is_prime, generate_primes_rec, count_sets and run_checkpoints, with the options --max-digit= and --skip-checkpoints. It is the implementation record for this article.
Python — Bitwise operations on integer types. The result of bitwise operations is calculated as though carried out in two's complement with an infinite number of sign bits.
Wikipedia — Sieve of Eratosthenes. The sieve finds all primes up to a given bound by marking, for every prime p, the multiples of p, starting from p².

Problem 118 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u32 = std::uint32_t;
using i64 = std::int64_t;

struct Options {
    int max_digit = 9;
    bool run_checkpoints = true;
};

struct PrimeEntry {
    u32 value = 0;
    int mask = 0;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--max-digit=", options.max_digit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.max_digit >= 1 && options.max_digit <= 9;
}

bool is_prime(u32 n) {
    if (n < 2) {
        return false;
    }
    if ((n % 2U) == 0U) {
        return n == 2;
    }
    for (u32 p = 3; static_cast<std::uint64_t>(p) * p <= n; p += 2) {
        if ((n % p) == 0U) {
            return false;
        }
    }
    return true;
}

void generate_primes_rec(const int max_digit,
                         int used_mask,
                         u32 value,
                         std::vector<PrimeEntry>& entries) {
    if (value > 0 && is_prime(value)) {
        entries.push_back({value, used_mask});
    }

    for (int d = 1; d <= max_digit; ++d) {
        const int bit = 1 << (d - 1);
        if ((used_mask & bit) != 0) {
            continue;
        }
        generate_primes_rec(max_digit, used_mask | bit, value * 10U + static_cast<u32>(d), entries);
    }
}

i64 count_sets(const int max_digit) {
    std::vector<PrimeEntry> entries;
    entries.reserve(50000);
    generate_primes_rec(max_digit, 0, 0, entries);

    std::sort(entries.begin(), entries.end(), [](const PrimeEntry& a, const PrimeEntry& b) {
        if (a.value != b.value) {
            return a.value < b.value;
        }
        return a.mask < b.mask;
    });
    entries.erase(std::unique(entries.begin(), entries.end(), [](const PrimeEntry& a, const PrimeEntry& b) {
                      return a.value == b.value && a.mask == b.mask;
                  }),
                  entries.end());

    const int full_mask = (1 << max_digit) - 1;
    std::vector<i64> memo(static_cast<std::size_t>(1 << max_digit), -1);

    const auto dfs = [&](auto&& self, int remaining_mask) -> i64 {
        if (remaining_mask == 0) {
            return 1;
        }
        i64& memo_cell = memo[static_cast<std::size_t>(remaining_mask)];
        if (memo_cell != -1) {
            return memo_cell;
        }

        const int anchor_bit = remaining_mask & -remaining_mask;
        i64 total = 0;

        for (const PrimeEntry& e : entries) {
            if ((e.mask & anchor_bit) == 0) {
                continue;
            }
            if ((e.mask & remaining_mask) != e.mask) {
                continue;
            }
            total += self(self, remaining_mask ^ e.mask);
        }

        memo_cell = total;
        return total;
    };

    return dfs(dfs, full_mask);
}

bool run_checkpoints() {
    if (count_sets(4) != 9) {
        std::cerr << "Checkpoint failed for digits 1..4" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << count_sets(options.max_digit) << '\n';
    return 0;
}

Python

# Problem 118: Pandigital prime sets
# Count sets of pandigital (1-9) primes.

from sympy import isprime
from itertools import permutations

def solve():
    # Generate all primes using digits 1-9 (each exactly once)
    # Then count partitions
    entries = []
    
    def gen_primes(used_mask, value):
        if value > 0 and isprime(value):
            entries.append((value, used_mask))
        for d in range(1, 10):
            bit = 1 << (d - 1)
            if used_mask & bit: continue
            gen_primes(used_mask | bit, value * 10 + d)
    
    gen_primes(0, 0)
    entries = list(set(entries))
    entries.sort()
    
    full_mask = (1 << 9) - 1
    memo = {}
    
    def dfs(remaining):
        if remaining == 0: return 1
        if remaining in memo: return memo[remaining]
        anchor = remaining & (-remaining)
        total = 0
        for val, mask in entries:
            if not (mask & anchor): continue
            if (mask & remaining) != mask: continue
            total += dfs(remaining ^ mask)
        memo[remaining] = total
        return total
    
    print(dfs(full_mask))

solve()

Java

import java.util.*;

public class Euler118 {
    static boolean isPrime(int n) {
        if(n<2)return false;if(n%2==0)return n==2;
        for(int p=3;(long)p*p<=n;p+=2)if(n%p==0)return false;
        return true;
    }
    static List<int[]> entries = new ArrayList<>();
    static void gen(int mask, int val) {
        if(val>0&&isPrime(val))entries.add(new int[]{val,mask});
        for(int d=1;d<=9;d++){int bit=1<<(d-1);if((mask&bit)!=0)continue;gen(mask|bit,val*10+d);}
    }
    public static void main(String[] args) {
        gen(0,0); int full=(1<<9)-1;
        Set<Long> seen = new HashSet<>(); List<int[]> unique = new ArrayList<>();
        for(int[] e:entries){long key=((long)e[0]<<16)|e[1];if(seen.add(key))unique.add(e);}
        entries=unique; long[] memo=new long[1<<9]; Arrays.fill(memo,-1);
        System.out.println(dfs(full,memo));
    }
    static long dfs(int rem, long[] memo) {
        if(rem==0)return 1;if(memo[rem]!=-1)return memo[rem];
        int anchor=rem&(-rem);long tot=0;
        for(int[] e:entries){if((e[1]&anchor)==0)continue;if((e[1]&rem)!=e[1])continue;tot+=dfs(rem^e[1],memo);}
        return memo[rem]=tot;
    }
}