Small but nontrivial prime puzzle - Page 7

rajula · 2014-10-26, 04:38

Quote:

Originally Posted by rajula

I'll report back if I abandon this search (until the next stupid idea I come up with) or if a new record is found.

Luckily a new record: k = 7970 with

Code:

s = 115936150054587808354957396106894919008217856298102019235309783713530182870319

Notice that finding this with my program took about a week using two cores. With that amount of computing time maybe a more direct search without playing around with the "good" intervals would have found a similar hit. I'll leave one core still running while I go to a conference for a week. Let's see if anything better is found while I'm away. (If it were a holiday trip, I would be sure to find a new Mersenne prime with that program!)

bsquared · 2014-10-27, 13:02

Quote:

Originally Posted by rajula

Luckily a new record: k = 7970 with

Code:

s = 115936150054587808354957396106894919008217856298102019235309783713530182870319

Notice that finding this with my program took about a week using two cores. With that amount of computing time maybe a more direct search without playing around with the "good" intervals would have found a similar hit. I'll leave one core still running while I go to a conference for a week. Let's see if anything better is found while I'm away. (If it were a holiday trip, I would be sure to find a new Mersenne prime with that program!)

Nice one!

I haven't been running mine but I think I'll start it back up now ;)

LaurV · 2014-10-28, 18:51

Quote:

Originally Posted by fivemack

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 am very sorry I can not give a speech to the said elevated assembly...

That is because there is no set of 558 numbers containing 101 primes.
Sieving any 558-long (559 consecutive numbers) interval with small primes in all possible situations will eliminate more than 458 numbers, no matter what, and I can prove this.

If you limit your small primes to 20 (i.e. the first 8 primes, from 2 to 19) there are 15156 "constellations" left (from 9699690 possible) with more than 100 primes - some as short as 535 numbers, from which 101 survive sieving, if the interval starts as 9699397 (mod 9699690) - and some others packing 105 survivors in 555 consecutive numbers, like the one starting at 9699397 (mod 9699690).

Adding 23 to the sieve will let only 935 possible "constellations" from 223092870 possible, the shortest packing 101 survivors in 547 consecutive numbers, (two such, starting at 223092607 and 223092587 (mod 223092870)) and the longest packing 103 survivors in 559 numbers (many, for example, the one starting at 223092629).

Now, put 29 into sieve and you end up with only 128 possible "stencils" (from 6469693230), sizes between 551 and 559, few still packing 102 survivors.

And 31 marches into the sieve, killing everything in its way, after which you end up with this:

Code:

[[24732872491, 200560490130, 101, 559], [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1]]
[[181693256071, 200560490130, 101, 559], [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1]]
[[18867233501, 200560490130, 101, 559], [1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1]]
[[175827617081, 200560490130, 101, 559], [1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1]]

(someone should do something with that CODE tags!!! they used to work well in the past!) [edit: expecting the picture with a kitty running from two biscuits]

Indeed, there are only 4 possible "stencils" surviving (from 200560490130 possible, with the offsets in the first column), and you can see by eyes that it is no way to match a 37 on any of them, in any way, without killing at least one 1.

Indeed, sieving with 37 lets nothing left.

What a pity I can't give a speech about it...
Or... do you accept that I come and I give a speech about how I didn't find 101 primes in 558-long interval...

[I am still digging into this problem. I have few nice "records". Keeping you in the fog, for a while... I still have some paths to explore... (unfortunately my time is quite limited, but it is progressing slowly, I put into it about 10-12 hours, spread like 1-2 hours in the evening after the job/shower/dinner/homework (with the little devil here in the house, she started trigonometry, grade 11, and she is a pain in the butt when she can't solve those thingies by herself)]

Xyzzy · 2014-10-28, 22:59

axn · 2014-10-29, 03:10

Quote:

Originally Posted by LaurV

I am very sorry I can not give a speech to the said elevated assembly...

That is because there is no set of 558 numbers containing 101 primes.

From the link I posted earlier (http://www.opertech.com/primes/k-tuples.html), the best width for an admissible set of 101 primes is 573 (proven by exhaustive search). However, for _100_ primes, it is 559. So, it would appear that Tom was referring to the wrong line.

LaurV · 2014-10-29, 04:49

Grrr... Is there any path I am walking, which was not previously walked at least hundreds of times?

Thanks for pointing that to me...

Waiting to get home tonight to see which of my "records" still "stands"... The last version of ~~siever~~ stencil puncher which I finished last night is extremely fast**, and I suspect that on those links of yours, the "exhaustive" means that the sieving was only done to primes under 50 or so. I will try to check those tables a bit more "exhaustive", see if I find something new, or waste the time.

----------
** essentially, I start with a list of vectors of bits. Initially the list contains vectors with all bits 1, and there is one vector for every size of the interval, from 3*N to Size+1, where N is the number of primes I am looking for, and Size is the interval size. In our case, the initial list contains "mersenne numbers" from 2^303-1 to 2^559-1 (seen as vectors of 303 ones, up to 559 ones, they are expanded with binary() when writing into the output log file, for clarity). I don't exclude the even numbers, and I have a good reason for it. A "sieving step" is done for each prime p, starting from 2, to the maximum prime I am going to sieve. A "sieving step" practically takes all vectors in the input list, and for each of them is putting p-1 vectors in the output list, where vector m is sieved with p, considering that it starts at m (mod p). The output list generated in this way become the input list of the next sieving step (the next prime), and the former input list is discarded.

This is extremely fast, but it has the disadvantage that the output list "explodes" with each sieving step. Therefore precautions are taken to reduce the size of the intermediary lists, like for example all intermediary vectors with less than N primes are discarded (fast counting function need to be done, or keeping track of the eliminated 1s or of the hit 0s, I use a combination of the methods, which still take a considerable time, comparable with the sieving itself). Also, vectors which do not have a 1 as the last component are eliminated, without counting or sieving - they are not added to the output list, but they are not "lost", that is why I use sizes from "3*N, and not only sieving Size+1 vectors: there may be a vector which packs N primes in a shorter size than Size, and in this way the list is kept shorter and non-redundant, which increase the speed of the following "sieving steps" (there is a practical reason why I have taken 3*N, too). [edit: remark that all vectors have the first bit set a 1, as I never sieve with m=0, i.e. there is no interval starting at 0 mod some sieving prime. So only the last bit is tested, not the first, and the sieving is done from the end, therefore the bad vectors are eliminated even before any sieving is done].

This method worked for small "rulers" at the beginning of this discussion topic, but you see, the memory is filled up "exponentially" when N and Size are larger. Of course, allocatemem() does not help at N=101 and Size>500 at all, unless there are many gigs of memory available. Therefore the 90% of the "work" I was talking about is "deloopization" and "derecursivation", done to keep the memory low, save periodical chunks on disk, etc. Pari is quite stupid at reading input parameters from files, you can read only the last line of the file, or all lines in a vector, and that is without talking about speed. And that is how ~30 lines of pari/gp became ~400 lines of pari/C (still using pari for commodity of functions as "chinese()", etc). Each vector, of course, has a "tracking offset" in front (see the previous post), combined by CRT, from which the prime's modules are easy to reconstruct.

Once the right "offsets" are found (mod maxp#), their relative values (offset of the offset?) are put in a vector v, and used as in "forstep(x,infinite,v, 'count' primes in a Size interval starting from x)". Here again, pari is very convenient to use, due to the possibility to place the incrementing steps in a vector. If the 'count' is satisfactory (it is coming "close enough" to N), then some "precprime()"s are counted in front of x, and some "nextprime()"s are counted behind of x+Size, the reason is that maybe we didn't find 101 primes there, but we still can break some other records, like (fictive example) "93 primes in a 543-size interval starting from this y" (the y is a bit smaller or equal to x).

And that is all.

rajula · 2014-11-02, 06:26

Quote:

Originally Posted by rajula

I'll leave one core still running while I go to a conference for a week. Let's see if anything better is found while I'm away. (If it were a holiday trip, I would be sure to find a new Mersenne prime with that program!)

I'm back. Nothing better found, so I (again) stopped my search.

Good luck finding a new record bsquared!

bsquared · 2014-11-09, 21:04

I've found a few more 8k's, but nothing better. Your record will stand unless someone else gets inspired.

Nice work!

mart_r · 2018-01-03, 19:07

I've utilized the recent find of Gapcoin to juxtapose:

Code:

There are  0 primes among 8349 consecutive integers starting from 293703234068022590158723766104419463425709075574811762098588798217895728858676728143228.
There are 85 primes among 8349 consecutive integers starting from 308659094021045384923259706078475073626915452573921506751799118286266628069157603874800.

mart_r · 2018-01-06, 20:46

Update:

Code:

There are  0 primes among 8349 consecutive integers starting from 293703234068022590158723766104419463425709075574811762098588798217895728858676728143228.
There are 91 primes among 8349 consecutive integers starting from 293720462720488820043450948350484244298158505892405044271861364129508508779060779927799.

Now that is a result I can live with.
At least until a gap of merit 45+ is found.

P.S. Extra thanks to Thomas Engelsma for providing the data set for an admissible 1059-tuplet.

MattcAnderson · 2018-01-08, 21:50

Hi,

I believe I understand the original puzzle.

The Hardy Littlewood second conjecture states that the densest set of n prime numbers is the first n prime numbers. This can be written in symbols

π(x+n) - π(x) is less than or equal to π(n)

where π(n) is the prime counting function.

See this webpage.

Regards,
Matt

2014-10-29, 04:49	#72
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 Posts	Grrr... Is there any path I am walking, which was not previously walked at least hundreds of times? Thanks for pointing that to me... Waiting to get home tonight to see which of my "records" still "stands"... The last version of ~~siever~~ stencil puncher which I finished last night is extremely fast, and I suspect that on those links of yours, the "exhaustive" means that the sieving was only done to primes under 50 or so. I will try to check those tables a bit more "exhaustive", see if I find something new, or waste the time. ---------- essentially, I start with a list of vectors of bits. Initially the list contains vectors with all bits 1, and there is one vector for every size of the interval, from 3N to Size+1, where N is the number of primes I am looking for, and Size is the interval size. In our case, the initial list contains "mersenne numbers" from 2^303-1 to 2^559-1 (seen as vectors of 303 ones, up to 559 ones, they are expanded with binary() when writing into the output log file, for clarity). I don't exclude the even numbers, and I have a good reason for it. A "sieving step" is done for each prime p, starting from 2, to the maximum prime I am going to sieve. A "sieving step" practically takes all vectors in the input list, and for each of them is putting p-1 vectors in the output list, where vector m is sieved with p, considering that it starts at m (mod p). The output list generated in this way become the input list of the next sieving step (the next prime), and the former input list is discarded. This is extremely fast, but it has the disadvantage that the output list "explodes" with each sieving step. Therefore precautions are taken to reduce the size of the intermediary lists, like for example all intermediary vectors with less than N primes are discarded (fast counting function need to be done, or keeping track of the eliminated 1s or of the hit 0s, I use a combination of the methods, which still take a considerable time, comparable with the sieving itself). Also, vectors which do not have a 1 as the last component are eliminated, without counting or sieving - they are not added to the output list, but they are not "lost", that is why I use sizes from "3N, and not only sieving Size+1 vectors: there may be a vector which packs N primes in a shorter size than Size, and in this way the list is kept shorter and non-redundant, which increase the speed of the following "sieving steps" (there is a practical reason why I have taken 3N, too). [edit: remark that all vectors have the first bit set a 1, as I never sieve with m=0, i.e. there is no interval starting at 0 mod some sieving prime. So only the last bit is tested, not the first, and the sieving is done from the end, therefore the bad vectors are eliminated even before any sieving is done]. This method worked for small "rulers" at the beginning of this discussion topic, but you see, the memory is filled up "exponentially" when N and Size are larger. Of course, allocatemem() does not help at N=101 and Size>500 at all, unless there are many gigs of memory available. Therefore the 90% of the "work" I was talking about is "deloopization" and "derecursivation", done to keep the memory low, save periodical chunks on disk, etc. Pari is quite stupid at reading input parameters from files, you can read only the last line of the file, or all lines in a vector, and that is without talking about speed. And that is how ~30 lines of pari/gp became ~400 lines of pari/C (still using pari for commodity of functions as "chinese()", etc). Each vector, of course, has a "tracking offset" in front (see the previous post), combined by CRT, from which the prime's modules are easy to reconstruct. Once the right "offsets" are found (mod maxp#), their relative values (offset of the offset?) are put in a vector v, and used as in "forstep(x,infinite,v, 'count' primes in a Size interval starting from x)". Here again, pari is very convenient to use, due to the possibility to place the incrementing steps in a vector. If the 'count' is satisfactory (it is coming "close enough" to N), then some "precprime()"s are counted in front of x, and some "nextprime()"s are counted behind of x+Size, the reason is that maybe we didn't find 101 primes there, but we still can break some other records, like (fictive example) "93 primes in a 543-size interval starting from this y" (the y is a bit smaller or equal to x). And that is all. Last fiddled with by LaurV on 2014-10-29 at 05:03*

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

2014-10-28, 22:59	#70
Xyzzy "Mike" Aug 2002 10000000100000₂ Posts

2014-11-09, 21:04	#74
bsquared "Ben" Feb 2007 3513₁₀ Posts	I've found a few more 8k's, but nothing better. Your record will stand unless someone else gets inspired. Nice work!

2018-01-08, 21:50	#77
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 1100100000₂ Posts	Hi, I believe I understand the original puzzle. The Hardy Littlewood second conjecture states that the densest set of n prime numbers is the first n prime numbers. This can be written in symbols π(x+n) - π(x) is less than or equal to π(n) where π(n) is the prime counting function. See this webpage. Regards, Matt