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.
 

***

Records   |  Conjectures  |  Problems  |  Puzzles