mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2015-02-08, 03:53   #45
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Cool the next Cyclo prime has >1.3M digits

Approximately a thousand dollars worth of EC2 g2.2xlarge (with GRID K520s) time yielded the next term for the OEIS sequence A246119 (n=17; b somewhat higher than expected; details will follow soon, after the doublecheck/N-1 proof with PFGW). Using three idle Ivy Bridge cores, I also ran quite a bit of my k=5 Proth reservation with waterline now advanced to around n~=10,000,000...

Now, a bit of final overhead is needed for the stragglers to prove the minimality of b. Thanks to Yves and Anand for some excellent coding. Without Cyclo, at b > ~65000, cycLLR (and gwnum that is powering it) switches from special to general FFT which is many times slower; I already had some work done for both n=16 (up to b<=75000) and n=17 (up to b<=60000), but both need quite a bit of more heavy lifting and for both Cyclo was the only way to go effectively. CycloSv by axn also helped to eliminate additional work by effective sieving.

I asked and received an increase for up to 20 spot instances in two zones. EC2 folks were quite helpful (late in January, I launched five nodes without checking "spot", accidentally, and before I realized this by watching cost report I was already out of a hundred bucks instead of normal ten bucks; they generously refunded me... a minor anecdote of course, but a pleasant one, nevertheless).
Attached Thumbnails
Click image for larger version

Name:	Half_of_the_EC2_farm.png
Views:	275
Size:	166.0 KB
ID:	12274  
Batalov is offline   Reply With Quote
Old 2015-02-08, 06:54   #46
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default

Congratulations!

FYI, there has been reported cases of the sieve reporting bad factors, due to occasional composite inputs that beats the PRP test for candidate factors. As a result, you must check that all factors actually divide the number. Hopefully, you've been doing that, but if not, you'll have to check the factors for false positives
axn is offline   Reply With Quote
Old 2015-02-08, 07:12   #47
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,787 Posts
Default

Yes, I have that perl reformatter into the Mod(b,f)^n ... form, which I then pipe to gp.
I'll do the final tally when I will be done with the batch as it is.

The PFGW test will take 15 hours (3 of which have passed), even on an AVX capable comp. The Cyclo test takes 2300s on the K520, and for comparison, 1660s on my 570, so those K520 are pretty worth the 6.4 cents per hour (approximately 4c per candidate times ~25,000). I will report the prime tomorrow early afternoon. I will report the OEIS extension only later when I will run all needed tests.
Batalov is offline   Reply With Quote
Old 2015-02-08, 14:34   #48
axn
 
axn's Avatar
 
Jun 2003

3×17×101 Posts
Default

New version 0.5:

Fixed ETA calculation. Was off by a factor of 50% (if it said 1hr, it would actually take 1.5hr).
Changed ETA update frequency from once every 3 seconds to 10 seconds


Attached are the source, win32 exe (CUDA 3.2), and compile scripts for windows and linux.
Attached Files
File Type: zip cyclosv0.5.zip (80.3 KB, 229 views)
axn is offline   Reply With Quote
Old 2015-02-08, 18:31   #49
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,787 Posts
Default

192098^262144 - 192098^131072 + 1 is prime. (Cyclo on a K520 2311.0 sec., err=2.88e-02, 1385044 digits)

Code:
Double check on GTX 570 (with Cyclo 1.0.1):
192098^262144 - 192098^131072 + 1 is a probable prime. (1655.9 sec., err=2.88e-002, 1385044 digits)

N-1 proof:
Primality testing Phi(3,-192098^131072) [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 7
Generic modular reduction using generic reduction AVX FFT length 480K, Pass1=384, Pass2=1280 on A 4601016-bit number
Calling Brillhart-Lehmer-Selfridge with factored part 47.15%
Phi(3,-192098^131072) is prime! (54402.0486s+0.3578s)
Attached Thumbnails
Click image for larger version

Name:	EC2_that_lucky_node.png
Views:	259
Size:	124.8 KB
ID:	12279  
Batalov is offline   Reply With Quote
Old 2015-03-08, 01:54   #50
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

256616 Posts
Default

Here is a bit funny prime: Phi(5, pq-1), where p=187·2^110513-1, q=409·2^129185-1 are primes.

One can observe that Phi5(x)-1 has factors x and x+1, and in this case x is 46% factored, and x+1 is fully factored; so that altogether allows for the 36.5% factored N-1 proof. Similarly, Phi10(x)-1 has factors x and x-1 and one can be fully factored and the other >33.3% factored.

Similar numbers have form Phi5(x) or Phi10(x), where x = { pq | pq-1 | pq+1 } (one form for each Phi5 and Phi10 is usable every time). One can combine all known small Proth and Riesel primes such that 33% is reached (in a nutshell, one needs p <= q < p2 to achieve the >33.3% proof.)

P.S. Another one is Phi7(p) (i.e. p6+p5+p4+p3+p2+p+1), where p=5978493*2^150006-1. With 270979 decimal digits, it is a bit short of entering the UTM prime database.

Last fiddled with by Batalov on 2015-03-11 at 06:04
Batalov is offline   Reply With Quote
Old 2015-05-06, 21:00   #51
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

225468 Posts
Wink Capt. Obvious warns the non-believers:

I've systematically scanned the Phi(3,-b^2^15) P.I.E.S. series and here is the chart for the numerologists to ponder.

This is the distribution of the 30 b values for which Phi(3,-b^2^15) is prime, and it is fairly clumpy in parts: there are seven primes for b<46,000; there are none for some stretches of >130,000 in length; there are a couple very close pairs: e.g. (570986, 571472) and (589179, 589797). I know for a fact that there are people in the audience who would cancel their reservation for their chunk "next" to a recent prime (because "there can't be a prime there now; my prime was stolen, now this range is crap!"); there are some who would look only for prime b values, etc. The truth is that after the sieving is done, all the survivor candidates (in their size bins) have equal chances to be prime as a plain function of their size. It is exactly the same for any class of primes: Mersenne series, any Proth/Riesel series*, Gaussian-Mersenne, partition numbers, you name it. Marvel the Poisson process at its best:

____________
*...and with k being a Proth or a Riesel number, it is also true. That probability is simply zero and equal for all candidates; however, there will be no candidates left in the sieve after the covering set has done its job.
Attached Thumbnails
Click image for larger version

Name:	PIES_chart.png
Views:	254
Size:	15.6 KB
ID:	12584  
Batalov is offline   Reply With Quote
Old 2015-05-08, 16:04   #52
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default

Random observation: It should be relatively easy to adapt Cyclo to do a primality proof instead of PRP test in the same amount of time, by implementing Pocklington's Theorem. http://primes.utm.edu/prove/prove3_1.html

Just noting, what with all the Cyclo primes currently being found
axn is offline   Reply With Quote
Old 2015-05-08, 17:07   #53
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

Sure! So far, Yves just recently wrangled that prime-specific pattern that happens during last iterations of squaring for some odd b values. So, one wouldn't want to jump to another algorithm before debugging that; but now would be a great time. He added the 80-bit math, he wrote, and it is used in last iterations.

In fact, today I found a very peculiar rounding error reported: 9.99e-01 , so the weird rounding errors are still possible albeit very rarely, even with v.1.1.0. (All previous PRPs returned either average rounding error or the flat value of 5.00e-01 and 'composite' verdict.)

My hunch is that the rounding error of ~ 1 could happen if trunc works in the mode 'round toward zero' and the true value (with carries) happened to go into negatives. Otherwise, of course, Occam's razor would tell us that rounding error > 0.5 is not possible.
But I haven't looked in the source.
Batalov is offline   Reply With Quote
Old 2015-05-09, 09:38   #54
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default

While I was thinking about how to efficiently implement the primality test, a thought occurred to me. Currently there is no "independent" double check of Cyclo residues (for non-PRPs). Running cyclo twice on the same candidate (albeit in different h/w) is not exactly independent. And 80-bit cyclo will be too slow for practical use. But there is another way to do it. We can calculate 2^(N-1) (mod N) as (2^((N-1)/b)^b. Since this is the same computation, the final residue should be the same, but every intermediate state will be different. Hence, this computation sort of fulfills the same role as GIMPS's random rotation thing. We could do (2^((N-1)/b^r)^(b^r) for some small random r.

Clever, huh?
axn is offline   Reply With Quote
Old 2015-05-09, 15:40   #55
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

The last operation x^b may be a bit tricky; the usual exponentiation relies on x being small: lots of squarings with some mul by x.
When x is as large as the whole residue, the long mul will need to be implemented.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime 95 and internet connection issue Jwb52z Software 10 2013-01-30 01:09
Twin prime search? MooooMoo Twin Prime Search 115 2010-08-29 17:38
Prime Search at School Unregistered Information & Answers 5 2009-10-15 22:44
Prime Search on PS-3? Kosmaj Riesel Prime Search 6 2006-11-21 15:19
Running prime on PC without internet-connection Ferdy Software 3 2006-04-25 08:53

All times are UTC. The time now is 22:06.


Tue Oct 26 22:06:55 UTC 2021 up 95 days, 16:35, 1 user, load averages: 1.07, 1.11, 1.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.