Small but nontrivial prime puzzle

mart_r · 2014-10-08, 16:20

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 well-studied, 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."

R.D. Silverman · 2014-10-08, 22:11

Quote:

Originally Posted by mart_r

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 well-studied, the thread may be removed by any mod.

Trivially, there is no maximum.

ewmayer · 2014-10-08, 22:30

So we can have more primes than integers in the interval? Interesting...

fivemack · 2014-10-08, 22:42

Quote:

Originally Posted by mart_r

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 well-studied, the thread may be removed by any mod.

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' ?

R.D. Silverman · 2014-10-08, 23:26

Quote:

Originally Posted by ewmayer

So we can have more primes than integers in the interval? Interesting...

The problem did not bound the length of the interval.

R.D. Silverman · 2014-10-08, 23:31

Quote:

Originally Posted by R.D. Silverman

The problem did not bound the length of the interval.

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.

R.D. Silverman · 2014-10-08, 23:32

Quote:

Originally Posted by fivemack

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' ?

The problem did not say "interval of fixed size'.......

LaurV · 2014-10-09, 02:11

I think he is looking for a table.

Gap 4 appears at 7, there are 2 primes maximum in a 4-size 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 6-sized 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 n-tuple primes" (hint: the primes are more dense in "lower intervals", there was a theorem about).

R.D. Silverman · 2014-10-09, 09:58

Quote:

Originally Posted by LaurV

In this form, the problem is indeed, almost trivial. I say "almost" because I am still trying to "see it clear",.

Wrong again. In this form it is anything BUT trivial. Finding the largest
permissible constellation in a fixed length interval is a difficult computation once
the interval becomes even moderately large.

LaurV · 2014-10-09, 13:09

Huh? You just have to "sieve" your n-length 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".

R.D. Silverman · 2014-10-09, 22:37

Quote:

Originally Posted by LaurV

Huh? You just have to "sieve" your n-length 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".

By Shanks' estimate the first gap
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.

2014-10-08, 16:20	#1
mart_r 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 well-studied, 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 2018-02-09 at 21:52

2014-10-09, 02:11	#8
LaurV 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 4-size 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 6-sized 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 n-tuple primes" (hint: the primes are more dense in "lower intervals", there was a theorem about). Last fiddled with by LaurV on 2014-10-09 at 02:18

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	2016-05-06 08:13
A small puzzle	Dubslow	Puzzles	18	2015-12-01 07:41
Zeta nontrivial zeros list	Damian	Analysis & Analytic Number Theory	11	2013-01-11 05:54
New puzzle about prime	wpolly	Puzzles	2	2009-07-02 20:27
Prime Puzzle #190	rogue	Puzzles	17	2006-09-15 19:08

2014-10-08, 22:30	#3
ewmayer ∂²ω=0 Sep 2002 República de Califo 2²·2,939 Posts	So we can have more primes than integers in the interval? Interesting...

2014-10-09, 13:09	#10
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2×5,179 Posts	Huh? You just have to "sieve" your n-length 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".