On dissectable prime numbers

A few weeks back, I was watching this Numberphile video about prime numbers, and it brought to mind a rather different question about numbers with special derived traits.

It took a while for me to find the name they’d already been given (“super-prime numbers”), so I initially called them “dissectable”.

First a bad question

Here’s the original question as I framed it. Don’t rush in where I did, though, because it was initially a bad question, with an answer “no”, and I hope you take a few moments to wonder about why that might be the case.

Is there a prime number, containing at least one copy of every digit (in base 10), from which you can remove each digit, concatenate the rest of the digits, and all of those will also be prime?

Quick answer: No.

Here’s the example that started me thinking this way, and then the realization that showed me it was not a thing.

Consider the number \(197\). It’s prime, and if I delete each of its three digits (and squish the remaining two digits back together in order), I get the numbers \(\{17,19,97\}\). And those are also prime!

So yes, this kind of prime number exists, but are there any that have all ten digits in them, and still have the property?

Think about it a minute before you answer. If you need a hint, think about divisibility by \(3\), and that old heuristic we learned in elementary school of adding the digits of a big number together to determine if it’s a multiple of three….

OK? Here’s what I realized, after I’d already written a program to look for these numbers:

1. If I add all the digits of my original “prime” number together, and they add up to a multiple of three, then I’m screwed because it isn’t really prime at all. Oh and by the way, if I naively think it’s gonna be a 10-digit number I start with, when I add one copy of all the digits \(0+1+2+3+4+5+6+7+8+9\) I get \(45\) and nope, that is a multiple of three, so as a side-proof, no ten-digit number with one copy of every digit is ever prime. So already we know it’s gonna have more digits, right?

2. Well then, say there are eleven digits. I can make a prime number with eleven digits, where there’s just an extra copy of one of them, in some order. You can too… and probably you can write a better program to find one, since I wrote a stupid little thing that just guessed until it got one. So we can get a prime to start with.

   But hey, now we have to do the second bit: Delete each digit, and have the ten smaller numbers all also be prime. Sadly, we added a new digit to make a prime, so for at least one digit in the “fixed” number, deleting it will make a composite multiple of three.

   Maybe it’s even longer?

3. Nope, we’re in worse shape. No matter how long our initial prime number is, I already said it will have all ten digits in it, right? That was a starting premise.

   Well, at least one of those is a \(1\), and at least one of them is a \(2\). If the initial number is prime, we know its digits (when added) do not add up to a sum \(S\) that is a multiple of three. But if that’s true, it must be the case that either \((S-1)\) or \((S-2)\) is divisible by three. For any integer \(i\), it is always true that \((i-0)\) or \((i-1)\) or \((i-2)\) is divisible by three.

   That’s how “divisible by three” and remainders work.

It was a bad question all along. Sorry!

A feasible question

“Well,” I thought, “I started with a number that worked! \(197\) is one of these things. What other ones are there?”

As long as we don’t specify “contains at least one of every digit”, there are quite a few.

I still couldn’t find the official (or as it happens, semi-official) name of these things, so I thought that maybe if I could discover a few more, I might be able to look them up in the OEIS and find out what they’re actually called.

I won’t burden you with the awful Ruby program I wrote to do this originally, but it did churn through a bunch of relatively small numbers without too much effort, and pooped out the following series (which was, in fact, enough to find the OEIS entry):

23
37
53
73
113
131
137
173
179
197
311
317
431
617
719
1013
...

This is “prime numbers from which every single digit can be deleted, in turn, and the resulting concatenated digits are also prime”. You can see \(197\) there, and also some smaller ones. No one-digit primes, since there aren’t enough zero-digit primes to satisfy the condition.

And here is the OEIS series, dubbed many years back something like “super-primes”. Which is fine; I like “dissectable” still, but I’m almost certain that means something else to somebody else, so use them interchangeably.

There are also some stack exchange threads on this series, and a good number of samples. Part of that discussion includes a proof that there must be an infinite number of these… and shortly after there is a proof that there is not an infinite number of these. So there are some. We can say that, right?

One thing you’ll notice, if you run a program to find dissectable super-primes, is they become remarkably scarce. Primes are common, but when you get up to more than ten digits, you’re talking about ten constraints on them in addition to their own primality. If we assume—without loss of generality I guess—that deleting a digit of a prime number has about a constant probability of landing on a new prime number (given by the density of primes overall), then as numbers get large our chances are dependent on something like flipping a biased coin an increasing number of times (one for each digit), and hoping to get “heads” on every toss. It happens, but it’s just not as common as you want.

My computer got hot, and I got bored, when I was looking for larger dissectable super-primes. Eventually I did come up with a (bad) heuristic of sorts: I’d find large prime numbers where the sum of the digits and the sums of the all-but-one subsets of digits weren’t divisible by three, and then permute those sets and look to see if any of the arrangements worked out.

Like for example, I’d find (don’t ask) a set of digits like [9, 6, 4, 3, 1, 3, 9, 3], and then I’d permute those digits in all possible ways and check to see if any were dissectable primes. That one does have a winner: \(93361493\) is prime, as are all of [3361493, 9361493, 9361493, 9331493, 9336493, 9336193, 9336143, 9336149].

But those are also scarce. I didn’t find any really long ones, even by accident. Mine was not a good approach… though I also haven’t found a better one.

I wonder if you might find it fun to look, too?