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
L=80, 354 primes: 19133139391911371797171391397919391117191773

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 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
L = 80: 431 primes


Records   |  Conjectures  |  Problems  |  Puzzles