Problem 118: Pandigital Prime Sets

Mathematical Development

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

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

2. Digit constraint: Each digit 1-9 is used exactly once. The digit 0 is never used.

3. Primality: Each number formed from a subset of digits must be prime.

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.

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$

Result

Exhaustive search yields 44680 distinct sets.

Editorial

The search space is most naturally described by subsets of digits rather than by finished numbers. For every non-empty subset of $\{1,\dots,9\}$, the implementation first generates all permutations of those digits and keeps the ones that are prime. That precomputation turns each subset mask into a ready-made list of admissible prime pieces.

The final count is obtained by depth-first search on the mask of remaining digits. At each step, the search chooses a non-empty submask, tries every prime that can be formed from exactly those digits, and recurses on the unused digits. The key device that makes the objects into sets instead of ordered tuples is the monotonicity condition: each newly chosen prime must be larger than the previous one. That removes duplicate orderings while keeping every valid partition once.

Pseudocode

For every non-empty subset of digits 1 through 9:
    Generate every permutation of those digits.
    Keep the numbers that are prime and store them under that subset mask.

Start a depth-first search from the full digit mask, with the previous prime set to 0.

At each search state:
    If no digits remain, count one complete prime set.
    Otherwise iterate over all non-empty submasks of the remaining digits.
    For each prime stored for that submask that is larger than the previous prime:
        Recurse after removing that submask from the remaining digits.

Return the total number of completed searches.

Complexity Analysis

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.

Answer

#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;
}

"""
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)