409 is an interesting prime number. If you remove any number of its digits, then you will get a number that is not prime.

4=2^2
0=not prime
9=3^2
40=2^3*5
49=7^2
09=9=3^2

Call a number with this property a minimal prime. Find all minimal primes.

Such minimal primes would need at least two digits: at least one to remove and at least another to remain.  As what might remain could be a single digit, the allowable digits must be limited to non-primes:

0,1,4,6,8,9

The last digit of course must be odd: either 1 or 9.

Categorizing them by their first and last digits:

1...1
only 11

4...1
only 41

6...1
only 61

8...1
The ellipsis can be filled with 0's and 8's. At least one of these must be non-zero (i.e., an 8), otherwise the number as a whole will be divisible by 3 rather than prime. All of 1's, 4's and 6's are not allowed as 11, 41 and 61 are prime, and 9's are not allowed as 89 is a prime.

881 is a prime, and is thus a minimal prime and in fact, no zeros or additional 8's can be added to this as 881 would be a prime subset. Thus 881 is the only minimal prime in the 8...1 grouping.

9...1
Again, 1's, 4's and 6's are not allowed--just 0's, 8's and 9's.

991 is such a prime. This also means that any 9 at all in the middle precludes any other digits there, as 991 would be a subset of the whole such built number.

Since 881 is a prime, only one 8 is allowed in the middle, requiring one or more zeros before and/or after the 8, as 981 itself is not a prime.

9001 is a minimal prime without any 8's. And thus also, at most one zero can accompany a lone 8, if such is possible. But 9081 and 9801 are both composite, so 991 and 9001 are the only two in the 9...1 category.

1...9
only 19

4...9
409, as pointed out, is a minimal prime. Thus zero can't be used in combination with other digits in the middle, and no 1's or 8's can be used at all as 19 and 89 are prime. That leaves 4's and 6's.

449 is similarly a minimal prime, thus ending the possibility of combining an interior 4 with any number of 6's. That leaves only 6's to play with. But 469 is divisible by 7. Placing an additional 6 in the middle, regardless of how many 6's were there (in this case just one), is equivalent to multiplying by 10 and subtracting 21, and so by induction all such numbers are divisible by 7, and no number of the form 4666...6669 is prime.

So 409, 449 and 499 are the only members in this category.

6...9
Both 1's and 8's are disallowed because of 61 and 89, leaving 0's, 4's, 6's and 9's. At least one 4 is needed to prevent divisibility by 3.

At most one 4 can be used, to prevent 449 as a subset, so exactly one 4 is needed, and no additional 9's can be used after the 4, as we need to prevent a 499 subset.

6469 is another minimal prime, as is 666649. So in any further combinations, no 6 can follow the 4 and at most two added interior 6's can appear before the 4 if other digits are to be added.

6949 is a minimal prime showing also that no 9 can be used before the 4 in conjunction with additional digits.

60000049 is a minimal prime showing at most 4 0's can be used before the 4 when combined with other digits.

640009 is a minimal prime, showing at most 2 zeros can be added after the 4 when combined with other digits.

Adding 6's:
66000049, 60649, 66600049

I don't see any way of adding additional 6's or rearranging them to get another minimal prime.

8...9
only 89

9...9
no 1's or 8's are allowed in the ellipsis--only 0's, 4's, 6's and 9's.

Again there must be at least one 4 to prevent divisibility by 3. But again you can't have more than one, in order to prevent 449 as a subset.

9649 is minimal and so 6 can't appear before any 4's if there are to be more digits added.

946669 is minimal.

No zeros can be added to the right of the 4, to prevent subset 409, but there might be zeros before the 4, and extra 9's anywhere.

9049 is minimal, so no 9's or 6's can be added anywhere if there's that zero to the left of the 4.

94999 would be minimal except it has 499 in it.

I think I've found them all:

11, 41, 61
881
991, 9001
19
409, 449, 499
6469, 666649, 6949, 60000049, 640009, 66000049, 60649, 66600049
89
9649, 9049

Looking at Ady's list, I see I missed 9949. The single-digit ones don't count for this puzzle, as, when you remove its digit you're not left with any number, let alone one that's not prime.

See also Math Man's comment on this solution for the other minimal prime I missed as well as the ineligibility of 640009.

Edited on April 24, 2012, 5:34 pm

Posted by Charlie on 2012-04-24 16:17:04