mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2014-10-08, 16:20   #1
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

2×73 Posts
Default 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
mart_r is offline   Reply With Quote
Old 2014-10-08, 22:11   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by mart_r View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2014-10-08, 22:30   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2×13×449 Posts
Default

So we can have more primes than integers in the interval? Interesting...
ewmayer is offline   Reply With Quote
Old 2014-10-08, 22:42   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

144548 Posts
Default

Quote:
Originally Posted by mart_r View Post
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' ?
fivemack is offline   Reply With Quote
Old 2014-10-08, 23:26   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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 is offline   Reply With Quote
Old 2014-10-08, 23:31   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2014-10-08, 23:32   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by fivemack View Post
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'.......
R.D. Silverman is offline   Reply With Quote
Old 2014-10-09, 02:11   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·613 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2014-10-09, 09:58   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2014-10-09, 13:09   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24×613 Posts
Default

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".
LaurV is offline   Reply With Quote
Old 2014-10-09, 22:37   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

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

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

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.