Prime with All Digits Problem

Problem: What is the smallest prime number that contains each of the 10 digits 0 to 9 at least once?

Solution: Any 10-digit solution has each digit once and only once, so the sum of the digits is:

1 + 2 + 3 + ... + 9 = 45

But the rule of 9 says that 9 divides a number if and only if it divides the sum of its digits. It follows that there are no 10-digit solutions.

An 11-digit solution will have exactly one digit repeated (not 0, because then the sum of the digits would again be 45 and the 11-digit number divisible by 9).

The smallest candidate results from placing the smaller digits in the higher places:

x = 10 123 456 789

This number is not a prime, but gives an idea of how to generate relatively small candidates: divide x into two pieces, leaving the left digits intact and permuting the right digits. The incidence of primes in the vicinity of x is about 4%, so a reasonable approach is to leave the left six digits intact and permute the rightmost five digits (there are 120 such permutations):

x' = 101234xyzuv,

where xyzuv is a permutation on {5, 6, 7, 8, 9}.

These are the smallest 11-digit numbers containing all ten digits that may be prime, and this C program generates them all and tests them for primality, turning up six primes among the 120 candidates, the smallest and solution to the original question (the smallest prime including all ten digits):

z = 10 123 457 689

QED.