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.)

[QUOTE=davar55;473344]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.)[/QUOTE]
For N = 1, the answer is obviously 4; any string composed of the digits 2, 3, 5, and 7 does the job.

For N > 1, there is an obvious upper bound: The first digit can be any of the 9 non-zero 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.

[QUOTE=Dr Sardonicus;473346]For N = 1, the answer is obviously 4; any string composed of the digits 2, 3, 5, and 7 does the job.

For N > 1, there is an obvious upper bound: The first digit can be any of the 9 non-zero 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.[/QUOTE]

for small values of N perhaps using russian doll primes or similar tricks may help. as long as there's a left truncatable,right truncatable pair with N-1 digits the same.

For N=2, length is 32. Here is one such string [c]23129411343747175359619673838979[/c]

Elegant. How can you show it's truly of minimum length? (but of course it is...)

Lower bounds for n=3,4,5 are 280, 2321, 19102. But I don't know if these are achievable.

[QUOTE=davar55;473352]Elegant. How can you show it's truly of minimum length? (but of course it is...)[/QUOTE]

For N=2, it is easy. There are 21 2-digit primes. Our best case length is 22 (start with a 2 digit prime, and then with each additional digit, we generate another unique 2-digit 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.

I misread the problem :blush:

I looked for strings such that a (not necessarily contiguous) sub[i]set[/i] of its characters would form all the N-digit 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 [i]upper[/i] bound for the length in question is

N*(primepi(10^N) - primepi(10^(N-1)),

the length of the string formed by simply concatenating all the N-digit primes.

[QUOTE=axn;473353]Lower bounds for n=3,4,5 are 280, 2321, 19102. But I don't know if these are achievable.[/QUOTE]
Can we come close if we don't require proof of absolute minimality? Like within 10% of
these lower bounds? In particular, is there a good, even if not optimal, string for N=3?

[QUOTE=davar55;474002]Can we come close if we don't require proof of absolute minimality? Like within 10% of
these lower bounds? In particular, is there a good, even if not optimal, string for N=3?[/QUOTE]

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 100-999 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.

So it's not hard to specify some digit string that contains all the, say , three-digit
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?