Shavitian subprime numbers

Shavitian subprime numbers, which may also be known by another term if anyone else has bothered to care about such numbers, are interesting things! Here's the formal definition:

`A positive integer N is a Shavitian subprime if any subset of consecutive digits within N, including N itself, is prime.`

For instance, for the number 1,234 to be a Shavitian subprime, the following numbers would all have to be prime:

 1234 122334 123234 1234

It turns out there are only 9 such numbers. They are:

 2357 23375373 373

It's actually possible to prove that these are the only Shavitian subprimes for all n > 1.

Proof of Shavitian subprimes

The trick to proving that there are no other Shavitian subprimes lies in how we can create candidates for subprimes. These candidates are not necessarily subprimes, but any multi-digit subprime can be created by this method. In other words, not every candidate is a subprime, but every subprime is a candidate. To create a candidate, take a known Shavitian subprime and append 2, 3, 5 or 7 to the left of it.

If we have all N-digit Shavitian subprimes, we can create a list of candidates that would contain all (N+1)-digit Shavitian subprimes by appending 2, 3, 5 and 7 to each N-digit number. Appending any other digit would introduce a non-prime digit to the number, thus making it not a Shavitian subprime. And we can prove that every (N+1)-digit Shavitian subprime is in the list of candidates1.

It's easy to create a list of all possible 1-digit Shavitian subprimes; they're just all one-digit prime numbers. We can then use these to create all 2-digit candidates, and use those to create all 3-digit candidates, etc. This creates a tree structure, with each number spawning four "children" derived from the above method. At each step, before we create the list of M1-4 candidates from a candidate N, we check to see if N is actually a Shavitian subprime; if it isn't, none of the Ms or their children will be, so we can abandon that branch of the tree. (Excuse the mixed metaphors; I didn't come up with these terms.)

Below is the list. As you can see, all of the branches end fairly quickly. Of all the 16 2-digit candidates, only 4 are actually Shavitian subprimes. And of the 16 candidates derived from those, only 1 is a Shavitian subprime. And none of its children are Shavitian subprimes. Remember, there can't be any Shavitian subprime that is not in this tree, as we showed above (and proved in the footnote).

(Note: In this list, a black number is a Shavitian subprime, while a red number is not. Also, at times I have notation x2 or x5. Any number that has a digit followed by 2 or 5 is not a Shavitian subprime, since that x2 or x5 subset would be divisible by 2 or 5. Each red number is followed by an ellipsis to signify that there are actually infinite candidates derivable from it, but none of them will be Shavitian subprimes, since they'd all contain that number.)

• 2
• x2...
• 3
• 23
• x23...
• 33... (divisible by 3)
• 53
• x53...
• 73
• 273... (divisible by 3)
• 373
• 2373... (divisible by 3)
• 3373... (33 is divisible by 3)
• 5373... (divisible by 3)
• 7373... (divisible by 73)
• 573... (divisible by 3)
• 773... (77 is divisible by 7)
• 5
• x5...
• 7
• 27... (divisible by 3. Incidentally, 27 is my favorite number.)
• 37
• 237... (divisible by 3)
• 337... (33 is divisible by 3)
• 537... (divisible by 3)
• 737... (divisible by 11)
• 57... (divisible by 3)
• 77... (divisible by 7)