Problems & Puzzles: Puzzles

Puzzle 1098 A Follow-up to puzzle 265 In our puzzle 265 we asked for the earliest integer having k distinct primes embedded, (as substrings). For example: 137 is the earliest number that has embedded 5 distinct primes: 3, 7, 13, 37 & 137 Dmitry Kamenetsky proposes the following open questions: The 10 digit number 1797193373 has 29 distinct substrings that are prime (see https://oeis.org/A093301). Q1. Can you find a 20 digit number that has the most distinct prime substrings? Q2. What about a 50 digit or a 100 digit number?

---

During the week from 6 to 11 August, 2022 contributions came from Paul Cleary, Giorgos Kalogeropoulos, Gennady Gusev.

***

Paul wrote:

Q1.

The following 20 digit numbers each have 75 prime substrings.

 

53882313797193373911

65892313797193373911

69832313797193373911

75582313797193373911.

 

Q2.

 

The following 50 digit number has 225 prime substrings.

 

66589231379719337391117917333313199131477933797337.

 

The following 100 digit number has 515 prime substrings.

 

5651928362945475388231379719337391111733199971137199371911973393739991331311791731979199391139993317.

 

As a matter of fact Paul also sent all the distinct primes for each solution. But I will save it for any person interested in these primes, on request.

***

Giorgos wrote:

Here are the best results that I could find. 

It is not guaranteed that the following numbers have "the most distinct prime substrings"

 

Q1

21319739719173319993 (Prime - 20 digits) has 72 prime substrings
 

Q2

58974339777113193119319371971933199197379397917933 (Composite - 50 digits) has 194 prime substrings
 

4598317377971397733937333133739791777331197391179113177191991937193737193313739973179393733719773153 (Composite = 100 digits) has 385 prime substrings

***

Gennady wrote:

My solutions:

20 digits:

21113173331797193373, 71 primes: [2, 3, 7, 11, 13, 31, 17, 73, 79, 97, 71, 19, 37, 211, 113, 131, 317, 173, 733, 331, 179, 797, 971, 719, 193, 337, 373, 2111, 1733, 7333, 3331, 9719, 7193, 1933, 9337, 3373, 11131, 11317, 17333, 73331, 33317, 33179, 17971, 71933, 111317, 113173, 317333, 317971, 179719, 971933, 193373, 1113173, 1797193, 21113173, 11131733, 13173331, 17333179, 31797193, 79719337, 211131733, 113173331, 733317971, 797193373, 733317971933, 331797193373, 1131733317971, 13173331797193, 17333179719337, 211131733317971, 113173331797193, 3173331797193373]

50 digits:

11315313331797193373919975991173331733377373999311, 190 primes: [3, 5, 7, 11, 13, 31, 53, 17, 79, 97, 71, 19, 37, 73, 59, 113, 131, 313, 331, 317, 179, 797, 971, 719, 193, 337, 373, 739, 919, 199, 997, 599, 991, 911, 173, 733, 773, 311, 1531, 3331, 9719, 7193, 1933, 9337, 3373, 3739, 3919, 9199, 1997, 1733, 7333, 9931, 9311, 31531, 15313, 31333, 13331, 33317, 33179, 17971, 71933, 33739, 39199, 91997, 75991, 17333, 73331, 33377, 33773, 73999, 113153, 315313, 153133, 313331, 317971, 179719, 971933, 193373, 933739, 739199, 975991, 759911, 599117, 317333, 373999, 1531333, 1797193, 3739199, 9199759, 1997599, 3331733, 7373999, 3739993, 3999311, 13331797, 31797193, 79719337, 93373919, 91173331, 73739993, 37399931, 133317971, 797193373, 719337391, 933739199, 739199759, 117333173, 331733377, 173337737, 9719337391, 1997599117, 9911733317, 79719337391, 19975991173, 59911733317, 11733317333, 17333173337, 33317333773, 33173337737, 31733377373, 73337737399, 153133317971, 531333179719, 331797193373, 733317333773, 331733377373, 173337737399, 733377373999, 377373999311, 7391997599117, 9911733317333, 3331733377373, 3173337737399, 15313331797193, 73337737399931, 33377373999311, 315313331797193, 193373919975991, 759911733317333, 331733377373999, 1131531333179719, 3153133317971933, 9337391997599117, 9911733317333773, 1173331733377373, 37391997599117333, 31733377373999311, 131531333179719337, 173331733377373999, 7193373919975991173, 15313331797193373919, 19975991173331733377, 131531333179719337391, 971933739199759911733, 759911733317333773739, 599117333173337737399, 1315313331797193373919, 7971933739199759911733, 7193373919975991173331, 9199759911733317333773, 7599117333173337737399, 33317971933739199759911, 99759911733317333773739, 193373919975991173331733, 975991173331733377373999, 759911733317333773739993, 13153133317971933739199759, 99759911733317333773739993, 131531333179719337391997599, 315313331797193373919975991, 1531333179719337391997599117, 3331797193373919975991173331, 9337391997599117333173337737, 3373919975991173331733377373, 13153133317971933739199759911, 33317971933739199759911733317, 97193373919975991173331733377, 131531333179719337391997599117, 3373919975991173331733377373999, 3919975991173331733377373999311, 37391997599117333173337737399931, 315313331797193373919975991173331, 531333179719337391997599117333173, 33179719337391997599117333173337737, 17971933739199759911733317333773739, 797193373919975991173331733377373999, 33317971933739199759911733317333773739, 3153133317971933739199759911733317333773, 13331797193373919975991173331733377373999311, 131531333179719337391997599117333173337737399]

***

On August 14, 2022 Dmitry Kamenetsky wrote:

For 20 digits I can get 77 prime substrings:

53843291733373939719
 

For 50 digits I can get 228 prime substrings:

24967998593997193319973973331131117317139137393977

***