2015-02-08, 03:53 | #45 |
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,787 Posts |
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). |
2015-02-08, 06:54 | #46 |
Jun 2003
3·17·101 Posts |
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 |
2015-02-08, 07:12 | #47 |
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·4,787 Posts |
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. |
2015-02-08, 14:34 | #48 |
Jun 2003
3×17×101 Posts |
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. |
2015-02-08, 18:31 | #49 |
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·4,787 Posts |
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) |
2015-03-08, 01:54 | #50 |
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2566_{16} Posts |
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 Phi_{5}(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, Phi_{10}(x)-1 has factors x and x-1 and one can be fully factored and the other >33.3% factored. Similar numbers have form Phi_{5}(x) or Phi_{10}(x), where x = { pq | pq-1 | pq+1 } (one form for each Phi_{5} and Phi_{10} 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 < p^{2} to achieve the >33.3% proof.) P.S. Another one is Phi_{7}(p) (i.e. p^{6}+p^{5}+p^{4}+p^{3}+p^{2}+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 |
2015-05-06, 21:00 | #51 |
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22546_{8} Posts |
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. |
2015-05-08, 16:04 | #52 |
Jun 2003
3·17·101 Posts |
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 |
2015-05-08, 17:07 | #53 |
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,787 Posts |
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. |
2015-05-09, 09:38 | #54 |
Jun 2003
3·17·101 Posts |
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? |
2015-05-09, 15:40 | #55 |
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,787 Posts |
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. |
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 |