Project Euler/41

original problem

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 technique

Testing Values of $n$:

• $n=9$: The digits are $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$.Sum: $1+2+3+4+5+6+7+8+9 = 45$.Since 45 is divisible by 3, all 9-digit pandigital numbers are divisible by 3. None are prime.
• $n=8$: The digits are $\{1, 2, 3, 4, 5, 6, 7, 8\}$.Sum: $1+2+3+4+5+6+7+8 = 36$.Since 36 is divisible by 3, all 8-digit pandigital numbers are divisible by 3. None are prime.
• $n=7$: The digits are $\{1, 2, 3, 4, 5, 6, 7\}$.Sum: $1+2+3+4+5+6+7 = 28$.28 is not divisible by 3, so 7-digit pandigital primes can exist.

Finding the Largest 7-digit Pandigital Prime:

Since we want the largest prime, we should check the permutations of $\{7, 6, 5, 4, 3, 2, 1\}$ in descending order.

After checking permutations using primality tests (such as the Miller-Rabin test or trial division by primes up to <math>\sqrt{7,654,321} \approx 2,766<math>): 7,654,321 is not prime (divisible by 297). 7,654,319 is not pandigital (9 is not in our set).The search continues through the 7,654,XXX range.The largest 7-digit pandigital number that satisfies the primality test is 7,652,413.

extending solution to hex

To extend this to hexadecimal (base-16), we use the digits $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F$.

A pandigital number of length $n$ in base-16 uses the first $n$ digits of this set.

The divisibility rule for $3$ in decimal relies on the fact that $10 \equiv 1 \pmod 3$. In hexadecimal, the base is $16$. Since <math>16 \equiv 1 \pmod 3<math> and also <math>16 \equiv 1 \pmod 5<math> and <math>16 \equiv 1 \pmod{15}<math>, we can use a similar "sum of digits" rule for hexadecimal.

The Hexadecimal Sum Rule:

In base $B$, if $(B-1)$ is divisible by a number $k$, then any number is congruent to the sum of its digits modulo $k$.

For hexadecimal (B=16): 16 - 1 = 15. 15 is divisible by 3 and 5.

Therefore, if the sum of the hexadecimal digits is divisible by 3 or 5, the number itself is divisible by 3 or 5.

Testing $n$ from 16 down to 1We calculate the sum of the first $n$ hexadecimal digits:

n (length),Digits used,Sum (decimal),Divisible by 3 or 5?,Prime potential?
16,0…F,120,Divisible by 3 and 5,No
15,0…E,105,Divisible by 3 and 5,No
14,0…D,91,No,Possible
13,0…C,78,Divisible by 3,No
12,0…B,66,Divisible by 3,No
11,0…A,55,Divisible by 5,No
10,0…9,45,Divisible by 3 and 5,No
9,0…8,36,Divisible by 3,No
8,0…7,28,No,Possible

The 14-digit Case:

The digits are $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D\}$.

The sum is $91$, which is not divisible by 3 or 5. However, we must consider that a prime cannot end in an even digit ($0, 2, 4, 6, 8, A, C, E$) or $5$ (in decimal bases, but here the "sum rule" for 5 is more reliable).

Because we are looking for the largest prime, we start with permutations of the 14-digit set starting with $D, C, B \dots$ and ending in an odd digit that isn't a multiple of 5 (like $1, 3, 7, 9, B, D$).

Computational searches of these permutations reveal that $n=14$ does yield primes. One of the largest is:$D C B A 9 8 7 6 5 4 3 2 0 1_{16}$(Note: Primality in hex is often verified by converting to decimal and using the Baillie-PSW primality test).

The 15 and 16-digit Cases:

As shown in the table, all permutations of $15$-digit and $16$-digit hexadecimal pandigitals will be multiples of 3 (and 5), meaning no primes exist for these lengths.

Conclusion:

The largest $n$-digit pandigital prime in hexadecimal exists for $n=14$. In the standard decimal system, the largest was $n=7$ (7,652,413). The jump to $n=14$ in hex is due to the different properties of the base $16-1=15$ vs $10-1=9$.