Small but nontrivial prime puzzle

[mart_r]

Originally Posted by MattcAnderson

Hi,
I believe I understand the original puzzle.

Actually, the original puzzle was wrongly phrased. The correctly phrased puzzle is:
"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."
(Is there any chance this can be modified in the OP?)

One or two new ideas prompted me to continue my work on this, and right now I'm at 96 primes.
I'll let the program run for another week or two, hoping to find a 100 (which seems unlikely, but not impossible to find), and then post results. Unless someone can beat me at this game.

[VBCurtis]

What interval length? Your new phrasing makes x appear arbitrary; is that your intent, or are you pursuing a record for a specific interval length?

[science_man_88]

Originally Posted by mart_r

Actually, the original puzzle was wrongly phrased. The correctly phrased puzzle is:
"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."
(Is there any chance this can be modified in the OP?)

One or two new ideas prompted me to continue my work on this, and right now I'm at 96 primes.
I'll let the program run for another week or two, hoping to find a 100 (which seems unlikely, but not impossible to find), and then post results. Unless someone can beat me at this game.

We know that (n#,n#+nextprime(n)-1) is an interval with no primes. The interval including endpoints has nextprime(n) numbers. Via pigeonhole principle, we get there can be at most eulerphi(nextprime(n)-1)+1 or (nextprme(n)-1)/3 whichever is lower.

[mart_r]

Originally Posted by VBCurtis

What interval length? Your new phrasing makes x appear arbitrary; is that your intent, or are you pursuing a record for a specific interval length?

That is actually sort of intended. x must come from a previously known prime gap, and choosing such a gap is not necessarily trivial for finding the primes in B.

[mart_r]

Originally Posted by science_man_88

We know that (n#,n#+nextprime(n)-1) is an interval with no primes. The interval including endpoints has nextprime(n) numbers. Via pigeonhole principle, we get there can be at most eulerphi(nextprime(n)-1)+1 or (nextprme(n)-1)/3 whichever is lower.

It's not about the theoretical number of primes (a.k.a. k-tuple conjecture) but actual results. You'd have a hard time finding 96 primes in an interval of, say, [n#+2, n#+n+1] where the primes must be as big as n#.

The Gapcoin-gap with an interval of 8349 consecutive composite integers is a very good point of reference for this puzzle, since it has the highest known merit and the primes involved are with 87 digits relatively small. Below 87 digits, the TOeSilva gap of 1476 would be next best, but the chances of finding a large number of primes in an interval where on average 42 primes are expected is at some point bigger compared to the advantage of speed where smaller numbers are involved.

[science_man_88]

Originally Posted by mart_r

It's not about the theoretical number of primes (a.k.a. k-tuple conjecture) but actual results. You'd have a hard time finding 96 primes in an interval of, say, [n#+2, n#+n+1] where the primes must be as big as n#.

The Gapcoin-gap with an interval of 8349 consecutive composite integers is a very good point of reference for this puzzle, since it has the highest known merit and the primes involved are with 87 digits relatively small. Below 87 digits, the TOeSilva gap of 1476 would be next best, but the chances of finding a large number of primes in an interval where on average 42 primes are expected is at some point bigger compared to the advantage of speed where smaller numbers are involved.

But theory tells you were you can find them to narrow the search so your example for 100 needs eulerphi(nextprime(n)-1) to be 99 in theory ( without pointing out that interval and gap aren't the same) from this we get that there is no easy interval, because 99 is not a totient.

[axn]

Originally Posted by science_man_88

We know that (n#,n#+nextprime(n)-1) is an interval with no primes.

Do we know this? What about n#+1?

[science_man_88]

Originally Posted by axn

Do we know this? What about n#+1?

Yeah I realized that.

[mart_r]

There are   0 primes among 8349 consecutive integers starting from 293703234068022590158723766104419463425709075574811762098588798217895728858676728143228.
There are 100 primes among 8349 consecutive integers starting from 295160409843753748151012998579391505598704703954606722982263291976741858941955805490779.

In fact, these 100 primes only need an interval of 8263 consecutive integers.