20171207, 14:13  #1 
May 2004
New York City
2^{3}·23^{2} Posts 
Digit strings containing primes
Find the length of a minimum length string of decimal digits which
contains as substrings all the primes of a particular length N, for N = 1,2,3,4,... (I didn't see this in the oeis, but I may have missed it.) 
20171207, 14:48  #2  
Feb 2017
Nowhere
4454_{10} Posts 
Quote:
For N > 1, there is an obvious upper bound: The first digit can be any of the 9 nonzero digits. The next N  2 digits can each be any of the ten decimal digits. The ones digit can be any of the digits 1, 3, 7, or 9. So for N > 1, the minimum length is no more than 9 + 10*(N  2) + 4 = 10*N  7. There could be a shorter string that does the job, but I don't see a good way offhand to find one. 

20171207, 15:12  #3  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:


20171207, 16:03  #4 
Jun 2003
2×3×19×43 Posts 
For N=2, length is 32. Here is one such string 23129411343747175359619673838979

20171207, 16:25  #5 
May 2004
New York City
2^{3}×23^{2} Posts 
Elegant. How can you show it's truly of minimum length? (but of course it is...)
Last fiddled with by davar55 on 20171207 at 16:27 
20171207, 16:29  #6 
Jun 2003
4902_{10} Posts 
Lower bounds for n=3,4,5 are 280, 2321, 19102. But I don't know if these are achievable.

20171207, 16:50  #7 
Jun 2003
2·3·19·43 Posts 
For N=2, it is easy. There are 21 2digit primes. Our best case length is 22 (start with a 2 digit prime, and then with each additional digit, we generate another unique 2digit prime). However, primes starting with 2,4,5,6, or 8, cannot be generated this way. There are 11 such primes. One of them can be used as starting prime, but that still leaves 10 that need 1 additional digit. So 22+10 = 32 is the theoretical lower bound, and as luck would have it, we can achieve it.

20171207, 17:12  #8 
Feb 2017
Nowhere
2·17·131 Posts 
I misread the problem
I looked for strings such that a (not necessarily contiguous) subset of its characters would form all the Ndigit primes. My bound works for that problem. Unfortunately, it's not the problem being posed. I can't presently improve on the analyses already given. An obvious upper bound for the length in question is N*(primepi(10^N)  primepi(10^(N1)), the length of the string formed by simply concatenating all the Ndigit primes. Last fiddled with by Dr Sardonicus on 20171207 at 17:25 
20171214, 14:12  #9 
May 2004
New York City
2^{3}·23^{2} Posts 

20171214, 14:28  #10 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
my guess is if we knew a few things we can show things like certain types of digits have to come up more often as last digits than the amount of times they are the first digits ( for odd values for example) and that forces certain interlocking patterns potentially via the pigeonhole principle. for n=3 the primes in range 100999 have 35 with last digit 1, 21 with first digit 1 and 13 with second digit is 1 since 21+13<35 we know there's at least one that has to be at the end/ doesn't overlap with any other prime.
Last fiddled with by science_man_88 on 20171214 at 14:34 
20180131, 14:45  #11 
May 2004
New York City
2^{3}×23^{2} Posts 
So it's not hard to specify some digit string that contains all the, say , threedigit
primes, and the OP puzzle did ask for a minimal length such string. If that's too hard to find and prove minimal at this point, how short a digit string can we find ignoring the minimality condition? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What to do with 16 digit twin, nonMersenne primes?  RienS  Miscellaneous Math  15  20141118 01:48 
911 Digit Primes Quiz  Stargate38  Puzzles  4  20110714 12:16 
Primes from powers of 2 strings.  Flatlander  Puzzles  40  20110210 09:42 
PrimeDigit Primes...  petrw1  Puzzles  10  20091216 21:58 
listing 15digit primes  fivemack  Software  8  20091019 20:22 