Small but nontrivial prime puzzle - Page 6

bsquared · 2014-10-15, 16:39

Some notes:

First attempt pre-sieved each range of 1e9 to get ~30e6 candidate primes. Followed by a multi-threaded PRP check of candidates using mpz_probab_prime_p with 1 MR witness to get ~5e6 PRPs. Finally, crawl through and find small k's. Rinse, repeat.

Second attempt tries to be smarter. It also does the pre-sieve on 1e9 ranges to get a candidate pool 'P'. Then for each of N subintervals of P, each with M candidates, record the length L. Find 'dense' subintervals: in the set of N subintervals, do (single-threaded) PRP checks on those where L is more than 3 standard deviations below the average length. Then the usual crawl for small k's. I used N = 200000, M = 500, which gives an average L of ~16000, with std of ~600. Approx 0.1% of subintervals are dense by the above metric (i.e., have 500 candidate primes in a k of <14k-ish).

The second method is a thousand times faster than the first, but of course is not as thorough. For example it has missed both sub-10k intervals that the first method found. The best it found was [791883651805, 9972] through w=1e12 (which took 43 minutes). I might try playing with N or M. Or not. Any other thoughts?

What cool tricks are others trying?

p.s.
Fivemack you are free to donate whatever you want... I'm just doing this for fun

rajula · 2014-10-15, 18:17

I left my program run while I was at work and the current best after 12h of more crunching (on one core) is

k = 9420 with

Code:

s = 115792089238294058746005917161405439247754363938954961454412921426229902682949
= (89·9868456807805249) · (4903·4909·4919·4931·4933·4937·4943·4951·4957·4967·4969·4973·4987·4993·4999·5003) - 7470

My results seem to be of the same order as those by bsquared. The simple program I wrote is the following:

Take r a bit more than half the size of the interval you are trying to find.
Define P = t#/r# with t such that the product of primes is something less than 2^256.
Sieve intervals [k*P-r,k*P+r] for increasing k (starting from the first one giving k*p>2^256). I sieve with roughly 200'000 primes.
If there are too few survivors, I discard the interval. (For example if there are 100 less survivors than the maximal number of survivors that has been observed before, or a certain top percentage based on the observed data.) Otherwise PRP-test the remaining candidates and check what is the minimal interval.

I would guess that using the form of the interval that I use does not help so much that it makes sense to consider such disjoint intervals. If someone cares, (s)he can do the math... So far I have not come up with other (possible) ways of improving the odds of finding a good interval.

I'll leave the program running for the next night also to see if it catches anything better.

Edit: as further proof that the idea I was using should not help that much is the fact that the sequence mentioned above did not really land to the middle of the interval.

MattcAnderson · 2014-10-16, 02:05

Hi Math people,

Here is a code snippet that could speed up the prime searching. It determines if the number has a factor less than 100. Since we want a long string of primes, give each a quick test and then move on.

Regards,
Matt

# produce an integer that is the product of primes less than 98.
a:=1:
for b from 1 to 25 do
a:=a*ithprime(b):
end do:
a;

composite_small:=proc(n::integer)
description “determine if n has a prime factor less than 100”
if igcd(2305567963945518424753102147331756070, n) = 1 then
return false
else return true
end if;
end proc:

composite_small(12)

composite_small(101)

# so composite_small tests if there are any factors 2 through 97
# this is faster than a full primality test.
# Matt C. Anderson 10-15-2014

bsquared · 2014-10-17, 21:50

I tweaked my program a bit: it is similar to method 2 above but does a better job identifying promising regions to test (i.e. regions relatively dense in candidate primes, after sieving). After running on one core for a little over a day, this popped out:

Code:

[1075336515063,8298]

rajula · 2014-10-18, 05:12

Quote:

Originally Posted by bsquared

I tweaked my program a bit: it is similar to method 2 above but does a better job identifying promising regions to test (i.e. regions relatively dense in candidate primes, after sieving). After running on one core for a little over a day, this popped out:

Code:

[1075336515063,8298]

That's a nice improvement. The best I could find with my program in these couple of days on one core is
k=9342 with

Code:

s = 115792092787238500461394617888090922050579425277583404792889163512259220486739

I have stopped my search and will resume only if I come up with something "clever".

mart_r · 2014-10-20, 19:33

Quote:

Originally Posted by bsquared

I tweaked my program a bit: it is similar to method 2 above but does a better job identifying promising regions to test (i.e. regions relatively dense in candidate primes, after sieving). After running on one core for a little over a day, this popped out:

Code:

[1075336515063,8298]

This is amazing - that's even a dense cluster compared to the region at 2^128 (where 101 primes are expected to span a range of 8873 ± )!
As for that k=5376-range, there is a cluster of 69 primes in there spanning a range of 5316 (and 70 primes with range 5404). It makes me doubt my assertion that a cluster of more than 73 primes is impossible to find (I mean, above 2^256)! Just a few more cores and maybe two or three weeks of calculation... (just my educated guess)

Re: my original puzzle, and just for general entertainment, here's a small list I made earlier this month of first occurences of #p primes in an interval where on one occasion before there were no primes in an interval of the same size:

Code:

#p/int:    gap @ cluster @
 2/  3:        8        11
 3/  7:       90        97
 4/ 13:      114       127
 5/ 17:      524      1087
 6/ 21:     1130      1277
 7/ 29:     1328      1423
 8/ 31:     1328      1423
 9/ 41:    15684     16057
10/ 49:    19610     21481
11/ 49:    19610     26681
12/ 51:    19610     26681
13/ 67:    31398     33563
14/ 71:    31398     33577
15/ 85:   155922    157207
16/103:   370262    414677
17/109:   370262    524921
18/105:   370262    783689
19/111:   370262    783689
20/127:  1357202   1652821
21/127:  1357202   2967317 < near miss
21/141:  2010734   2967269
22/171: 17051708  17339081
23/169: 17051708  17788709
24/175: 17051708  17788703
25/207: 20831324  21402047
26/205: 20831324  26217613
27/213: 47326694  68974307
28/233:189695660 246979981

If I triggered someone's attention he or she might try to continue here, or fill in the gaps in this more detailed table:

Code:

#p/int:   gap @ cluster @ (prime at either end)
 1/  1:       4        5
 1/  3:       8        9
 2/  3:       8       11
 2/  5:      24       27 (37)
 2/  7:      90       95 (131)
 3/  7:      90       97
 3/  9:     114      131
 4/  9:     114      191
 4/ 11:     114      189 (223)
 4/ 13:     114      127
 5/ 13:     114     1481
 5/ 15:     524     1277
 5/ 17:     524     1087
 6/ 17:     524    16057
 6/ 19:     888     1289
 6/ 21:    1130     1277
 6/ 23:    1328     1471
 7/ 21:    1130     5639
 7/ 25:    1328     1597
 7/ 27:    1328     1427
 7/ 29:    1328     1423
 8/ 27:    1328    88793
 8/ 29:    1328    88789
 8/ 31:    1328     1423
 9/ 31:    1328    88789
 9/ 33:    1328    88787 (416387)
 9/ 35:    9552    88785 (2839927)
 9/ 37:   15684    26681
 9/ 39:   15684    26679 (26693)
 9/ 41:   15684    16057
10/ 33:    1328 9853497737
10/ 35:    9552   113143
10/ 37:   15684   113141 (6937933)
10/ 39:   15684   113139 (25658429)
10/ 41:   15684   113137 (16698883)
10/ 43:   15684    26681
10/ 45:   19610    26679 (26687)
10/ 47:   19610    23017
10/ 49:   19610    21481
11/ 37:   15684 1418575498573
11/ 41:   15684        ? (>6e10)
11/ 43:   15684 51448351
11/ 45:   19610 25658429
11/ 47:   19610   113131
11/ 49:   19610    26681
12/ 43:   15684 1418575498567
12/ 45:   19610        ? (>5e10)
12/ 47:   19610 21669255187
12/ 49:   19610 5102510423
12/ 51:   19610    26681
13/ 49:   19610 10527733922579
13/ 51:   19610 179590045469 *
13/ 53:   31398 179590045467 ((>2e11))
13/ 55:   31398 9307812037
13/ 57:   31398 925594457
13/ 59:   31398 925594455 (244445394199)
13/ 61:   31398   113117
13/ 63:   31398   113111
13/ 65:   31398    33577
13/ 67:   31398    33563
14/ 51:   19610 21817283854511261
14/ 55:   31398        ?
14/ 57:   31398        ?
14/ 59:   31398        ?
14/ 61:   31398 1039086074069
14/ 63:   31398 1095672161
14/ 65:   31398 1095672159 ((>13e11))
14/ 67:   31398   113111
14/ 69:   31398   113109 (1225061)
14/ 71:   31398    33577
15/ 57:   31398 1158722981124148367
15/ 59:   31398        ?
15/ 61:   31398        ?
15/ 63:   31398        ?
15/ 65:   31398        ?
15/ 67:   31398        ?
15/ 69:   31398 4649574971
15/ 71:   31398 4649574969 ((>2e10))
15/ 73:  155922 925594441
15/ 75:  155922 925594439 (13072401689)
15/ 77:  155922  1749211
15/ 79:  155922  1749209 (7587731)
15/ 81:  155922   585839
15/ 83:  155922   585837 (113896777)
15/ 85:  155922   157207
* almost-14-tuplet, p+14 mod 19 = 0

(Note that there is no indefinitely admissible interval of 23 integers with 7 primes where the first and the last integers are primes, as is the case with 11/39 and 14/53. (The next one would be 31/143.))

rajula · 2014-10-20, 20:22

Quote:

Originally Posted by rajula

I have stopped my search and will resume only if I come up with something "clever".

I did not come up with anything "clever", but still I decided to give a new trivial idea some computing time. Taking m a number between 0 and p# < 2^256 such that sieving an interval starting from m (for example [m,m+10000]) with primes from 1 to p leaves quite many candidates, I left the computer to test intervals [k*p#+m, k*p#+m+10000] (with p=157) first by sieving a bit further with about 100000 primes and then PRP-testing the remaining candidates. So far, with 4 hours of testing on one core, I got k =8512 with

Code:

s = 115792089237316854386787690214179534766191307809502298805659818938105138402859

Now, from quick (heuristic) estimates it should not improve the probability that much to use the numbers of the form I use this time, so I think I just got lucky. I will leave the program run for at least the next night, but I doubt it will find a better interval than the current best.

rajula · 2014-10-21, 04:07

Quote:

Originally Posted by rajula

I will leave the program run for at least the next night, but I doubt it will find a better interval than the current best.

After 8 more hours the current best (for this program, still not better than bsquared's find) is k=8328 with

Code:

s = 115792089460431930243510317899738362111758665717981586635535255309225006362841

I feel optimistic enough to let the program run for another day or so. Let's see if anything better is found..

bsquared · 2014-10-21, 14:08

Quote:

Originally Posted by rajula

After 8 more hours the current best (for this program, still not better than bsquared's find) is k=8328 with

Code:

s = 115792089460431930243510317899738362111758665717981586635535255309225006362841

I feel optimistic enough to let the program run for another day or so. Let's see if anything better is found..

Two nice 8k finds in one day is definitely grounds to let it run for a while longer. With all of these 8k's popping up it seems they are not as rare as we thought; or maybe your method *does* produce better chances.

rajula · 2014-10-21, 19:56

No new results yet.

Quote:

Originally Posted by bsquared

Two nice 8k finds in one day is definitely grounds to let it run for a while longer. With all of these 8k's popping up it seems they are not as rare as we thought; or maybe your method *does* produce better chances.

You are probably right. I put a second core to run with different parameters a few hours ago. It found a k=8566 quite fast, so these 8k's are indeed not that rare. I don't have time at the moment to improve my code (too busy with my research-level math). It would be of some interest to at least record the number of disjoint intervals of length less than 9000 with 101 primes. Currently I just print out the k and s if a new record k (for that run) has been found. 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.

mart_r · 2014-10-22, 20:20

Before I go to bed, I'd like to announce a new record for my original problem:

There are 00 primes in 1539 consecutive integers starting from 18361375334787046698 (Nyman, 2014).
There are 74 primes in 1539 consecutive integers starting from 18361377388643564603 (mart_r, 2014).

2014-10-15, 18:17	#57
rajula "Tapio Rajala" Feb 2010 Finland 3²×5×7 Posts	I left my program run while I was at work and the current best after 12h of more crunching (on one core) is k = 9420 with Code: s = 115792089238294058746005917161405439247754363938954961454412921426229902682949 = (89·9868456807805249) · (4903·4909·4919·4931·4933·4937·4943·4951·4957·4967·4969·4973·4987·4993·4999·5003) - 7470 My results seem to be of the same order as those by bsquared. The simple program I wrote is the following: Take r a bit more than half the size of the interval you are trying to find. Define P = t#/r# with t such that the product of primes is something less than 2^256. Sieve intervals [kP-r,kP+r] for increasing k (starting from the first one giving kp>2^256). I sieve with roughly 200'000 primes. If there are too few survivors, I discard the interval. (For example if there are 100 less survivors than the maximal number of survivors that has been observed before, or a certain top percentage based on the observed data.) Otherwise PRP-test the remaining candidates and check what is the minimal interval. I would guess that using the form of the interval that I use does not help so much that it makes sense to consider such disjoint intervals. If someone cares, (s)he can do the math... So far I have not come up with other (possible) ways of improving the odds of finding a good interval. I'll leave the program running for the next night also to see if it catches anything better. Edit: as further proof that the idea I was using should not help that much is the fact that the sequence mentioned above did not really land to the middle of the interval. Last fiddled with by rajula on 2014-10-15 at 18:49*

2014-10-17, 21:50	#59
bsquared "Ben" Feb 2007 DB9₁₆ Posts	I tweaked my program a bit: it is similar to method 2 above but does a better job identifying promising regions to test (i.e. regions relatively dense in candidate primes, after sieving). After running on one core for a little over a day, this popped out: Code: [1075336515063,8298]

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-15, 16:39	#56
bsquared "Ben" Feb 2007 3×1,171 Posts	Some notes: First attempt pre-sieved each range of 1e9 to get ~30e6 candidate primes. Followed by a multi-threaded PRP check of candidates using mpz_probab_prime_p with 1 MR witness to get ~5e6 PRPs. Finally, crawl through and find small k's. Rinse, repeat. Second attempt tries to be smarter. It also does the pre-sieve on 1e9 ranges to get a candidate pool 'P'. Then for each of N subintervals of P, each with M candidates, record the length L. Find 'dense' subintervals: in the set of N subintervals, do (single-threaded) PRP checks on those where L is more than 3 standard deviations below the average length. Then the usual crawl for small k's. I used N = 200000, M = 500, which gives an average L of ~16000, with std of ~600. Approx 0.1% of subintervals are dense by the above metric (i.e., have 500 candidate primes in a k of <14k-ish). The second method is a thousand times faster than the first, but of course is not as thorough. For example it has missed both sub-10k intervals that the first method found. The best it found was [791883651805, 9972] through w=1e12 (which took 43 minutes). I might try playing with N or M. Or not. Any other thoughts? What cool tricks are others trying? p.s. Fivemack you are free to donate whatever you want... I'm just doing this for fun

2014-10-16, 02:05	#58
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 2⁵·5² Posts	Hi Math people, Here is a code snippet that could speed up the prime searching. It determines if the number has a factor less than 100. Since we want a long string of primes, give each a quick test and then move on. Regards, Matt # produce an integer that is the product of primes less than 98. a:=1: for b from 1 to 25 do a:=a*ithprime(b): end do: a; composite_small:=proc(n::integer) description “determine if n has a prime factor less than 100” if igcd(2305567963945518424753102147331756070, n) = 1 then return false else return true end if; end proc: composite_small(12) composite_small(101) # so composite_small tests if there are any factors 2 through 97 # this is faster than a full primality test. # Matt C. Anderson 10-15-2014

2014-10-22, 20:20	#66
mart_r Dec 2008 you know...around... 663₁₀ Posts	Before I go to bed, I'd like to announce a new record for my original problem: There are 00 primes in 1539 consecutive integers starting from 18361375334787046698 (Nyman, 2014). There are 74 primes in 1539 consecutive integers starting from 18361377388643564603 (mart_r, 2014).