Embedded Primes

The number associated with my diurnal age today, 27197, has the property that it contains nine embedded primes, namely 2, 7, 19, 71, 97, 197, 271, 719 and 2719. This qualifies it for membership in OEIS  A179917 (permalink):

A179917

Primes with nine embedded primes.

The initial members of the sequence are:

11317, 19739, 19973, 21317, 21379, 22397, 22937, 23117, 23173, 23371, 23971, 24373, 26317, 27197, 29173, 29537, 32719, 33739, 33797, 37397, 39719, 51137, 51973, 52313, 53173, 53479, 53719, 57173, 57193, 61379, 61979, 63179, 66173, 82373, 83137, 91373, 93719

This got me thinking about primes that contain no embedded primes. It turns out that there are only 125 such primes in the range up to 100,000. Primes with this property are members of OEIS A033274 (permalink):

A033274

Primes that do not contain any other prime as a proper substring.

The initial members of the sequence are:

11, 19, 41, 61, 89, 101, 109, 149, 181, 401, 409, 449, 491, 499, 601, 691, 809, 881, 991, 1009, 1049, 1069, 1481, 1609, 1669, 1699, 1801, 4001, 4049, 4481, 4649, 4801, 4909, 4969, 6091, 6469, 6481, 6869, 6949, 8009, 8069, 8081, 8609, 8669, 8681, 8699, 8849, 9001, 9049, 9091, 9649, 9901, 9949, 10009, 10069, 14009, 14081, 14669, 14699, 14869, 16001, 16069, 16649, 16901, 16981, 18049, 18481, 18869, 40009, 40099, 40609, 40699, 40801, 40849, 44699, 46049, 46099, 46649, 46681, 46901, 48049, 48481, 48649, 48869, 49009, 49069, 49081, 49481, 49669, 49681, 49801, 60091, 60649, 60869, 60901, 64081, 64609, 64849, 64901, 69481, 80669, 80681, 80849, 81001, 81649, 81869, 84869, 86069, 86969, 86981, 88001, 88469, 88801, 90001, 90469, 90481, 90901, 91081, 94009, 94849, 94949, 96001, 98801, 98869, 99469

So there are two types of primes: one contains no prime substrings while the other contains one or more prime substrings. Even five digit numbers can have ten embedded primes, although there are only three of them: 23719, 31379 and 52379. The embedded primes for these numbers are (permalink):

23719: 2, 3, 7, 19, 23, 37, 71, 719, 2371, 3719
31379: 3, 7, 13, 31, 37, 79, 137, 313, 379, 3137
52379: 2, 3, 5, 7, 23, 37, 79, 379, 523, 5237
Primes such as these belong to OEIS A179918:


 A179918



Primes with ten embedded primes.                        


The initial members of this sequence are:

23719, 31379, 52379, 111373, 111731, 111733, 112397, 113117, 113167, 113723, 113759, 113761, 115237, 117191, 117431, 121139, 122971, 123113, 123373, 123479, 123731, 124337, 126173, 126317, 127139, 127733, 127739, 127973, 129733, 131171

Of course, the number containing the embedded primes does not need to be prime itself. If we consider only composite numbers, then the following numbers contain nine embedded primes (permalink):

11379, 13137, 13173, 13179, 13197, 13673, 13719, 13731, 13732, 13735, 15237, 17337, 19137, 19733, 21131, 22371, 22373, 22379, 22971, 23113, 23119, 23179, 23313, 23317, 23379, 23479, 23571, 23673, 23733, 23739, 24173, 24673, 25317, 25937, 27113, 27131, 27137, 28317, 28373, 28379, 29371, 29373, 29379, 29397, 29713, 31137, 31197, 31371, 31372, 31375, 31733, 31797, 33719, 33733, 35479, 35937, 36173, 36719, 36733, 36737, 37193, 37197, 37972, 37973, 37975, 37977

There are 66 such composite numbers in the range up to 40,000. Consider 11379, the first number in the sequence. It has the following embedded primes: 3, 7, 11, 13, 37, 79, 113, 137, 379 but is itself composite, factoring to 3 x 3793. This sequence is not listed in the OEIS.

31373 holds the record in the range up to 100,000 with 11 embedded primes, namely 3, 7, 13, 31, 37, 73, 137, 313, 373, 1373 and 3137. It's composite and factorises to 137 x 229. It should be noted that the count of embedded primes is being made without regard to multiplicity. Thus the 3 that occurs three times in 31373 is counted only once. This counting without multiplicity applies to all the previously mentioned sequences.

What about composite numbers that contain no embedded primes. Well, we won't find any numbers containing the digits 2, 3, 5 or 7 and only the digits 0, 1, 4, 6, 8 and 9 will be allowed. There's 1011 in the range up to 40,000 (permalink) but I won't list them here.