Project Euler Problem 41

Solution

Answer: 7652413

1. Mathematical analysis

We want the largest pandigital prime, where an $n$-digit pandigital number uses each digit $1$ to $n$ exactly once.

For example:

$$2143$$

is $4$-digit pandigital and prime.

The naive idea is:

Generate all pandigital numbers,
Check primality,
Take the maximum.

But we can do much better using number theory.

Key insight 1: Divisibility by 3

A number is divisible by $3$ iff the sum of its digits is divisible by $3$.

For an $n$-digit pandigital number, the digit sum is:

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

Let’s check values of $n$:

$$n=9:\quad \frac{9\cdot10}{2}=45$$

Divisible by $3$, so every 9-digit pandigital number is divisible by 3 → impossible to be prime.

$$n=8:\quad \frac{8\cdot9}{2}=36$$

Also divisible by $3$ → every 8-digit pandigital number is composite.

$$n=7:\quad \frac{7\cdot8}{2}=28$$

Not divisible by $3$, so a 7-digit pandigital prime might exist.

Thus the largest pandigital prime must be 7-digit or smaller.

We only need to search among permutations of:

$$1,2,3,4,5,6,7$$

Key insight 2: Search in descending order

We want the largest such prime.

Instead of generating all pandigital numbers and taking the maximum, generate permutations in descending lexicographic order and stop at the first prime found.

This guarantees optimality.

Key insight 3: Fast primality test

To test whether a number $n$ is prime:

Reject $n < 2$,
Reject even numbers,
Try divisors only up to:

$$\sqrt{n}$$

because if $n = ab$, one factor must be at most $\sqrt{n}$.

So for each candidate, test divisibility by odd integers up to:

$$\lfloor \sqrt{n} \rfloor$$

Since there are only:

$$7! = 5040$$

7-digit permutations, brute force is tiny.

2. Python implementation

from itertools import permutations
import math

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

    limit = int(math.isqrt(n))

    # Check odd divisors only
    for d in range(3, limit + 1, 2):
        if n % d == 0:
            return False

    return True

def largest_pandigital_prime():
    # Try n from largest to smallest
    for n in range(9, 0, -1):

        # Skip digit lengths whose digit sum is divisible by 3
        digit_sum = n * (n + 1) // 2
        if digit_sum % 3 == 0:
            continue

        digits = ''.join(str(i) for i in range(n, 0, -1))

        # Generate permutations in descending order
        for perm in permutations(digits):
            number = int(''.join(perm))

            if is_prime(number):
                return number

answer = largest_pandigital_prime()
print(answer)

3. Code walkthrough

Imports

from itertools import permutations
import math

permutations generates all digit arrangements.
math.isqrt() computes integer square roots efficiently.

Primality test

def is_prime(n):

Checks whether n is prime.

if n < 2:
    return False

Numbers below 2 are not prime.

if n % 2 == 0:
    return n == 2

Reject even numbers except 2.

limit = int(math.isqrt(n))

Only test divisors up to $\sqrt{n}$.

for d in range(3, limit + 1, 2):

Only odd divisors are needed.

if n % d == 0:
    return False

If divisible, it is composite.

Otherwise:

return True

Main search

for n in range(9, 0, -1):

Search from largest digit count downward.

Skip impossible cases

digit_sum = n * (n + 1) // 2
if digit_sum % 3 == 0:
    continue

Eliminates $n=9,8,6,5,3,2$, etc., because all such pandigital numbers are divisible by 3.

The first meaningful case is:

$$n=7$$

Generate candidates in descending order

digits = ''.join(str(i) for i in range(n, 0, -1))

For $n=7$:

"7654321"

Then:

for perm in permutations(digits):

Enumerates permutations in descending lexicographic order.

Thus the first prime encountered is automatically the largest.

Small example check

For the example:

$$2143$$

Our primality test checks divisors up to:

$$\sqrt{2143}\approx 46$$

No divisor exists, so it is prime.

Also, $2143$ uses digits $1,2,3,4$ exactly once, confirming the example.

4. Final verification

We proved:

8-digit and 9-digit pandigital numbers are impossible because digit sums are divisible by 3.
Therefore the answer must be 7-digit.
We search all 7-digit pandigital numbers in descending order.
The first prime encountered is:

$$7652413$$

Checks:

Uses digits $1$–$7$ exactly once ✓
Odd and not divisible by 3 ✓
Prime ✓
Largest by descending search ✓

Answer: 7652413