20141008, 16:20  #1 
Dec 2008
you know...around...
929 Posts 
Small but nontrivial prime puzzle
Can you find the maximum number of primes in an interval of the same size as an interval of smaller numbers in which no prime occured?
Disclaimer: if this puzzle is already known and wellstudied, the thread may be removed by any mod. Edit: Rephrasing of the problem: "Given two intervals of the same size, A = [a, a+x] and B = [b, b+x] with b > a, where there are no primes in A, find as many primes as possible in B." Last fiddled with by ATH on 20180209 at 21:52 
20141008, 22:11  #2 
"Bob Silverman"
Nov 2003
North of Boston
7635_{10} Posts 
Trivially, there is no maximum.

20141008, 22:30  #3 
∂^{2}ω=0
Sep 2002
República de Califo
2^{2}·2,939 Posts 
So we can have more primes than integers in the interval? Interesting...

20141008, 22:42  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
2·7·461 Posts 
Can you phrase the question a bit better? Are you just looking for more statements of the form 'there are no primes in 114..126; there are five primes in 1481..1493' or 'there are no primes in 524..540; there are six primes in 16057..16073' ?

20141008, 23:26  #5 
"Bob Silverman"
Nov 2003
North of Boston
3×5×509 Posts 

20141008, 23:31  #6 
"Bob Silverman"
Nov 2003
North of Boston
16723_{8} Posts 
Given an interval [x. x+A] in which no primes occur, one can find an
interval [y, y+A], for y > x such that the number of primes in the latter interval does not have a maximum because we can choose A to be arbitrarily large. i.e. as A > oo, we can find an interval [y, y+A] with an arbitrarily large number of primes. There is no maximum. lim sup is unbounded. Last fiddled with by R.D. Silverman on 20141008 at 23:32 
20141008, 23:32  #7 
"Bob Silverman"
Nov 2003
North of Boston
1110111010011_{2} Posts 
The problem did not say "interval of fixed size'.......

20141009, 02:11  #8 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2×5,179 Posts 
I think he is looking for a table.
Gap 4 appears at 7, there are 2 primes maximum in a 4size interval with start larger than 7. Any tween primes will do it. Of course, there are 3 primes in [2,6], i.e. {2,3,5}, but this interval does not start higher than 7. Gap 6 appears at 23, now there are 4 primes in [2..8], and 3 primes in [3..9], but neither 2, nor 3, are larger than 23, and there are no 3 primes in any 6sized interval that starts higher than 23, so the maximum is still 2. Two primes in trivial, any larger primes with a gap 2 or 4 will do it. Gap 8 appears at 89 (I think), and for any interval [89+1+x, 89+1+x+8] there can be maximum 3 primes (as 4 of them are divisible by 2, and at least one of the other is divisible by 3, we have to find 5 and 7 hitting exactly in one of those during sieving, so a solution is {97, 101, 103}, or {101, 103, 107}, etc. So, the table up to now is 2 2 4 2 6 2 8 3 etc. In this form, the problem is indeed, almost trivial. I say "almost" because I am still trying to "see it clear", it is not clear for me for example, if the magic set appears always right after the gap, etc. We discussed this on the thread about "how do you efficiently sieve for ntuple primes" (hint: the primes are more dense in "lower intervals", there was a theorem about). Last fiddled with by LaurV on 20141009 at 02:18 
20141009, 09:58  #9  
"Bob Silverman"
Nov 2003
North of Boston
3×5×509 Posts 
Quote:
permissible constellation in a fixed length interval is a difficult computation once the interval becomes even moderately large. 

20141009, 13:09  #10 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2×5,179 Posts 
Huh? You just have to "sieve" your nlength interval with primes up to n/2. That is the number you are looking for. The rest is "translation". For example, when I looked to gap 8 above, said that half of them are eliminated by 2 and another 1 is eliminated by 3, so there are 3 left. I was not interested in 5 or 7, because I can always "translate" the interval in such a way that 5 and 7 (which fall only once in the interval) fall on already cut out numbers. I can even translate it in such a way that both fall in the same number if I like (i.e. taking all intervals of 8 which contain a multiple of 35  there are infinitely many of them containing 3 primes). This is kinda very particular "constelation".

20141009, 22:37  #11  
"Bob Silverman"
Nov 2003
North of Boston
3·5·509 Posts 
Quote:
of length g occurs near exp(sqrt(g)). Say g = 1000000. The first gap will be near 1.97 x 10^434. Now, find an instance of the interval [x, x + 1000000] for x > 10^434 having the maximal number of primes. Enjoy. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve  mickfrancis  Factoring  2  20160506 08:13 
A small puzzle  Dubslow  Puzzles  18  20151201 07:41 
Zeta nontrivial zeros list  Damian  Analysis & Analytic Number Theory  11  20130111 05:54 
New puzzle about prime  wpolly  Puzzles  2  20090702 20:27 
Prime Puzzle #190  rogue  Puzzles  17  20060915 19:08 