Solution

Answer: 44680

We must count the number of sets of primes formed by using each digit $1,\dots,9$ exactly once.

For example,

$${2,5,47,89,631}$$

is valid because:

every element is prime,
the digits $1$ through $9$ are used exactly once overall,
order does not matter because this is a set.

The challenge is to count all such distinct sets.

Mathematical analysis

1. Observations about primes

We concatenate digits to form integers.

A number formed from distinct digits can only be prime if:

it does not end in an even digit,
it does not end in $5$,
it is not divisible by $3$.

The divisibility-by-3 observation is especially important.

For any integer, divisibility by $3$ depends on the sum of digits.

The digits $1$ through $9$ sum to

$$1+2+\cdots+9 = 45.$$

Since $45\equiv 0 \pmod 3$, the entire concatenation is divisible by $3$.

Therefore we cannot place all digits into one prime.

More generally:

any subset of digits whose digit sum is divisible by $3$ cannot form a prime (except the number $3$ itself).

This dramatically prunes the search space.

2. Strategy

We will:

Generate every prime that:

uses distinct digits from $1$–$9$,
uses no digit twice,
contains no zero.

Represent each prime by a bitmask of used digits.
Use recursive search/backtracking to combine disjoint masks until all nine digits are used.
Enforce an ordering condition to avoid counting the same set multiple times.

3. Prime generation

There are only

$$\sum_{k=1}^9 P(9,k)$$

possible digit arrangements, where

$$P(9,k)=\frac{9!}{(9-k)!}.$$

This total is manageable.

For each permutation of length $k$:

convert to integer,
test primality,
store if prime.

4. Avoiding duplicate sets

Suppose we recursively choose primes.

If we allow arbitrary order, then

$${2,5,47}$$

would be counted as:

$2,5,47$
$2,47,5$
$5,2,47$
etc.

To prevent this, we require primes to be selected in increasing order.

Thus each set is generated exactly once.

Python implementation

from itertools import permutations
from math import isqrt

# ------------------------------------------------------------
# Primality test
# ------------------------------------------------------------

def is_prime(n):
    """Return True if n is prime."""
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    if n % 3 == 0:
        return n == 3

    r = isqrt(n)
    f = 5
    while f <= r:
        if n % f == 0 or n % (f + 2) == 0:
            return False
        f += 6
    return True

# ------------------------------------------------------------
# Generate all usable primes
# ------------------------------------------------------------

digits = '123456789'

# primes_by_mask[mask] = list of primes using exactly those digits
primes = []

for length in range(1, 10):
    for perm in permutations(digits, length):

        # quick divisibility-by-3 pruning
        digit_sum = sum(ord(c) - ord('0') for c in perm)
        if digit_sum % 3 == 0:
            # only possible prime is 3 itself
            if not (length == 1 and perm[0] == '3'):
                continue

        # last digit cannot be even or 5
        if perm[-1] in '24568':
            if not (length == 1 and perm[0] in '25'):
                continue

        n = int(''.join(perm))

        if is_prime(n):

            # build bitmask
            mask = 0
            for ch in perm:
                mask |= 1 << (ord(ch) - ord('1'))

            primes.append((n, mask))

# ------------------------------------------------------------
# Sort primes so recursive generation is canonical
# ------------------------------------------------------------

primes.sort()

FULL_MASK = (1 << 9) - 1

answer = 0

# ------------------------------------------------------------
# Backtracking search
# ------------------------------------------------------------

def search(start_index, used_mask):
    """
    Choose increasing primes whose digit masks are disjoint
    until all digits are used.
    """
    global answer

    if used_mask == FULL_MASK:
        answer += 1
        return

    for i in range(start_index, len(primes)):
        p, mask = primes[i]

        # disjoint digit sets only
        if used_mask & mask:
            continue

        search(i + 1, used_mask | mask)

search(0, 0)

print(answer)

Code walkthrough

Primality testing

def is_prime(n):

We use trial division up to $\sqrt n$, optimized with the $6k\pm1$ pattern.

Generating permutations

for length in range(1, 10):
    for perm in permutations(digits, length):

This enumerates every possible number using distinct digits.

Divisibility pruning

digit_sum = ...
if digit_sum % 3 == 0:

If the digit sum is divisible by $3$, the number is divisible by $3$.

The only exception is the single-digit prime $3$.

Last-digit pruning

if perm[-1] in '24568':

Any multi-digit prime ending in an even digit or $5$ is composite.

Bitmask encoding

mask |= 1 << (ord(ch) - ord('1'))

Each digit corresponds to one bit:

digit 1 → bit 0,
digit 2 → bit 1,
...
digit 9 → bit 8.

This lets us test overlap quickly using bit operations.

Recursive search

if used_mask & mask:
    continue

Skip primes sharing digits with already-used primes.

Canonical ordering

search(i + 1, ...)

We only recurse forward through the sorted list, ensuring each set is counted once.

Small-example verification

The example set

$${2,5,47,89,631}$$

works because:

all are prime,
masks are disjoint,
together they cover all digits $1$–$9$.

The recursion would count it exactly once due to increasing order.

Final verification

The count should:

be fairly large because many partitions exist,
but not astronomically huge because primality constraints are strong,
definitely be an integer well below the total number of permutations.

Running the program gives:

$$44680$$

Therefore,

Answer: 44680

Project Euler Problem 118