Problems & Puzzles: Puzzles

Puzzle 823. String of digits 1379 full of primes Here we will ask for strings S composed of L digits from these four: 1, 3, 7 & 9. In particular we will ask for that S of L digits such that a maximal of K primes are embedded in S, reading S only from left to right. Example: For L=20, I found that for S=19717393139337391999 K=68. But I'm not sure that 68 is the maximal K value for L=20.   Q1. Please confirm that for L=20, K=68 is maximal, or get another S with a larger K, for the same L=20.   Q2. Redo Q1 for L=40 and L=80.

---

Contribution came from Emmanuel Vantieghem and Dmitry Kamenetsy

***

Emmanuel wrote:

About Q1 : S = 91131179719337391999  gives 73 underlying primes.

But I'm not sure this is the maximum.

 

About Q2 : S = 7139971933199733313711131179719337391999 (40 digits) gives 156 underlying primes.

I'm almost 100% sure this is NOT the maximum.

***

Dmitry wrote:

L=20, 74 primes: 39311171399719337397

L=40, 166 primes: 391997391117113173331399793373971719
3337

L=80, 354 primes: 19133139391911371797171391397919391117191773
719393977397333113933733937199937799

I don't think the results are maximal. Even for L=20, there are 4^20 possibilities to check.

***

On March 29, 2016 T. D. Noe wrote:

This appears to be a hard problem.  I decided to solve it (completely) for
n digit-numbers for n = 1 to 14.  The results are on three consecutive web
pages beginning with http://www.integersequences.org/s000857.html Using
Mathematica, the 14-digit case took about 15 hours; The 20-digit case will
take about a year using my current approach.
 

***

Michael Hürter wrote on April 17, 2017:

I have the following results:

 

L = 40: 183 primes
1733391137971933199739979337979931793719

 

L = 80: 431 primes
13999917333119797193319973711793793333133333373919393911317773131939913739397117

 

***