Problem 41: Pandigital Prime

Mathematical Development

Definitions

Definition 1. For $n \in \{1, 2, \ldots, 9\}$, an $n$-pandigital number is a positive integer whose decimal representation is a permutation of the digits $\{1, 2, \ldots, n\}$.

Definition 2. The digit sum of the $n$-pandigital class is $S(n) = \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.

Theoretical Development

Theorem 1 (Divisibility by 3). An $n$-pandigital number is divisible by $3$ if and only if $3 \mid S(n)$. In particular, every $n$-pandigital number is divisible by $3$ for $n \in \{2, 3, 5, 6, 8, 9\}$.

Proof. Let $N$ be an $n$-pandigital number with decimal digits $a_1, a_2, \ldots, a_n$. By the standard divisibility rule for $3$, we have $N \equiv \sum_{i=1}^n a_i \pmod{3}$. Since $\{a_1, \ldots, a_n\}$ is a permutation of $\{1, \ldots, n\}$, the digit sum equals $S(n) = n(n+1)/2$ for every $n$-pandigital number. Hence $3 \mid N$ if and only if $3 \mid S(n)$.

We compute $S(n) \bmod 3$:

For $n \in \{2,3,5,6,8,9\}$, we have $3 \mid S(n)$, so every $n$-pandigital number is divisible by $3$. Since every $n$-pandigital number with $n \geq 2$ exceeds $3$, it is composite. $\square$

Lemma 1. No $1$-pandigital prime exists.

Proof. The unique $1$-pandigital number is $1$, which is not prime by the convention that primes are integers $p \geq 2$ with no positive divisors other than $1$ and $p$. $\square$

Theorem 2 (Admissible values of $n$). The only values of $n$ for which an $n$-pandigital prime can exist are $n = 4$ and $n = 7$.

Proof. By Lemma 1, $n = 1$ is excluded. By Theorem 1, $n \in \{2,3,5,6,8,9\}$ forces every $n$-pandigital number to be composite. The remaining candidates are $n = 4$ and $n = 7$, for which $S(n) \equiv 1 \pmod{3}$. Division by $3$ is not automatically forced, so primes may exist among these classes. $\square$

Remark. Theorem 2 does not guarantee that pandigital primes exist for $n = 4$ or $n = 7$; it merely asserts these are the only candidates. Existence is established computationally in Theorem 3.

Theorem 3. The largest pandigital prime is $7652413$.

Proof. By Theorem 2, it suffices to search among $7$-pandigital and $4$-pandigital numbers. Since every $7$-pandigital number exceeds every $4$-pandigital number (the smallest $7$-pandigital number is $1234567 > 4321$), we search $7$-pandigital numbers first in lexicographically descending order.

There are $7! = 5040$ permutations of $\{1,2,3,4,5,6,7\}$. The largest is $7654321$. We enumerate permutations in descending lexicographic order and apply a primality test to each. The first prime encountered is $7652413$.

Verification of primality. We have $\lfloor \sqrt{7652413} \rfloor = 2766$. By trial division, checking all primes $p \leq 2766$, we confirm that $p \nmid 7652413$ for every such $p$. Therefore $7652413$ is prime.

Since $7652413$ is the first prime encountered in the descending enumeration of $7$-pandigital numbers, it is the largest $7$-pandigital prime, and hence the largest pandigital prime overall. $\square$

Editorial

By the divisibility argument, only $7$-pandigital and $4$-pandigital numbers need to be considered. We enumerate the corresponding digit permutations in descending lexicographic order, first for $\{1,2,\ldots,7\}$ and then for $\{1,2,3,4\}$, convert each permutation into its integer value, and apply a primality test. Because every $7$-pandigital number exceeds every $4$-pandigital number and the enumeration is descending within each class, the first prime encountered is the largest pandigital prime.

Pseudocode

Algorithm: Largest Pandigital Prime
Require: The digit sets {1, 2, 3, 4} and {1, 2, ..., 7}.
Ensure: The largest pandigital prime.
1: For each admissible digit length m in the order 7, then 4, do:
2:     Enumerate the m-digit pandigital permutations in descending lexicographic order.
3:     Convert each permutation pi to its integer value p.
4:     If p is prime, return p.
5: Return failure if no candidate survives.

Complexity Analysis

Proposition (Time complexity). The algorithm terminates in $O(n! \cdot \sqrt{N_{\max}})$ time in the worst case, where $n \leq 7$ and $N_{\max} = 7654321$.

Proof. In the worst case, we enumerate all $7! = 5040$ permutations. For each permutation, constructing the integer takes $O(n)$ time, and the primality test by trial division requires testing divisors up to $\sqrt{N_{\max}} < 2767$, costing $O(\sqrt{N_{\max}})$ divisions. The total worst-case time is therefore

In practice, early termination occurs well before exhausting all permutations. $\square$

Proposition (Space complexity). The algorithm uses $O(n)$ auxiliary space, where $n \leq 7$.

Proof. The only data structures are the current permutation ($n$ digits) and loop variables. $\square$

Answer

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

bool is_prime(int n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; (long long)i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    // By Theorem 2, only n=7 and n=4 can yield pandigital primes.
    // Search n=7 first in descending lexicographic order.
    string digits = "7654321";
    do {
        int num = stoi(digits);
        if (is_prime(num)) {
            cout << num << endl;
            return 0;
        }
    } while (prev_permutation(digits.begin(), digits.end()));

    // Fallback: search n=4
    digits = "4321";
    do {
        int num = stoi(digits);
        if (is_prime(num)) {
            cout << num << endl;
            return 0;
        }
    } while (prev_permutation(digits.begin(), digits.end()));

    return 0;
}

from itertools import permutations


def is_prime(n):
    """Deterministic primality test by trial division."""
    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():
    """Find the largest n-digit pandigital prime.

    By the divisibility-by-3 criterion, n-pandigital numbers are composite
    for n in {2,3,5,6,8,9}. Only n=7 and n=4 can yield primes.
    We search 7-digit pandigital numbers in descending order first.
    """
    for n in (7, 4):
        for perm in permutations(range(n, 0, -1)):
            num = int(''.join(map(str, perm)))
            if is_prime(num):
                return num
    return None


answer = solve()
assert answer == 7652413
print(answer)