Small but nontrivial prime puzzle

[R.D. Silverman]

Originally Posted by R.D. Silverman

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.

Oh. We are not allowed to assume the k-tuples conjecture, because it
is unproven.

[LaurV]

Originally Posted by R.D. Silverman

Oh. We are not allowed to assume the k-tuples conjecture, because it is unproven.

ok, ok, I can't argue with you either... I think you conspired with Serge to put all your heavy artillery on me, on all threads

For sure you are right here, but I didn't think you need to go so high with that table. All this argument is like when I say "finding prime numbers is easy" (which indeed it is!) and then you come and reply "yeah? then find a prime number with a billion digits".

Why should I do all those estimates? For your 1M gap, I take a generic interval, say starting at s=1M# (that is primorial of one million) and sieve it with primes up to 500k. Sieving is like taking a ruler with a million holes into it, and "cover one hole" for any composite (like I would cross out a number, in Eratosthenes sieve). Those primes (<500k) fall two times in the interval, and I might have trouble "fitting" the interval by translation. Then, what is left from my interval initial ruler is a "stencil" of possible primes. When I overpose the stencil over the axis of natural numbers, I see some numbers trough holes. I claim that I can "translate" the stencil on the N axis till I see only primes trough holes, i.e. I claim that the number of holes (be that k) in the stencil is the number you are looking for.

I don't need to find the "best constellation", I even don't need to find any constellation. I don't need "the smaller interval that can fit k primes" (in my understanding, that is a constellation, together with the arrangement of such primes), who cares about that? The key is that the interval is higher than the first apparition of the gap. If there is a better constellation, that is lower. There may be better fittings lower, as the primes are more dense in small numbers, but who cares?

Practically, if I make the product of all primes to s=1M#, let this be S, then I can fit my "stencil" on the N (the axes of natural numbers) in such a way that nS (one multiple of S) falls under a covered hole, and all the holes show only primes, and this "fitting" can be done in an infinite number of ways (by translation of the stencil toward infinity, and beyond... ).

Now, I agree that I am thinking as a programmer, and not as a mathematician, and I may be totally wrong. You may be seeing some "hole" in my ruler which I can't see. No hard feeling. As I said in the first post, I didn't really "grasped" what happens to larger numbers. I continued the reason from my previous post few steps higher (extending the table few lines) and it seems to always work.

[R.D. Silverman]

Originally Posted by LaurV

ok, ok, I can't argue with you either... I think you conspired with Serge to put all your heavy artillery on me, on all threads

For sure you are right here, but I didn't think you need to go so high with that table. All this argument is like when I say "finding prime numbers is easy" (which indeed it is!) and then you come and reply "yeah? then find a prime number with a billion digits".

Why should I do all those estimates? For your 1M gap, I take a generic interval, say starting at s=1M# (that is primorial of one million) and sieve it with primes up to 500k. Sieving is like taking a ruler with a million holes into it, and "cover one hole" for any composite (like I would cross out a number, in Eratosthenes sieve). Those primes (<500k) fall two times in the interval, and I might have trouble "fitting" the interval by translation. Then, what is left from my interval initial ruler is a "stencil" of possible primes. When I overpose the stencil over the axis of natural numbers, I see some numbers trough holes. I claim that I can "translate" the stencil on the N axis till I see only primes trough holes, i.e. I claim that the number of holes (be that k) in the stencil is the number you are looking for.

I don't need to find the "best constellation", I even don't need to find any constellation. I don't need "the smaller interval that can fit k primes" (in my understanding, that is a constellation, together with the arrangement of such primes), who cares about that? The key is that the interval is higher than the first apparition of the gap. If there is a better constellation, that is lower. There may be better fittings lower, as the primes are more dense in small numbers, but who cares?

Practically, if I make the product of all primes to s=1M#, let this be S, then I can fit my "stencil" on the N (the axes of natural numbers) in such a way that nS (one multiple of S) falls under a covered hole, and all the holes show only primes, and this "fitting" can be done in an infinite number of ways (by translation of the stencil toward infinity, and beyond... ).

Now, I agree that I am thinking as a programmer, and not as a mathematician, and I may be totally wrong. You may be seeing some "hole" in my ruler which I can't see. No hard feeling. As I said in the first post, I didn't really "grasped" what happens to larger numbers. I continued the reason from my previous post few steps higher (extending the table few lines) and it seems to always work.

Gibberish.

[mart_r]

Okay, I'm back... now, what I initially meant was to explicitly find an example with, say, more than 50 primes, which is still quite easy considering the prime gaps found so far. This gets hard by the time we're looking for more than 60 primes. [SIZE=1](My personal record is actually 67.)[/SIZE]

Of course, the theoretical maximum is \infty.

[R.D. Silverman]

Originally Posted by mart_r

Okay, I'm back... now, what I initially meant was to explicitly find an example with, say, more than 50 primes, .

This is still meaningless. Doesn't anyone bother to read??

I said very explicitly that one needed to bound the length of the interval. Why are you ignoring this? You have still failed to do so!

[mart_r]

Originally Posted by R.D. Silverman

This is still meaningless. Doesn't anyone bother to read??

I said very explicitly that one needed to bound the length of the interval. Why are you ignoring this? You have still failed to do so!

Admittedly, "the maximum number of primes..." may have been a bit misleading. Should be more along the lines of "How many can you find?"
After all, it's just some sort of puzzle.

The length of the interval is bounded by any large gap g one can find between two primes p and q. As long as the "Merit" g/log p is large enough, one can try looking for as many primes > q as one can find in an interval as large as that gap.

[LaurV]

Originally Posted by mart_r

(My personal record is actually 67.)

Oh, I didn't know that gaps between primes can be odd... According with these guys, the gaps can be defined to be odd too. I always used the "even" definition. So, your solution is for 66 or for 68? Anyhow, did you find all 14 of them? Or you found 15?

It took my computer less than 5 seconds, with a (not so good written) pari script. I still claim that this problem is trivial.

BTW, the "manual" solution I gave for 6 and 8 was wrong, hehe, my script found 3 primes in a 6-long interval and 4 primes in an 8-long interval (well, I was a bit idiot when I counted them by hand - imagine 11, 13, 17, 19, the Chinese Reminder theorem has to be considered when you sieve).

So, with even gaps, you have 4 primes in a 8 or 10 gap, 5 in a 12 and 14, ... 7 in a 20... 14 in a 66... etc, up to 17 in an 80-long interval.

There is not clear right now if there are 20 or 21 in a 100 interval (there are quite a lot of combinations for CRT to test, but some of them can be discarded, however I have run out of stack with the lists and doing a looping solution would take a lot of time).

[mart_r]

Originally Posted by LaurV

Oh, I didn't know that gaps between primes can be odd... According with these guys, the gaps can be defined to be odd too. I always used the "even" definition. So, your solution is for 66 or for 68? Anyhow, did you find all 14 of them? Or you found 15?

I was about eight years old when I was told that, when writing a story or something like that, I should avoid using the same word over and over again.
Maybe I should have used the word "primes" behind that 67 yet once again...?

[VBCurtis]

LaurV-
When the OP claimed he found 67 primes as his personal best, he meant that he found a gap between primes of some (unstated) length, then searched higher than that gap and found 67 primes within an interval of the same size as the one he didn't state. It's not much of a puzzle without interval lengths, as RDS states.

Your ruler/stencil idea overlooks the substantial number of candidates that factor as products of primes not on your ruler. You have no reason to assume you can always shift the ruler to avoid such composites, and seem to be making conclusions about large numbers ("always") based on seeing it work for small numbers.

As a programmer, perhaps you might consider using "trivial" as a description for polynomial-time tasks. Is this puzzle as you interpret it polynomial-time in the length of the interval?

[R.D. Silverman]

Originally Posted by LaurV

Oh, I didn't know that gaps between primes can be odd... According with these guys, the gaps can be defined to be odd too. I always used the "even" definition. So, your solution is for 66 or for 68? Anyhow, did you find all 14 of them? Or you found 15?

It took my computer less than 5 seconds, with a (not so good written) pari script. I still claim that this problem is trivial.

).

Arrogant, ignorant, and argumentative. You don't know enough to be making any such claim. When are you going to stop prattling about a subject that
you clearly do not understand.

The problem is NOT trivial under
any definition of 'trivial' that you can name. I suggest you look at the time
complexity function for finding the maximal admissible constellation among all
intervals [x, x+A] for given A and x > y for y ~ exp(sqrt(A)).

Your claim of 'trivial' requires that the complexity function is polynomial.
Back up your claim. Prove that it.

[fivemack]

Do you mean something like this (using the table in https://en.wikipedia.org/wiki/Prime_gap#Further_results)

z=303371455241 is prime; z+500 is prime; there are no primes between them; there are 44 primes between z+10775601048 and z+10775601548 inclusive. However http://oeis.org/A008407/b008407.txt and standard conjectures indicate that there should be a constellation of length 494 containing 90 primes, somewhere.

z=1425172824437699411 is prime, z+1476 is the next prime; there are 73 primes between z+w-1476 and z+w inclusive for w=5318916180. b008407 similarly says there should be a constellation of 230 primes of length 1476, somewhere up in the impractically large integers.

This is a reasonably fun programming exercise - efficient sieve plus efficient primality test on 64-bit integers. Whereas finding a single minimal-length prime 24-tuplet (diameter is 100, i.e. k and k+100 are prime) would be a significantly hard problem and involve searching around 2^90.