Digit strings containing primes

davar55 · 2017-12-07, 14:13

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

Dr Sardonicus · 2017-12-07, 14:48

Quote:

Originally Posted by davar55

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

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.

science_man_88 · 2017-12-07, 15:12

Quote:

Originally Posted by Dr Sardonicus

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.

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.

axn · 2017-12-07, 16:03

For N=2, length is 32. Here is one such string 23129411343747175359619673838979

davar55 · 2017-12-07, 16:25

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

axn · 2017-12-07, 16:29

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

axn · 2017-12-07, 16:50

Quote:

Originally Posted by davar55

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

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.

Dr Sardonicus · 2017-12-07, 17:12

I misread the problem

I looked for strings such that a (not necessarily contiguous) subset 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 upper 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.

davar55 · 2017-12-14, 14:12

Quote:

Originally Posted by axn

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

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?

science_man_88 · 2017-12-14, 14:28

Quote:

Originally Posted by davar55

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?

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.

davar55 · 2018-01-31, 14:45

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?

2017-12-07, 14:13	#1
davar55 May 2004 New York City 2³·23² 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.)

2017-12-07, 16:25	#5
davar55 May 2004 New York City 2³×23² Posts	Elegant. How can you show it's truly of minimum length? (but of course it is...) Last fiddled with by davar55 on 2017-12-07 at 16:27

2017-12-07, 17:12	#8
Dr Sardonicus 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 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 upper 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. Last fiddled with by Dr Sardonicus on 2017-12-07 at 17:25*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
What to do with 16 digit twin, non-Mersenne primes?	RienS	Miscellaneous Math	15	2014-11-18 01:48
911 Digit Primes Quiz	Stargate38	Puzzles	4	2011-07-14 12:16
Primes from powers of 2 strings.	Flatlander	Puzzles	40	2011-02-10 09:42
Prime-Digit Primes...	petrw1	Puzzles	10	2009-12-16 21:58
listing 15-digit primes	fivemack	Software	8	2009-10-19 20:22

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

2017-12-07, 16:29	#6
axn Jun 2003 4902₁₀ Posts	Lower bounds for n=3,4,5 are 280, 2321, 19102. But I don't know if these are achievable.

2018-01-31, 14:45	#11
davar55 May 2004 New York City 2³×23² Posts	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?