Beyond 23

The algorithm that I got Gemini to create and that I used in the post 23 Revisited was the result of the following prompt:

Write a program in SageMath that determines all the composite, positive integers in a given range that contain the digits 2 and 3 in ascending order from left to right (but not necessarily consecutively) and whose prime factors also all contain the digits 2 and 3 in ascending order but not necessarily consecutively. The default range can be from 1 to 40000. The output should a table showing number and factors followed by a comma-separated list of the qualifying numbers.

Instead of the prime 23, other prime numbers can be investigated. Composite numbers could be investigated too but this would lead to rather large numbers and so I'll restrict this investigation to prime numbers but I'll increase the range from 1 to one million.

Here are the results for 11 (permalink):

Number       | Prime Factors

------------------------------

110231       | 11, 911

111221       | 11, 10111

112321       | 11, 10211

117821       | 11, 10711

128711       | 11, 11701

129811       | 11, 11801

131153       | 11, 11923

131197       | 11, 11927

171121       | 211, 811

211321       | 11, 19211

231121       | 11, 21011

232111       | 11, 21101

261143       | 113, 2311

351119       | 311, 1129

451121       | 11, 41011

511621       | 11, 46511

781121       | 11, 71011

892111       | 11, 81101

Here are the results for 13 (permalink):

Number       | Prime Factors

------------------------------

13169         | 13, 1013

16913         | 13, 1301

22139         | 13, 131

113269       | 13, 8713

131729       | 13, 10133

131807       | 13, 10139

132703       | 131, 1013

134069       | 13, 10313

136669       | 13, 10513

137069       | 113, 1213

137969       | 13, 10613

138781       | 137, 1013

147013       | 113, 1301

161369       | 13, 12413

169013       | 13, 13001

171301       | 13, 13177

171379       | 13, 13183

172133       | 13, 13241

180713       | 13, 13901

190013       | 139, 1367

211303       | 131, 1613

313469       | 13, 24113

313729       | 13, 24133

313781       | 13, 24137

360139       | 13, 2131

407213       | 313, 1301

413473       | 313, 1321

421369       | 13, 32413

661369       | 313, 2113

797513       | 613, 1301

813397       | 13, 4813

813451       | 613, 1327

Here are the results for 17 (permalink):

Number       | Prime Factors

------------------------------

51731         | 17, 179

117589       | 17, 6917

173009       | 17, 10177

178313       | 17, 617

198917       | 17, 11701

217843       | 179, 1217

291703       | 17, 17159

295817       | 17, 17401

301733       | 17, 17749

308417       | 179, 1723

351713       | 17, 1217

368917       | 17, 21701

506617       | 17, 1753

517021       | 17, 1789

541753       | 317, 1709

717043       | 17, 42179

Here, and finally, are the results for 19 (permalink):

Number       | Prime Factors

------------------------------

19361         | 19, 1019

36119         | 19, 1901

119467       | 193, 619

121943       | 197, 619

193667       | 19, 10193

194629       | 191, 1019

196667       | 193, 1019

251929       | 191, 1319

361019       | 19, 19001

361969       | 19, 19051

366719       | 19, 19301

370519       | 19, 19501

371963       | 19, 19577

376219       | 19, 19801

381947       | 193, 1979

519329       | 191, 2719

601967       | 193, 3119

714419       | 19, 1979

719473       | 19, 1993

752419       | 19, 199

796519       | 419, 1901

I won't continue with primes larger than 23 because really what I want is an algorithm that will identify a sequence of digits that form a prime within a number and then check that the same digit sequence occurs with each of its prime factors. The number being checked is thus composite. Here is a permalink to the program that I've now included in my daily number analysis.

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.