mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2017-12-07, 14:13   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

5×7×112 Posts
Default 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.)
davar55 is offline   Reply With Quote
Old 2017-12-07, 14:48   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×23×37 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-12-07, 15:12   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-12-07, 16:03   #4
axn
 
axn's Avatar
 
Jun 2003

5,179 Posts
Default

For N=2, length is 32. Here is one such string 23129411343747175359619673838979
axn is online now   Reply With Quote
Old 2017-12-07, 16:25   #5
davar55
 
davar55's Avatar
 
May 2004
New York City

102138 Posts
Default

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
davar55 is offline   Reply With Quote
Old 2017-12-07, 16:29   #6
axn
 
axn's Avatar
 
Jun 2003

5,179 Posts
Default

Lower bounds for n=3,4,5 are 280, 2321, 19102. But I don't know if these are achievable.
axn is online now   Reply With Quote
Old 2017-12-07, 16:50   #7
axn
 
axn's Avatar
 
Jun 2003

5,179 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
axn is online now   Reply With Quote
Old 2017-12-07, 17:12   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×23×37 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2017-12-14, 14:12   #9
davar55
 
davar55's Avatar
 
May 2004
New York City

5×7×112 Posts
Default

Quote:
Originally Posted by axn View Post
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?
davar55 is offline   Reply With Quote
Old 2017-12-14, 14:28   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by davar55 View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-01-31, 14:45   #11
davar55
 
davar55's Avatar
 
May 2004
New York City

5×7×112 Posts
Default

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?
davar55 is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 07:54.


Sun Nov 28 07:54:27 UTC 2021 up 128 days, 2:23, 0 users, load averages: 1.32, 0.97, 0.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.