View Single Post
Old 2019-04-06, 21:08   #5
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×5×659 Posts
Default Why don't we use the information in the series of p values for the known Mp to predict the next?

Well, some of us do, or pretend to, but it is not productive. Put simply it does not work. It has not ever worked, despite hundreds of documented tries (with a few tries yet to be resolved). Even the best number theorists are not sure how many there are in the interval up to p~109, and are unsure where or when or whether any future such discoveries will appear. See for example https://primes.utm.edu/mersenne/index.html

See also the attachments here, the predict M45, predict M50, predict M51 or predict M52 threads, or the one based on curve fitting.
https://www.mersenneforum.org/showthread.php?t=6334 predict M45
https://www.mersenneforum.org/showth...137#post422137 predict M50
https://www.mersenneforum.org/showthread.php?t=22879 predict M51
https://www.mersenneforum.org/showthread.php?t=23892 predict M52

https://www.mersenneforum.org/showthread.php?t=24256 "Hidden number" malarky thread, based on curve fitting numerous unspecified curves

https://www.mersenneforum.org/showpo...4&postcount=69 also demonstrates the reliable failure of fits to predict even the highest known Mp on which a fit is based.

There are numerous other threads about various dubious claims to be able to make Mersenne prime predictions.
There's also a thread or two about digit sums of exponents, for which there's no known justification to believe it aids in finding Mersenne primes. Also occasional vague references to using AI or machine learning specifically, to detect patterns we don't see. To my knowledge no one has actually both attempted it and posted any results, useful or not, re AI or machine learning application to predicting Mersenne number primality or factors.

The accumulated experience of predicting or guessing Mersenne primes, in the various Predict Mxx threads, and various other threads concerning predictions, over a combined total of hundreds of distinct guesses and predictions, is: hundreds proven composite, 9 yet to be settled, and zero proven successful guesses or predictions. Another way to look at it is of over 300 guesses or predictions I've found in the forum, about 97.2% have been proven composite, about 2.8% are yet to be determined, and 0.00% (NONE) have been proven prime. And of the as-yet-unresolved, 6 are for exponents so large that they are not amenable to any P-1 factoring (or P+1 or ECM or NFS) or to primality testing by PRP or LL, either within the limits of existing software capabilities or of probable hardware lifetime, or likely GIMPS participant lifetime, so can only be attacked with trial factoring currently. Some exponents (above about 67 bits) would even have save file sizes that would exceed the capacity of nearly all currently available file systems!
For comparison: mfakto supports up to 32 bit exponents and 92-bit factor candidates; mfaktc up to 32bit exponents and 95-bit factor candidates; lifetime of a computing system ~10 years; human ~80 years; a civilization ~1000 - 5000 years depending on definition; end of multicellular life on earth due to solar aging ~109 years; Sol and perhaps its currently habitable planet ~1010 years.

Six very large unresolved exponents, in exponent size order:
  • https://mersenneforum.org/showpost.p...&postcount=213 p=252097800623 (the ten-billionth prime number as Mersenne exponent) is a ~37.88 bit exponent, of order 200 times larger than is practical to primality test on a Radeon VII GPU currently with Gpuowl in a year, and about 250 times larger than is practical currently to P-1 factor to both stages there. Some TF could be attempted with Ernst's Mfactor or Luigi's Factor5; no factor found by kriesel in Mfactor to 89 bits; kriesel continuing to 90 bits intermittently with 4 processes on a 4-core / 8-HT i5-1035G1; I estimate that the TF-optimal bit level would be 107 bits; that it would be necessary to switch from 1-word mfactor to 2word to go above 96 bits, and to modify mfactor to support >64-bit k values to go above 103 bits; that on the i5-1035G1 completing through 107 bits would take ~105,000 years; to reach the software's current limit 96 bits would take ~52. years on the i5-1035G1;
  • https://www.mersenneforum.org/showpo...33&postcount=4 p= 71324207525210468041 which is a 65.95 bit exponent, billions of times larger than what is practical to primality test or P-1 factor now; no factor in TF to 105 bits by ET_, and from 105 bits to 118 bits by kriesel using Ernst's Mfactor program; factoring from 116 bits to 117 required 27 days 13 hours with 16 processes on a dual Xeon e5-2697v2; I estimate that the TF-optimal bit level would be 188 bits; that it would be necessary to switch from 1-word mfactor to 2word to go above 96 bits, and to 3word to go above 128 bits, and to modify mfactor to support >64-bit k values to go above 131 bits; that on the dual-Xeon e5-2670 completing through 188 bits would take ~4E20 years; to reach the current software's limit would take ~2776. years on the dual-Xeon e5-2670;
  • https://www.mersenneforum.org/showthread.php?t=17050, p=97600541752017987211, a 66.4 bit exponent, no factor in TF to 107.4 bits by Ernst Mayer, and from 107 bits to 119 bits by kriesel using Ernst's Mfactor program https://www.mersenneforum.org/showpo...9&postcount=18; to 120 bits is running intermittently with 8 Mfactor processes on a dual-xeon-e5-2697v2; it's estimated through 188 bit TF depth would take 1E20 years;
  • https://mersenneforum.org/showpost.p...6&postcount=10 A 75.89 bit exponent; 270237298350549551468899-1.Trial factoring completed to 126 bits by kriesel using Ernst's Mfactor program; to 127 bits is intermittently running; I estimate that the TF-optimal bit level would be 218 bits; that it would be necessary to switch from 1-word mfactor to 2word to go above 96 bits, and to 3word to go above 128 bits, and to modify mfactor to support >64-bit k values to go above 141 bits to 192 bits, to use a modified 4word to finish; that on the Xeon Phi 7250 completing through 218 bits would take ~7E26 years; to reach the limit of the current software on the Xeon Phi 7250 ~4632. years;
  • https://www.mersenneforum.org/showthread.php?t=20238 MM127, a 127 bit exponent, p=170141183460469231731687303715884105727, no factor in TF to 185 bits by various contributors. See http://www.doublemersennes.org/mm127.php and https://mersenneforum.org/forumdisplay.php?f=99 It takes just over a month for a 5P block (5x1015) in k on a GTX1650, so going from 185 bits to 186 bits would take about 2.4 years as a continuous run in mmff, or about 8 months on an RTX2080 Super. The estimated chance of finding a factor by doing so is 0.54%. An order of magnitude faster GPU is worth about 3 bits more TF depth. MM127 is also MMM7, MMMM3, and MMMMM2. MMFF is the fastest known available software for GPU TF on modest exponent double mersenne numbers, supporting up to MM127 (or Fermat numbers to F223); newer builds at https://mersenneforum.org./showthread.php?t=17162&page=23 I estimate the TF optimal bit level is ~373 bits for CPU, 377 for GPU. Maximum bit size supported in kernels present in mmff v0.28 is 188 for MM127, so writing and proving out higher bit-level kernels would be required. Reaching 188 bits completed would take about 5 RTX2080-Super-years; reaching TF optimal bit level would require an estimated 3E56 RTX2080-years (assuming bigger kernels are no slower, which is unjustifiably optimistic).
  • A real giant of an integer is MM82589933, with 282589933 bits. A single TF trial is about the same amount of work as primality testing M82589933, which takes most of a day on a fast GPU. TF attempts on this giant may be theoretically possible with existing software but impractically slow for mortal humans. https://www.mersenneforum.org/showpo...8&postcount=55 This is the largest, of the double Mersennes based on currently known Mersenne primes, with no known factors. As far as I could tell from the doublemersennes site, MM61 through MM82589933 (43 candidates) have no known factors yet. It is believed but not proven that none of these are prime. https://en.wikipedia.org/wiki/Double_Mersenne_number Mmff double-mersenne support is currently limited to mm127, 188 bits. To go above mm127, such as for mm521, or to higher bit levels for mm31 - mm127, requires writing more kernels. George Woltman has remarked that mm521 would be better implemented using karatsuba, than grammar school style multiplication as is used in the existing kernels. Presumably for much higher double mersennes a transition to IBDWT fft would be advisable. TF optimal bit level run times on existing or foreseeable hardware would be impossibly absurdly long.
Note these examples are well beyond the capabilities of prime95 and other primality testing or P-1 factoring software and mfaktx TF software, as well as beyond feasible primality test or P-1 run times of currently available hardware, and will remain so for a long period of time. Some will remain so forever, since their sizes dwarf the number of subatomic particles in the known universe (~1080 ~2266). That makes constructing a memory of adequate size and speed for primality testing or P-1 factoring them, or sufficiently trial factoring them impossible, regardless of technical advances.

They would have extraordinarily large memory requirements. A huge extrapolation from recent gpuowl test results for stage 2 P-1 memory per buffer indicates 8.6E13 to 8.9E32 MB for 66 to 127 bit exponents. Compare to 1.6E4 MB for ram on a Radeon VII or Tesla P100 GPU.

Similarly CUDALucas file sizes are extrapolated at 8.7E12 to 2.1E31 MB for 66 to 127 bit exponents. https://www.mersenneforum.org/showpo...1&postcount=10
Gpuowl file sizes were estimated at 8.7E12 to 2.1E31 MB for 66 to 127 bit exponents. https://www.mersenneforum.org/showpo...7&postcount=22

Other software such as Ernst Mayer's Mfactor or Luigi Morelli's Factor5 can be used to continue TF, and in the case of MM127, George Woltman's mmff on CUDA GPUs. Even MMFF and Mfactor have limits.
There are also sometimes guesses or predictions in the 300M to 1G range, that take weeks to months each to primality test on fast hardware.

The absence of correct predictions or guesses is consistent with the probability of an equal number of randomly selected prime exponents, <1ppm per guess at nontrivial exponent. Probability of primality of a number n is ~1/ln(n). Where n=2p - 1, primality probability is x~1 / ( ln(2) * p). So, for example, for p~108, x~14ppb; p~852M, x ~ 0.000,000,001,7 (1.7 chances in a billion); for MM127, p=2127-1, x~8.5E-39.

In the attachments, I count guessed or claimed exponents only once, not each duplicate time a guessed or claimed exponent occurs per person doing the re-guessing.
There have been some very poor quality claims and guesses made, including MM31 more than once, even 39 years after its first known factor was found. MM127 has also been claimed more than once. Many guesses or claims have been for exponents for which LL, LL & DC, PRP, PRP & DC, or PRP & Cert have already proven them composite, or for Mersenne numbers with known factors available on mersenne.org or mersenne.ca, and even including Mersenne numbers with composite exponents which guarantee a composite Mersene with multiple factors that are easily found. (One had at least 14 factors!)


Not really a set of predictions or claims, but more of a playful computation, is George Woltman's computation of exponents from the Wagstaff expected mean incidence of Mersenne primes, in the second attachment. It does well at small values but quickly falls apart by p>127. Above 100M, it is reliable at listing only exponents with known factors:
107448193, 3 known factors
154772603, 1 known factor
223029773, 2 known factors
321520513, 1 known factor
463692847, 1 known factor
669004691, 1 known factor
965590643, 2 known factors


Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1
Attached Files
File Type: pdf pix etc and limits of curve fits.pdf (30.7 KB, 250 views)
File Type: pdf predicting Mxx wagstaff expected.pdf (10.7 KB, 266 views)
File Type: pdf predicting Mxx.pdf (66.7 KB, 18 views)

Last fiddled with by kriesel on 2022-06-22 at 15:48 Reason: minor edit re P+1, ECM
kriesel is offline