Detailed mathematical approach

Problem Summary

A positive integer is called \(n\)-pandigital if its decimal digits are exactly \(1,2,\dots,n\), each used once. The task is to determine the largest pandigital number that is also prime.

At first glance the search space seems broad, because one might imagine checking pandigital numbers of every length from 1 through 9. The key simplification is that most lengths are impossible for purely arithmetic reasons, so the brute-force search collapses to a very small candidate set.

Mathematical Approach

For each \(n\), let \(\mathcal{P}_n\) denote the set of all numbers formed by permuting the digits \(1,2,\dots,n\). Then \(|\mathcal{P}_n| = n!\), and the problem is to compute

$\max\{x \in \mathcal{P}_1 \cup \mathcal{P}_2 \cup \cdots \cup \mathcal{P}_9 : \operatorname{Prime}(x)\}.$

The implementations do not examine this union blindly. They first eliminate impossible digit lengths, then enumerate the remaining candidates in descending order so that the first prime found is automatically the answer.

Eliminating Most Digit Lengths with a Digit-Sum Invariant

Every \(n\)-pandigital number uses the same digits, so every member of \(\mathcal{P}_n\) has the same digit sum

$s_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$

A decimal integer is divisible by 3 exactly when its digit sum is divisible by 3. Therefore, if \(3 \mid s_n\), then every element of \(\mathcal{P}_n\) is divisible by 3 and cannot be prime. The only exception to that logic would be the number 3 itself, but 3 never appears as an \(n\)-pandigital number under this definition.

Modulo 3, the quantity \(\frac{n(n+1)}{2}\) vanishes precisely when \(n \equiv 0\) or \(2 \pmod{3}\). Among \(1 \le n \le 9\), the only surviving lengths are therefore

$n \in \{1,4,7\}, \qquad s_1 = 1,\quad s_4 = 10,\quad s_7 = 28.$

So the original optimization problem reduces immediately to

$\max\{x \in \mathcal{P}_7 \cup \mathcal{P}_4 \cup \mathcal{P}_1 : \operatorname{Prime}(x)\}.$

The one-digit case contributes only \(1\), which is not prime, so in practice the real competition is between 7-digit and 4-digit pandigital numbers.

Why Descending Search Is Sufficient

Every 7-digit number is larger than every 4-digit number, and every 4-digit number is larger than the 1-digit case. Consequently, if a 7-digit pandigital prime exists, it is automatically larger than every pandigital prime of smaller length.

This is why the implementations scan \(n\) from 9 down to 1. After the divisibility-by-3 filter, that outer loop effectively becomes

$7 \to 4 \to 1.$

Within each surviving length, the search starts from the largest possible arrangement

$7654321,\qquad 4321,\qquad 1,$

and then moves strictly downward through all remaining permutations. Because the digits have fixed length and are compared left to right, lexicographic order and numerical order coincide here. Therefore the first prime encountered in the descending enumeration is the largest pandigital prime of that length, and the first prime encountered by the outer loop is the global maximum.

The Permutation Invariant Used by the Implementations

The candidate list is traversed by the standard previous-permutation rule. If the current digit string is \(d_1d_2\cdots d_n\), find the rightmost index \(i\) with \(d_i > d_{i+1}\). Then find the rightmost index \(j > i\) with \(d_j < d_i\), swap \(d_i\) and \(d_j\), and reverse the suffix \(d_{i+1}\cdots d_n\).

This construction gives the largest permutation that is still smaller than the current one. That invariant guarantees a strictly descending walk through all pandigital arrangements, with no duplicates and no omissions.

Worked Example

The digit-sum argument already removes the most tempting large cases. For \(n=8\),

$s_8 = \frac{8 \cdot 9}{2} = 36 \equiv 0 \pmod{3},$

so every 8-pandigital number is composite. For \(n=7\),

$s_7 = \frac{7 \cdot 8}{2} = 28 \not\equiv 0 \pmod{3},$

so 7-digit pandigital primes remain possible.

The descending traversal can be seen in a smaller family. Starting from \(4321\), the previous-permutation rule produces \(4312\). The first candidate is composite because

$4321 = 29 \cdot 149,$

and the second is composite because it is even. The algorithm continues in the same descending way until it reaches a prime. The full solution uses exactly this mechanism, but it begins with the 7-digit family because that is where the maximum must live if any 7-digit pandigital prime exists.

How the Code Works

Filtering Lengths and Building the Starting Candidate

The C++, Python, and Java implementations iterate \(n\) from 9 down to 1, compute \(\frac{n(n+1)}{2}\), and immediately skip any length whose digit sum is divisible by 3. For a surviving length, they build the maximal pandigital arrangement \(n,n-1,\dots,1\), which is the correct start state for a descending search.

Generating Candidates in Descending Order

Each implementation repeatedly converts the current digit arrangement into an integer and checks whether it is prime. If not, it advances to the next smaller permutation. The C++ version relies on a standard library previous-permutation routine; the Python and Java versions implement the same lexicographic step directly. In all three cases, the invariant is the same: the current state is always the largest untested pandigital number below the previous state.

Primality Testing and Early Exit

The primality test is plain trial division. Values below 2 are rejected, even numbers are handled separately, and then only odd divisors are tried. The loop guard is written in the mathematically equivalent form \(p \le m/p\), where \(m\) is the candidate being tested, instead of \(p^2 \le m\).

As soon as one candidate passes the test, the program returns immediately. The implementations also include small checkpoint tests using one known pandigital prime and one known composite example, so the primality routine is validated before the full search begins.

Complexity Analysis

After the digit-sum filter, only the lengths \(7,4,1\) remain. In the worst case, the total number of pandigital candidates examined is therefore

$7! + 4! + 1! = 5040 + 24 + 1 = 5065.$

For each candidate \(m\), trial division costs \(O(\sqrt{m})\), and here \(m < 10^7\). A clean overall bound is

$O\!\left(\sum_{n \in \{1,4,7\}} n!\sqrt{10^n}\right),$

which is dominated by the 7-digit case and is tiny in practice.

Memory usage is \(O(n)\) with \(n \le 7\), because the implementation stores only the current digit arrangement and a few scalar values. No sieve, recursion tree, or large candidate table is required.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=41
2. Pandigital number: Wikipedia - Pandigital number
3. Divisibility rule: Wikipedia - Divisibility rule
4. Lexicographic order: Wikipedia - Lexicographic order
5. Prime number: Wikipedia - Prime number