Small but nontrivial prime puzzle

[R.D. Silverman]

Originally Posted by 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 42 primes between z+58818606 and z+58819106 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 63 primes between z+w-1476 and z+w inclusive for w=123557462. 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.

Actually there is a proof by Schinzel (and independently by my ex)
that the interval [13,113] is the last interval of length 100 containing 25
primes and that the most one can find in length 100 infinitely often is
23 primes.

I don't know if there are any intervals of length 100 containing exactly
24 primes. There can be only finitely many.

[axn]

Originally Posted by R.D. Silverman

I don't know if there are any intervals of length 100 containing exactly
24 primes. There can be only finitely many.

http://www.opertech.com/primes/k-tuples.html

[LaurV]

Originally Posted by VBCurtis

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.

Oh, my understanding of the problem, then, was completely wrong. The OP (after I read his explanation, sorry for the delay, but here was night) wants in fact that you can pick any known prime gap, either found by yourself or taken from the tables, but known, this means that you know the length of the gap, G (i.e. bounded), and the starting position S, and then searching (sieving) above the S+G limit, how many primes can you find that can fit together in a G-sized interval.

The problem is still easy, nothing puzzling about it. Sieving over those big gaps of thousands may give you a much better chance, but proving primality there gets slower. However, there are enough gaps on those tables where finding primes would be easy (like around 70 to 500 digits dtarting point and up to 30000 in size. The P155 from Dana Jacobsen is very tempting, especially as she is also member of this forum, hehe. I can not believe that one can't get more than 67 primes in an >11k interval of 155 digit numbers. Five minutes of programming effort in front of the coffee cup this nice Saturday (my free Saturday, so you can't get rid of me and about 15 minutes of waiting (in fact browsing the forum) and here you are, using the largest known maximal gap that is 1476 and its starts at P19 = 1425172824437699411: There are 73 primes in a 1476-long interval, starting from 1425172829756614139

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.[]

No, it does not. Think about why I said that the ruler has to be centered around those points. There, all combinations of the primes you talk about will fall in a single hole, which is covered. There is no other way.

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?

I never claim the problem to be polinomial, see where I mentioned CRT. My understanding of the problem was that you have to say what is the "maximal" number of primes that you can put there (in the interval G mentioned above), and not to find few specific primes. In this respect RDS was right all along (yeah, I never said I am not a crank, and that is me, arrogant, ignorant, and argumentative ). Your interval where the "maximal" could fit it can start at x_i (mod p_i) and you have to take all combinations of 0<xi<pi, for primes pi<G/2. Of course this is not polynomial.

It might be my wrong handling of English, or my stupidity either, you can pick, but (to make an analogy without connection to our subject ) it is trivial for me to print all n-factorial permutations of n symbols in lexicographic order, but I don't think any of us would claim that such activity will take a polynomial time in n.

[mart_r]

Originally Posted by R.D. Silverman

Actually there is a proof by Schinzel (and independently by my ex)
that the interval [13,113] is the last interval of length 100 containing 25
primes and that the most one can find in length 100 infinitely often is
23 primes.

I don't know if there are any intervals of length 100 containing exactly
24 primes. There can be only finitely many.

Doesn't the interval [13,113] have a length of 101?
According to the k-tuple conjecture, an interval of length 100 can only contain at most 23 primes infinitely often. With interval length=101, there may be 24 (infinitely often as well). Apparently Mr Chermoni and Mr Wroblewski are on the hunt for such a dense cluster. May still take a few years till it's found.

@ fivemack:
You got it. 73 primes is the new record.

[R.D. Silverman]

Originally Posted by mart_r

Doesn't the interval [13,113] have a length of 101?
.

The last time I looked, the length of a line segment [a,b] is b-a.
length != "cardinality"

[LaurV]

Originally Posted by mart_r

@ fivemack:
You got it. 73 primes is the new record.

He edited his post AFTER he saw my solution. Supermods can do that. But he forgot to edit the quotations to his posts in the subsequent posts. Bad supermod! Bad! See RDS's post after his post, with the quotation, where Tom only found 63 primes
(gotcha!)

[VBCurtis]

Originally Posted by LaurV

No, it does not. Think about why I said that the ruler has to be centered around those points. There, all combinations of the primes you talk about will fall in a single hole, which is covered. There is no other way.

There are 25 primes in the interval [13,113]. If your ruler idea were correct, there should be 25 primes in higher intervals also; but it is proven no higher 101-length intervals exist with 25 primes. Do I misunderstand your claim?
-Curtis

[mart_r]

Originally Posted by LaurV

He edited his post AFTER he saw my solution. Supermods can do that. But he forgot to edit the quotations to his posts in the subsequent posts. Bad supermod! Bad! See RDS's post after his post, with the quotation, where Tom only found 63 primes
(gotcha!)

Looks like it... so to you, LaurV.

@ RDS: Agreed.
I'm still somewhat confused about that issue with cardinal and ordinal infinities. So many definitions, so many axioms, and so little time...

[fivemack]

I left the calculation running overnight and edited the post in the morning before hitting the update button and seeing what other people had done overnight; I then went to Blackpool for the weekend to see my cousins' extremely cute small babies.

[LaurV]

Originally Posted by VBCurtis

There are 25 primes in the interval [13,113]. If your ruler idea were correct, there should be 25 primes in higher intervals also; but it is proven no higher 101-length intervals exist with 25 primes. Do I misunderstand your claim?
-Curtis

I saw your post yesterday, but wanted to be sure before going deeper in the sh!t
My ruler shows only 24 holes, and there is no way you could get 25, even if you sieve only to primes under (and including) 19. You only get 24 holes when the interval starts at 217153, 1314277, 1639987, 3465013, 4811743, 4887847, 6234577, 8059603, 8385313, or 9482437 (mod 9699690). For all the other 9699690-10=9699680 cases, the ruler shows fewer holes (between 2 and 23, when primes up to 47 are used for sieving). So, your number is 24.

Technically (and offtopic), because there is a sieving possibility which only lets 2 holes in the ruler (i.e. there is no possibility to cover all the ruler with primes below 50), we can use two additional primes to cover the holes, so there should be a gap of at least 100 after x, where x is 0 (mod 2, 3, 5, 7, 29, 43, 53, 59), 10 (mod 11), 7 (mod 13), 16 (mod 19), 9 (mod 23), 20 (mod 31), 6 (mod 37), 30 (mod 47). You can combine them by CRT to see where this gap is, and if really is there. Of course, this is not the first gap, and it has nothing to do with our problem

[fivemack]

I want to find the shortest set of 101 consecutive primes greater than 2^256. Current best I've found is 12523:

s=2^256; w=6423013; k=12522
p=0; for(c=0,k,if(isprime(s+w-c),p=p+1)); p

The admissable-set work says that k=558 ought to be possible, but if you can manage that you're likely to find yourself obliged to give a speech at the International Congress of the International Mathematical Union.

I will donate to the forum $(0.1 * (12558-kmin)) for the working (w,k) pair (both positive!) with smallest k, posted here before 1 January 2015; I will be very happy (and it would be a nice publishable piece of work) if someone finds a way to cost me $600 or more, whether by using the Chinese Remainder Theorem in a clever way or otherwise.

Please don't make a BOINC project; I'd really rather people not squander $1000 of the electricity bills and computer depreciation of third parties in order to make $100 for the forum.