Project Euler Problem 41 Solution: Pandigital Prime

Project Euler Problem 41 Statement

We shall say that an $n$-digit number is pandigital if it makes use of all the digits $1$ to $n$ exactly once. For example, $2143$ is a $4$-digit pandigital and is also prime.

What is the largest $n$-digit pandigital prime that exists?

Solution

This problem asks us to investigate the realm of pandigital numbers for the largest prime. An obvious question is: what is the value of n in n-digit pandigital prime? We know it's between 4 and 10 but that leaves a huge set of prime number candidates to search through. So let's eliminate some values of n by using the divisibility rule which states that an integer is divisible by 3 whose sum of digits is divisible by 3 and therefore composite and not prime.

9+8+7+6+5+4+3+2+1+0 = 45, 45/3 = 15
9+8+7+6+5+4+3+2+1 = 45, 45/3 = 15
8+7+6+5+4+3+2+1 = 36, 36/3 = 12
7+6+5+4+3+2+1 = 28, 28/3 = 9.333…
6+5+4+3+2+1 = 21, 21/3 = 7
5+4+3+2+1 = 15, 15/3 = 5
4+3+2+1 = 10, 4/3 = 1.333…
3+2+1 = 6, 6/3 = 2
2+1 = 3 3/3 = 1

Only pandigital numbers of length 4 and 7 can form a prime number. The others cannot because any combination of their digits will sum to a number divisible by 3 as affirmed by the commutative law of addition. So that leaves us to search odd 4 and 7 digit pandigital numbers for a prime number less than 4321 and 7654321 respectively. Since we want the largest pandigital prime we'll start with 7 digit numbers.

The result is quickly found by the 954th iteration of our investigation. Starting with 7654321 we check each decreasing odd number for being pandigital and prime. The first number meeting both these conditions is our solution.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 41

HackerRank Project Euler 41: Find the largest n-digit pandigital prime below some limit, $N\lt 10^{10} - 1$.

Python Source Code

import itertools, Euler
    
p = []
for i in [4,7]:
    for j in itertools.permutations(range(1, i+1)):
        n = int(''.join(map(str, j)))
        if Euler.is_prime(n): p.append(n)

for _ in range(int(input())):
    N = int(input())
    print(next((i for i in p[::-1] if i <= N), -1))

Last Word

This is another closed-ended problem. Just solve and move on to the next.

The is_prime function will be imported instead of hard coded into the source code. This makes a concise solution and allows the function to be improved.