Small but nontrivial prime puzzle - Page 4

fivemack · 2014-10-13, 14:49

w=19397335 k=12312

fivemack · 2014-10-13, 14:58

[22619263, 12132]

fivemack · 2014-10-13, 15:21

[50128873, 11436]

axn · 2014-10-13, 15:43

Are you doing some kind of sieving?

fivemack · 2014-10-13, 15:56

Can someone give me a hand with the stats here? These numbers aren't remotely consistent with being a sample from the sum of 100 Poisson variables with lambda=log(2^256) - that would have mu=17500 sigma=130, and so 11436 would be a thirty-SD event. Obviously sum(x1..x100) is not uncorrelated with sum(x2..x101) but I don't know how you'd model the partial sums. If you want some successive minima, I'll offer

Code:

[15751, 15454]
[70221, 15444]
[70465, 15330]
[70477, 15226]
[73797, 15050]
[74683, 15012]
[108285, 14898]
[108291, 14874]
[108447, 14762]
[108745, 14560]
[109381, 14550]
[111915, 14250]
[112045, 14172]
[112177, 13980]
[112303, 13890]
[180585, 13664]
[461083, 13660]
[859837, 13600]
[862003, 13558]
[862045, 13554]
[863853, 13550]
[863967, 13404]
[864153, 13212]
[864667, 12960]
[3231663, 12738]
[6266061, 12660]
[6266701, 12580]
[6423013, 12522]
[19397335, 12312]
[22618995, 12212]
[22619263, 12132]
[50128303, 11986]
[50128327, 11670]
[50128383, 11588]
[50128603, 11508]
[50128623, 11498]
[50128873, 11436]
[114298947, 11394]
[114299053, 11346]
[114299865, 11334]
[304607541, 11274]
[319831065, 11124]
[319831071, 11108]
[319831123, 11088]
[319831143, 11000]
[319831585, 10902]
[319831597, 10822]
[319831975, 10470]
[11006283127, 10402]
[11006283133, 10390]
[11006283163, 10350]

fivemack · 2014-10-13, 15:58

Quote:

Originally Posted by axn

Are you doing some kind of sieving?

I can't figure out how you'd sieve cleverly, so these results are just from calling pari nextprime() and maintaining a circular buffer. We need actual-primes (well, OK, we're far enough along Z that base-3 Fermat pseudoprimes would be pretty much as good), and at 2^256 I'm finding that less than 15% of numbers coprime to 10^6 are prime, so I don't think the sieving can save much.

axn · 2014-10-13, 16:05

Quote:

Originally Posted by fivemack

I can't figure out how you'd sieve cleverly, so these results are just from calling pari nextprime() and maintaining a circular buffer.

Probably not feasible in PARI, but a simple C program implementing segmented SoE with the first (say) 100K primes, followed by GMP/MPIR prp check might be 2-3x faster.

EDIT:- Actually, you might even avoid PRP checking all numbers, and only check sieve survivors occurring in a "tight" cluster.

fivemack · 2014-10-13, 16:10

Go for it; you've more experience with sieve implementation than I have

Should we have a http://procrasti-nation.eu/wp-conten...e-my-money.jpg smiley?

LaurV · 2014-10-13, 16:15

I just did a list of 101 primes starting from 2^256. To this list, in an infinite loop, I add the next 2-PRP, and I eliminate the first in the list (with listput, listpop, my own 2-prp function which is about 5 times faster than pari's nextprime(), not compiled (i mean, in /gp). No presieving. The size is always a[#a]-a[1], and list operations are fast in pari. I keep the minimum size, and print it in case it appears.

This is the result of ~3 minutes of run, i will let it for few hours to see what it gets. I print all the results, in case the best interval contains a 2-pseudoprime, which is the worst thing which can happen... (well, the worst is that all intervals contains 2-PSP, which is highly improbable).

The second parameter is an offset, in case I want to restart, and the last is the string used for nice printing

Code:

gp > findmininterval(1<<256,0,101,"2^256")
Found 101 primes in a 15444-long interval, starting from 2^256+[54777..70221] - still searching ...
Found 101 primes in a 15330-long interval, starting from 2^256+[55135..70465] - still searching ...
Found 101 primes in a 15226-long interval, starting from 2^256+[55251..70477] - still searching ...
Found 101 primes in a 15050-long interval, starting from 2^256+[58747..73797] - still searching ...
Found 101 primes in a 15012-long interval, starting from 2^256+[59671..74683] - still searching ...
Found 101 primes in a 14898-long interval, starting from 2^256+[93387..108285] - still searching ...
Found 101 primes in a 14874-long interval, starting from 2^256+[93417..108291] - still searching ...
Found 101 primes in a 14762-long interval, starting from 2^256+[93685..108447] - still searching ...
Found 101 primes in a 14560-long interval, starting from 2^256+[94185..108745] - still searching ...
Found 101 primes in a 14550-long interval, starting from 2^256+[94831..109381] - still searching ...
Found 101 primes in a 14250-long interval, starting from 2^256+[97665..111915] - still searching ...
Found 101 primes in a 14172-long interval, starting from 2^256+[97873..112045] - still searching ...
Found 101 primes in a 13980-long interval, starting from 2^256+[98197..112177] - still searching ...
Found 101 primes in a 13890-long interval, starting from 2^256+[98413..112303] - still searching ...
Found 101 primes in a 13664-long interval, starting from 2^256+[166921..180585] - still searching ...
Found 101 primes in a 13660-long interval, starting from 2^256+[447423..461083] - still searching ...
Found 101 primes in a 13600-long interval, starting from 2^256+[846237..859837] - still searching ...
Found 101 primes in a 13558-long interval, starting from 2^256+[848445..862003] - still searching ...
Found 101 primes in a 13554-long interval, starting from 2^256+[848491..862045] - still searching ...
Found 101 primes in a 13554-long interval, starting from 2^256+[848541..862095] - still searching ...
Found 101 primes in a 13550-long interval, starting from 2^256+[850303..863853] - still searching ...
Found 101 primes in a 13404-long interval, starting from 2^256+[850563..863967] - still searching ...
Found 101 primes in a 13212-long interval, starting from 2^256+[850941..864153] - still searching ...
Found 101 primes in a 12960-long interval, starting from 2^256+[851707..864667] - still searching ...
Found 101 primes in a 12738-long interval, starting from 2^256+[3218925..3231663] - still searching ...
Found 101 primes in a 12660-long interval, starting from 2^256+[6253401..6266061] - still searching ...
Found 101 primes in a 12580-long interval, starting from 2^256+[6254121..6266701] - still searching ...
Found 101 primes in a 12522-long interval, starting from 2^256+[6410491..6423013] - still searching ...
... [ 18258865, 18276187 ] size 12522...

fivemack · 2014-10-13, 16:27

Quote:

Originally Posted by axn

Probably not feasible in PARI, but a simple C program implementing segmented SoE with the first (say) 100K primes, followed by GMP/MPIR prp check might be 2-3x faster.

EDIT:- Actually, you might even avoid PRP checking all numbers, and only check sieve survivors occurring in a "tight" cluster.

I don't think that helps, because survivors outnumber real primes by about a factor six, so a tight cluster is overwhelmingly likely to be mostly survivors

mart_r · 2014-10-13, 19:11

Quote:

Originally Posted by fivemack

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

Code:

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 just had my own Pari program running (speed ~ 3.44*10^6 w's per minute per core) when I saw that you already searched up to > 10^9. The last k-value is quite amazing!
Maybe I do an overnight calculation to see if I can find some k<10^4.

Looking at the prime gap listings, the gap at 5378 is currently the best one below 2^256, so the next milestone would be a cluster with k=5376...

2014-10-13, 14:49	#34
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	Donation of at least $24.60 w=19397335 k=12312

2014-10-13, 14:58	#35
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	Donation of at least $45.60 [22619263, 12132]

2014-10-13, 15:21	#36
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	Donation of at least $112.20 [50128873, 11436]

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-13, 15:43	#37
axn Jun 2003 13BC₁₆ Posts	Are you doing some kind of sieving?

2014-10-13, 16:10	#41
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	Go for it; you've more experience with sieve implementation than I have Should we have a http://procrasti-nation.eu/wp-conten...e-my-money.jpg smiley?