mersenneforum.org Digit strings containing primes
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-12-07, 14:13 #1 davar55     May 2004 New York City 23·232 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, 14:48   #2
Dr Sardonicus

Feb 2017
Nowhere

445410 Posts

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.

2017-12-07, 15:12   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

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.

 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:25 #5 davar55     May 2004 New York City 23×232 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, 16:29 #6 axn     Jun 2003 490210 Posts Lower bounds for n=3,4,5 are 280, 2321, 19102. But I don't know if these are achievable.
2017-12-07, 16:50   #7
axn

Jun 2003

2·3·19·43 Posts

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.

 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
2017-12-14, 14:12   #9
davar55

May 2004
New York City

23·232 Posts

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?

2017-12-14, 14:28   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

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.

Last fiddled with by science_man_88 on 2017-12-14 at 14:34

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

 Similar Threads Thread Thread Starter Forum Replies Last Post RienS Miscellaneous Math 15 2014-11-18 01:48 Stargate38 Puzzles 4 2011-07-14 12:16 Flatlander Puzzles 40 2011-02-10 09:42 petrw1 Puzzles 10 2009-12-16 21:58 fivemack Software 8 2009-10-19 20:22

All times are UTC. The time now is 15:45.

Tue Apr 13 15:45:17 UTC 2021 up 5 days, 10:26, 1 user, load averages: 2.69, 2.46, 2.37