Project Euler

Pandigital Prime Sets

Using all of the digits 1 through 9 exactly once, and concatenating them to form individual numbers, how many distinct sets of primes can be formed?

Source sync Apr 19, 2026

Problem #0118

Level Level 05

Solved By 8,174

Languages C++, Python

Answer 44680

Length 346 words

modular_arithmeticnumber_theorysearch

Using all of the digits $1$ through $9$ and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set $\{2,5,47,89,631\}$, all of the elements belonging to it are prime.

How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?

Problem 118: Pandigital Prime Sets

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Answer

\boxed{44680}

Mathematical Analysis

Approach

We need to partition the digits $\{1, 2, \ldots, 9\}$ into groups, form a number from each group (considering all permutations of digits within the group), check if each resulting number is prime, and count the distinct sets (not sequences) of primes.

Key Observations

Order within sets does not matter: We count sets, not ordered tuples. To avoid counting permutations of the same set, we enumerate partitions in increasing order of the numbers.
Digit constraint: Each digit 1-9 is used exactly once. The digit 0 is never used.
Primality: Each number formed from a subset of digits must be prime.

Editorial

We use backtracking with bitmask. We represent the set of remaining digits as a 9-bit mask. We then at each step, enumerate subsets of the remaining digits, form all permutations of those digits, check if the resulting number is prime, and if so, recurse with the remaining digits. Finally, to ensure we count sets (not ordered tuples), we require that each subsequent number is strictly larger than the previous one.

Pseudocode

Represent the set of remaining digits as a 9-bit mask
At each step, enumerate subsets of the remaining digits, form all permutations of those digits, check if the resulting number is prime, and if so, recurse with the remaining digits
To ensure we count sets (not ordered tuples), we require that each subsequent number is strictly larger than the previous one

Pruning

A number with digit sum divisible by 3 cannot be prime (unless it is 3 itself).
Even numbers greater than 2 are not prime.
Single-digit primes from {1,…,9}: 2, 3, 5, 7.

Complexity

The number of subsets of 9 elements is $2^9 = 512$ . For each subset, we permute the digits (at most $9! = 362880$ in the worst case, but subsets are small). The total search space is manageable due to pruning.

Result

Exhaustive search yields 44680 distinct sets.

C++ project_euler/problem_118/solution.cpp

#include <bits/stdc++.h>
using namespace std;

// Miller-Rabin primality test for numbers up to ~10^9
bool is_prime(long long n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int digits[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// For each bitmask of digits, store all primes formable from those digits
map<int, vector<long long>> mask_primes;

void gen_perms(int mask, vector<int>& ds, int idx, long long num, vector<long long>& primes) {
    if (idx == (int)ds.size()) {
        if (is_prime(num)) primes.push_back(num);
        return;
    }
    for (int i = idx; i < (int)ds.size(); i++) {
        swap(ds[i], ds[idx]);
        gen_perms(mask, ds, idx + 1, num * 10 + ds[idx], primes);
        swap(ds[i], ds[idx]);
    }
}

void precompute() {
    // Enumerate all non-empty subsets of {1..9} (bitmask over 9 bits)
    for (int mask = 1; mask < 512; mask++) {
        vector<int> ds;
        int dsum = 0;
        for (int i = 0; i < 9; i++) {
            if (mask & (1 << i)) {
                ds.push_back(i + 1);
                dsum += (i + 1);
            }
        }
        // Pruning: if digit sum divisible by 3 and subset has >1 digit or the single digit is not 3
        // Actually, just compute all primes and filter
        vector<long long> primes;
        gen_perms(mask, ds, 0, 0, primes);
        // Remove duplicates and sort
        sort(primes.begin(), primes.end());
        primes.erase(unique(primes.begin(), primes.end()), primes.end());
        if (!primes.empty()) {
            mask_primes[mask] = primes;
        }
    }
}

int answer = 0;

void solve(int remaining_mask, long long last_prime) {
    if (remaining_mask == 0) {
        answer++;
        return;
    }
    // Enumerate all non-empty subsets of remaining_mask
    for (int sub = remaining_mask; sub > 0; sub = (sub - 1) & remaining_mask) {
        auto it = mask_primes.find(sub);
        if (it == mask_primes.end()) continue;
        for (long long p : it->second) {
            if (p > last_prime) {
                solve(remaining_mask ^ sub, p);
            }
        }
    }
}

int main() {
    precompute();
    solve(511, 0); // 511 = (1<<9)-1, all 9 digits available
    cout << answer << endl;
    return 0;
}

Python project_euler/problem_118/solution.py

"""
Problem 118: Pandigital Prime Sets

Find the number of distinct sets of primes that use each digit 1-9 exactly once.
"""

from itertools import permutations

def isprime(n):
    """Deterministic primality test for n up to ~10^9."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def solve():
    # Precompute: for each bitmask of digits {1..9}, find all primes
    mask_primes = {}

    for mask in range(1, 512):
        digits = []
        for i in range(9):
            if mask & (1 << i):
                digits.append(i + 1)

        primes = set()
        for perm in permutations(digits):
            num = int(''.join(map(str, perm)))
            if isprime(num):
                primes.add(num)

        if primes:
            mask_primes[mask] = sorted(primes)

    # DFS: partition all 9 digits into sets forming primes in increasing order
    count = 0

    def dfs(remaining, last_prime):
        nonlocal count
        if remaining == 0:
            count += 1
            return

        # Enumerate non-empty subsets of remaining
        sub = remaining
        while sub > 0:
            if sub in mask_primes:
                for p in mask_primes[sub]:
                    if p > last_prime:
                        dfs(remaining ^ sub, p)
            sub = (sub - 1) & remaining

    dfs(511, 0)
    return count

answer = solve()
assert answer == 44680
print(answer)