mersenneforum.org Small but nontrivial prime puzzle
 Register FAQ Search Today's Posts Mark Forums Read

 2014-10-08, 16:20 #1 mart_r     Dec 2008 you know...around... 2×73 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-08, 22:11   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

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.

 2014-10-08, 22:30 #3 ewmayer ∂2ω=0     Sep 2002 República de California 2×13×449 Posts So we can have more primes than integers in the interval? Interesting...
2014-10-08, 22:42   #4
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

144548 Posts

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

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

Nov 2003

746010 Posts

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.

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

Nov 2003

164448 Posts

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.

Last fiddled with by R.D. Silverman on 2014-10-08 at 23:32

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

Nov 2003

746010 Posts

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

 2014-10-09, 02:11 #8 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 24·613 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
2014-10-09, 09:58   #9
R.D. Silverman

Nov 2003

746010 Posts

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.

 2014-10-09, 13:09 #10 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 24×613 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".
2014-10-09, 22:37   #11
R.D. Silverman

Nov 2003

22×5×373 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Factoring 2 2016-05-06 08:13 Dubslow Puzzles 18 2015-12-01 07:41 Damian Analysis & Analytic Number Theory 11 2013-01-11 05:54 wpolly Puzzles 2 2009-07-02 20:27 rogue Puzzles 17 2006-09-15 19:08

All times are UTC. The time now is 01:19.

Wed Dec 1 01:19:57 UTC 2021 up 130 days, 19:48, 0 users, load averages: 1.53, 1.50, 1.43

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.