2020-12-24, 17:51 | #1 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7·983 Posts |
Exponents of particular forms
This thread is intended as a reference thread for Mersenne exponents of special forms. For discussion, please use the reference discussion thread https://www.mersenneforum.org/showthread.php?t=23383. (Discussion posts added to this thread may be moved or deleted without notice or recourse.)
The various forms or subsets are discussed here as a sort of mathematical amusement. There is no known basis for believing they have higher chance of revealing a Mersenne prime. They lie at an intersection of Mersenne primes and recreational mathematics. They might also be used as an added arbitrary selection method for sampling the natural number line segment for substantial black box QA testing of software algorithms. It's unlikely to be a good selection method compared to pseudorandom and boundary-informed selection methods. Intro and table of contents (this post) Mersenne rhymes https://www.mersenneforum.org/showpo...43&postcount=2 Straights https://www.mersenneforum.org/showpo...44&postcount=3 Repdigits and near-repdigits https://www.mersenneforum.org/showpo...45&postcount=4 Palindromic numbers as exponents https://www.mersenneforum.org/showpo...46&postcount=5 Prime approximations of round multiples of irrational or transcendental numbers https://www.mersenneforum.org/showpo...48&postcount=6 Personally significant dates encoded into exponents https://www.mersenneforum.org/showpo...61&postcount=7 Large exponents https://www.mersenneforum.org/showpo...47&postcount=8 Dual digit value palindromic exponents https://www.mersenneforum.org/showpo...18&postcount=9 Near-palindromic exponents https://www.mersenneforum.org/showpo...5&postcount=10 Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2022-08-07 at 17:50 Reason: added near palindromic exponents |
2020-12-24, 17:56 | #2 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7×983 Posts |
Mersenne rhymes
As used here, a rhyme is an exponent that has in common several rightmost digits with another, in the same order. Rhymes in one number base likely will not be rhymes in most others, or only to lesser extent. Except as indicated, base ten is used here. (If there is an established term for this, please PM me and I'll adopt it here.)
There is no reason to believe that if an exponent p corresponds to a Mersenne prime, that any rhyming prime exponent r = p + c x base^{n} would also, at above the probability for a randomly chosen exponent. Yet in the category of dubious claims (or maybe math trolling), sometimes someone claims that one or more such rhyme's corresponding Mersenne number is prime. For example, 82589933, 102589933. (C 2, base 10, n 7; 7digit decimal rhyme, 0x4ec38ed, 0x61d65ed 2digit hexadecimal rhyme) emerged in this thread. Or the nearest prime to a rhyme as in https://www.mersenneforum.org/showpo...8&postcount=13, with the derivation speculatively described in https://www.mersenneforum.org/showpo...4&postcount=24. Rhymes among exponents of known Mersenne primes Empirically, it is straightforward to show that no two of the 51 known Mersenne primes' decimal exponents rhyme deeper than 3 decimal digits. A simple spreadsheet with exponents p, and cells p mod 10^n for n=1...4 and sorting by column for differing n is enough. Single digit rhymes are unavoidable in base 10 given the number of known Mersenne primes. The n+1-digit rhymes are a subset of the n-digit rhymes. The expected number of n+1-digit rhymes is ~1/10 the number of n-digit rhymes for n>1. The number of prime exponent rhymes for right digit 2 or 5 are necessarily zero, as for 4, 6, 8, or 0. Rhyming decimal exponents among the known Mersenne primes, versus number of digits: 1 digit: 4 cases possible, all of which are found, 49 members of rhyme sets There are unavoidably many matches, since, after 2 and 5, there are only 4 choices for final digit, 1, 3, 7, 9. 1 13 cases (31, 61, 521, 2281, 9941, 21701, 216091, 2976221, 20996011, 25964951, 42643801, 57885161, 74207281) 2 (2) 3 12 cases (3, 13, 2203, 4253, 4423, 11213, 86243, 110503, 859433, 6972593, 24036583, 82589933) 5 (5) 7 15 cases (7, 17, 107, 127, 607, 3217, 19937, 44497, 1257787, 3021377, 13466917, 30402457, 32582657, 37156667, 77232917) 9 9 cases (19, 89, 1279, 9689, 23209, 132049, 756839, 1398269, 43112609) total 51 check 2 digit: 12 cases (of 50 odd 2 digit numbers, minus 10 odd multiples of 5 = 40 possible), 28 members 01 (21701, 42643801) 03 (3, 2203, 110503) 07 (7, 107, 607) 09 (23209, 43112609) 13 (13, 11213) 17 (17, 3217, 13466917, 77232917) 21 (521, 2976221) 33 (859433, 82589933) 57 (30402457, 32582657) 61 (61, 57885161) 81 (2281, 74207281) 89 (89, 9689) 3 digit: 2 cases, 4 members 281 (2281, 74207281) 917 (13466917, 77232917) 4 digit: 0 cases, 0 members; null set 2-digit rhymes are a subset of 1-digit rhymes. 3-digit are a subset of 2-digit. 4-digit would be a subset of 3-digit. Etc. Subset of a null set is null. 5-digit and higher rhyme length are necessarily null sets. Presumably, if the conjecture of existence of an infinite number of Mersenne primes is correct, there are exponent rhymes of any arbitrarily large length. Testing for rhyme exponents As a proactive measure against such guesses/trolls, I've tabulated the candidate base ten prime 7-digit rhyme length or longer rhymes in the mersenne.org exponent range 2 < r <10^{9}, and begun taking the factoring and testing of them further. Running such widely scattered exponents tests many different fft lengths in the software used, and may reveal bugs or unreliable hardware. It has already identified the PrimeNet server's PRP proof handling exponent limitation to ~596M. There was also found and fixed an issue in prime95 where the AVX512 ffts were limited to AVX2 maximum exponent. As of 2020-12-24: Many known Mersenne primes' 7-digit decimal exponent prime rhymes for r<10^{9} have been shown composite for all up to 100MDigit or higher: Mp51*, Mp48*, Mp46, Mp44, Mp42, Mp41, Mp39, Mp37, Mp34, Mp31, Mp30, Mp28, Mp27, Mp26, Mp23, Mp22, Mp20, Mp19, Mp18, Mp17, Mp14, Mp13, Mp12, Mp9, Mp8, Mp7, Mp6, Mp5, Mp4, Mp3, Mp2, Mp1 (32 of the 51 known) Of those, some are completed through 200Mdigits: Mp5, Mp23, Mp44 Some are only one PRP test away from complete to r<10^{9}: Mp44, Mp42, Mp39, Mp36 One is completed through r<10^{9} (slightly higher than 300Mdigit): Mp5 (M13) Mp3 and Mp1 can have no prime exponents that are decimal rhymes (with 2 or 5 as right digit of the exponent) All known Mersenne primes' 7-digit decimal exponent prime rhymes for r<10^{9} have been P-1 factored to recommended bounds up to 100Mdigit level except: Mp24 (260019937 is the remaining rhyme exponent, P-1 in progress) All known Mersenne primes' 7-digit decimal exponent prime rhymes for r<10^{9} have been trial factored to recommended bounds up to 100Mdigit exponent level. For Mp47-Mp51* the rhyming exponents have been completed in TF and P-1 up to recommended bounds up to 200Mdigit level. Others with incomplete factoring below the 200Mdigit level: Mp46 has a P-1 pending on one rhyme exponent to that level, as do Mp43, Mp30, Mp25 and Mp24. Mp34 and Mp27 each have a rhyme exponent on which TF is pending and P-1 is unstarted. Mp26 has a rhyme exponent on which P-1 is unstarted. Mp22 and below mostly have multiple rhymes with factoring incomplete. TF remains to complete on >5% of identified rhymes; P-1 on >17%; PRP on >29%, of the 601 identified rhyming prime exponents < 10^{9}. As of 2021-02-09: Many known Mersenne primes' 7-digit decimal exponent prime rhymes for r<10 9 have been shown composite for all up to 100MDigit or higher: Mp51*, Mp49*, Mp48*, Mp46, Mp44, Mp42, Mp41, Mp39, Mp38, Mp37, Mp34, Mp31, Mp30, Mp28, Mp27, Mp26, Mp23, Mp22, Mp21, Mp20, Mp19, Mp18, Mp17, Mp14, Mp13, Mp12, Mp9, Mp8, Mp7, Mp6, Mp5, Mp4, Mp3, Mp2, Mp1 (35 of the 51 known) Of those, some are completed through 200Mdigits: Mp5, Mp23, Mp44 Some are only one PRP test away from complete to r<10^{9}: Mp44, Mp42, Mp39, Mp36, Mp18 One is completed through r<10^{9} (slightly higher than 300Mdigit): Mp5 (M13) Mp3 and Mp1 can have no prime exponents that are decimal rhymes (with 2 or 5 as right digit of the exponent) All known Mersenne primes' 7-digit decimal exponent prime rhymes for r<10^{9} have been P-1 factored to recommended bounds up to 100Mdigit level All known Mersenne primes' 7-digit decimal exponent prime rhymes for r<10^{9 }have been trial factored to recommended bounds up to 100Mdigit exponent level. For Mp47-Mp51* the rhyming exponents have been completed in TF and P-1 up to recommended bounds up to 200Mdigit level. Others with incomplete factoring below the 200Mdigit level: Mp46 has a P-1 pending on one rhyme exponent to that level, as do Mp25, Mp24, Mp21, Mp20, Mp16, Mp12, Mp11, Mp8, Mp7, and Mp2. Mp34 and Mp27 each have a rhyme exponent on which TF is pending and P-1 is unstarted below 200Mdigit. TF remains to complete on <1.5% of identified rhymes; P-1 on <13%; PRP on <29%, of the 601 identified rhyming prime exponents < 10^{9}. Estimated effort to complete remaining primality testing is about 3,900,000 GhzDays. Update as of 2021-04-24: Done through 100Mdigits, also Mp47, Mp45, Mp43, Mp40, Mp29, Mp25, Mp24, Mp16 (so in total, 43 of the 51 known) Done through 200Mdigits: Mp44, Mp38, Mp23, Mp14, Mp5 Ten are only one PRP test away from complete to r<10^{9}: Mp44, Mp42, Mp39, Mp38, Mp36, Mp29, Mp24, Mp23, Mp18, Mp14 All TF has been completed for exponents below 200Mdigits. TF on one exponent remains to be completed out of 601 (0.17%); all TF completed 2021-04-29; P-1 <10% remain; PRP <27%. Estimated effort to complete remaining primality testing is about 3,864,000 GhzDays. Update as of 2021-05-07: M480003217 is composite, completing the testing of 7-decimal-digit rhymes r<10^{9} for M3217. Update as of 2021-05-23: M660000031 P-1 factoring completed, completing 7-digit mersenne rhyme P-1 factoring below 200Mdigit. Update as of 2021-06-23: Of the 601 identified 7-digit-rhyme prime rhyme exponents <1G, 54 of them are 8-digit rhyme exponents; of these 28 have factors found, and 6 have primality tests completed indicating composite; all are TF completed; 4 need P-1 factoring completed; 20 remain to be primality tested if needed. The 54 is 9%, exactly what we'd expect; to be an 8-digit rhyme, the 9th digit must differ, so values 1-9 for the known 8-digit or smaller exponents of known Mersenne primes; the 8th digit must match; 9/10*1/10=9% x 601=54.09. Of the 601, TF is complete, P-1 <9% remain; PRP <26% remain. If/when we find Mp#52* (likely >104M exponent), all the above completion figures will change. Estimated effort to complete remaining primality testing is about 3,821,000 GhzDays. At the rate of progress of primality testing averaged over the past two months, it will take about 15 years to complete the search, without new Mersenne prime discoveries adding workload or new hardware speeding progress or existing hardware failing faster than it's replaced. Update as of 2021-07-14: Of the 601 identified 7-digit-rhyme prime rhyme exponents <1G, TF is complete, P-1 <6% remain; PRP <25% remain. Update as of 2021-08-24: Of the 601 identified 7-digit-rhyme prime rhyme exponents <1G, TF is complete, P-1 <2% remain; PRP <25% remain. Testing completed on 7-decimal-digit exponent rhymes of 2976221. Update as of 2021-09-11: Of the 601 identified 7-digit-rhyme prime rhyme exponents <1G, TF is complete, P-1 <1% remain; PRP <25% remain. All PRP below 321398269 have been completed. Update as of 2021-10-05: Of the 601 identified 7-digit-rhyme prime rhyme exponents <1G, P-1 is complete; PRP <24% remain. M321398269 is the only remaining uncompleted PRP in the set below 100Mdigit. Update as of 2021-11-09: Of the 601 identified 7-digit-rhyme prime rhyme exponents <1G, PRP <23% remain. All under 100Mdigit are complete. Lowest remaining is M357885161. The mersenne number corresponding to the last remaining 7-digit decimal rhyme exponent of the exponent of M11213 < 10^{9} M800011213 which is also an 8-digit decimal rhyme, has been found composite by PRP/GEC with proof generation power 9 (~31. THzD). The list of Mersenne primes whose exponents have been shown to have all 7-digit decimal rhymes exponents <10^{9} produce composite Mersenne numbers is now: 13466917 (Mp#39) 2976221 (Mp#36) 11213 (Mp#23) 3217 (Mp#18) 13 (Mp#5) 5 (Mp#3) 2 (Mp#1) Seven down, 44 to go, for now. There remain 137 primality tests in p <10^{9} 7-decimal-digit exponent rhymes; ~3549. THzD. Ten of the 44 are one PRP test away each from completion. Update as of 2022-01-19: Of the 601 identified 7-digit-rhyme prime rhyme exponents <1G, 132, <22% remain to be PRP tested and certified, ~3490. THzD of PRP effort. The list of Mersenne primes whose exponents have been shown to have all 7-digit decimal rhymes exponents <10^{9} produce composite Mersenne numbers now also includes 25964951 (Mp#42) Update as of 2022-07-22: Of the 601 identified 7-digit-rhyme prime rhyme exponents <1G, 126, <21% remain to be PRP tested and certified, ~3383. THzD of PRP effort (~20. RadeonVII-years). The list of Mersenne primes whose exponents have been shown to have all 7-digit decimal rhymes exponents <10^{9} produce composite Mersenne numbers now also includes 6972593 (Mp#38) This state of progress is the result of many people's efforts in TF, P-1, PRP or LL as part of the overall GIMPS project. Please help. Anyone willing to help complete this subproject, please contact Kriesel by PM for work coordination. There are no longer any TF or P-1 tasks available, but there are available tasks for primality testing via PRP/GEC/proof generation from ~450M up to ~991M. There will probably also be some sizable Cert tasks available eventually, as a result of large-exponent PRP/GEC/proof runs completing. M843112609 is a recent example. These land in the PRP triple-check thread. While the PrimeNet server is unable to automatically process proof files for exponents over ~595.7M, future effort will prioritize completing PRP testing within the server's capability. These assignments also require great patience and very reliable hardware. ECC system ram is recommended. In mprime / prime95, v30.3 or higher would be needed for PRP proof generation or running certs. In mprime / prime95, above ~595.7M would require AVX2 or AVX512 capable hardware; above ~920.8M would require AVX512 capable hardware. (I think Mlucas would offer more flexibility on exponent versus hardware. Total run time is a concern. And IIRC the current Mlucas release does not yet support PRP proof generation, so for now its use on first tests is discouraged.) PRP/GEC/proof for ~1G on a Xeon Phi 7250 running prime95 on Windows as a single worker would take a little over a year. At ~500M, run times would be slightly less than 1/4. PRP run time scaling or benchmarks for prime95 on various hardware is available in attachments at the "Effect of number of workers" posts in https://www.mersenneforum.org/showthread.php?t=23900 Gpuowl (at least v6.11-318 for proof generation) on a Radeon VII or fast NVIDIA Tesla GPU would also work well. (CUDALucas being LL without even Jacobi check would be too unreliable, and is also considerably slower on the same gpuowl-capable hardware and task.) At the upper bound: ~1G on a Radeon VII PRP/GEC/proof time would be ~5-6 months each. At ~500M, run times would be slightly less than 1/4. See also Gpuowl PRP run time versus exponent or fft length https://www.mersenneforum.org/showpo...35&postcount=2 Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2022-07-22 at 16:16 Reason: minor edits |
2020-12-24, 18:00 | #3 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
15341_{8} Posts |
Straights
These are exponents such as 160456789 which also sometimes come up in dubious claims or guesses as exponents of Mersenne primes. In the mersenne.org search space 2<p<999999999, the run of ascending digits is limited to 8 or less and not a multiple of 3. A 3-digit run segment is divisible by 3 always: c c+1 c+2 is c*100 + c*10 + c + 10 + 2 = 111c +12 which will be divisible by 3, since 111=37*3 and 12=4*3.
Both ascending straights and descending straights occur, as well as shuffled straights. Shuffled straights would be more probable so more common than sorted straights. Ascending straights seem to me the most interesting of the 3. I am unaware of any effort to search for or tabulate straights that are prime exponents or the factoring or primality status of the corresponding Mersenne numbers. There's a thread about straights as exponents. One could generalize from straights to additional valued poker hands. Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2021-01-08 at 16:48 |
2020-12-24, 18:07 | #4 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7·983 Posts |
Repdigits and near-repdigits
Repdigits are numbers consisting only of repetition of the same digit value. (Single-digit numbers are excluded by definition.)
For Mersennes' exponents, repdigit digit values larger than one lead to composite exponents, and thereby to composite Mersenne numbers. Composite digit counts also lead to composite exponents and composite Mersenne numbers. This leaves exponents consisting of a prime number of ones, which lead to mostly composite exponents. It also leads to a very small set of candidates, since for p<10^{9}, number of digits no greater than 9, only 2, 3, 5, or 7 digits are prime length for exponent expressed in base ten. In 1<p<999999999 Mersenne.org range: 11; prime exponent but 2^{11}-1 is divisible by 23. 111 = 3 x 37; could have ruled this out by noting sum of digits is 3 11111 = 41 x 271 1111111= 239 × 4649 So there are no Mersenne primes with base-10 repdigit exponents in 1<p<999999999 mersenne.org range. Trying hexadecimal, 11h = 17 decimal prime exponent; 2^{11h}-1 =131071 base 10 which is a known small Mersenne prime; 111h = 273 = 3 x 7 x 13 11111h = 69905 = 5 × 11 × 31 × 41 1111111h = 17895697 = 29 × 43 × 113 × 127 Use of smaller number bases bring more small prime exponent lengths into range. Near the limit, base 3 11(3) = 4 = 2^{2} 111(3) = 13 (prime) M(13) is Mp5 11111(3)= 121= 11^{2} 1111111(3) = 1093 (prime); M(1093) has 5 factors 11111111111(3) = 88573 = 23 × 3851 ...7 174453 = 11^{2} × 13 × 4561 64 570081 = 1871 × 34511 Base 2: bits p Mp status 2 3 prime 3 7 prime 5 31 prime 7 127 prime 11 2047 = 23 × 89 so Mp is composite 13 8191 prime 17 131071 prime 19 524287 prime 23 8388607 = 47 × 178481 29 536870911 = 233 × 1103 × 2089 Near-repdigits Exponents with the rightmost digit differing from the rest may be prime for digit values other than one repeating also. A small perl program to find 9-digit base 10 prime exponents that are near-repdigits yields the following 7 exponents, with current status as shown: 111111113 Factored 222222227 LL; LL DC matched 444444443 Factored 666666667 Tested LL & DC by LaurV 777777773 Factored 888888883 Factored 888888887 No factor to 85 bits TF completed; P-1 done; LL!! assigned JamesShao 2020-1-22, no progress indicated yet Six composite, one remaining to be determined in the short list above. Code:
# nearrep.pl # perl script to find near repdigit prime exponents iiiiiiiij, j != i, i>0, base 10 use ntheory; $count=0; for ( $i=1; $i<10; $i++ ) { #repfield is $i as digits x 8 places foreach $j ( 1, 3, 7, 9 ) { #rightmost if ($i != $j ) { $k=$i*11111111*10+$j; if ( Math::Prime::Util::GMP::is_prime($k) == 0 ) { # print "$k is composite\n"; } else { print "$k\n"; $count++; } } } } print "Counted $count\n(end)\n"; Checking for other positions of the differing digit, and annotating the resulting output with current status: Code:
# nearrep2.pl # perl script to find near repdigit prime exponents i..iji..i, j != i, i>0, base 10 # where leftmost digit may be j but rightmost is not use ntheory; $count=0; for ( $l=1; $l<9; $l++ ) { #power of ten at which digit differs for ( $j=0; $j<10; $j++ ) { #differing digit foreach $i ( 1, 3, 7, 9 ) { #repfield is $i as digits x 8 places if ( $i != $j ) { $k= $i*111111111 +($j- $i) *10**$l; if ( Math::Prime::Util::GMP::is_prime($k) == 0 ) { # print "$k is composite\n"; } else { print "$k\n"; $count++; } } } } } print "Counted $count\n(end)\n"; Code:
333333313 factored 999999929 NF 86; P-1 NF; LL! assigned JamesShao 2020-01-22 but no progress indicated yet; PRP C; proof file generation in progress 111111131 factored 111111181 LL C; LLDC matched 777777577 factored 999999599 factored 777777677 factored 333331333 factored 999992999 NF 86, P-1 NF; PRP assigned Etinn 2021-05-15 shows no progress yet; PRP & proof in progress 111113111 factored 333334333 factored 777776777 NF 85, P-1 NF, PRP C, CERT 777767777 factored 111181111 factored 111191111 factored 333233333 factored 999299999 NF 86, P-1 NF, PRP C, CERT 999499999 factored 999599999 NF 86, P-1 NF, PRP C, CERT 333733333 factored 333833333 factored 115111111 factored 776777777 factored 337333333 NF 81; P-1 NF, PRP C, CERT 118111111 LL C; LLDC matched 778777777 factored 998999999 NF 86; P-1 NF, PRP C, CERT 101111111 factored 131111111 factored 373333333 factored 787777777 factored 577777777 factored 799999999 NF 85; P-1 NF; PRP assigned Yuki Ito prematurely 2020-12-16, but no progress indicated yet; PRP & proof in progress Counted 33 (end) There's also a very short very old forum thread about such numbers. Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2022-09-19 at 21:02 Reason: status update |
2020-12-24, 18:10 | #5 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7·983 Posts |
Palindromic numbers as exponents
Palindromic numbers are numbers that are reversible digit by digit without changing value. 110505011 is an example, which as a Mersenne exponent, leads to a P-1 factor.
Palindromic numbers in base ten are quite common. The subset that are primes are also common. There are 5172 in 10^{8}<p<10^{9}. As of 2021 Jan 19, over 3100 of those have been factored, and more than 200 others have PRP or LL composite primality test results. Even-digit-count palindromic primes are rare: 11; see https://mersenneforum.org/showpost.p...4&postcount=19. Palindromic number exponents 10 < p < 10^{8} have already been tested at least once by GIMPS and indicated composite. None of the currently known Mersenne primes have an exponent that is a palindromic number of 2 or more digits in base ten. By definition, single digit numbers are palindromic, so the 4 known Mersenne primes that have palindromic numbers as exponents in base ten are M(2), M(3), M(5), M(7). Consider 171575171 which is a prime exponent and the corresponding Mersenne number has a minimal factor. f=2kp+1 = 343150343, k=1 https://www.mersenne.ca/exponent/171575171. That factor is nearly palindromic, off by one in a single digit. A subset of palindromic numbers contain shorter palindromic prime numbers in their decimal representation. For example, 110757011 contains 11 and 757. Or consider those of form p*10^{6}+(2p+1)*10^{3}+p, such as 171343171, which also is a prime exponent, and the corresponding Mersenne number has a known factor. There are also some palindromic exponents with embedded palindromic prime numbers. An example of base ten 9-digit palindromic prime numbers of form a (10^{6}+1)+b 10^{3} containing only 3-digit palindromic prime numbers a and b, of form c (10^{2}+1) + 10 d containing only 1-digit primes, is 373 353 373. 373353373 It's both palindromic and prime, at 9 digits, the three 3-digit segments considered individually, and as individual digits. (2-digit scan fails prime at 33 and 35) Please PM Kriesel with what those special cases are called. Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2022-02-11 at 03:03 Reason: add link to dr sardonicus post on even length palindromes |
2020-12-24, 18:18 | #6 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7·983 Posts |
Prime approximations of round multiples of irrational or transcendental numbers
Consider [ceiling|floor] r = c x 10^{n} x b, where b is an irrational or transcendental number such as pi, e, sqrt(2), sqrt(3), sqrt(5), sqrt(10), etc and where c, n are are small positive integers chosen such that 10^{8}< r < 10^{9}. And find the nearest prime exponent to r. Or [ceiling|floor] r = c x 10^{n} x b^{m} where b is a transcendental number and m is also a small positive integer.
Factoring or primality testing on such exponents may be useful by falling in regions of the number line that would not be selected otherwise in a simple QA selection method. Some early examples of such runs revealed limitations on CUDAPm1 exponent that were later found to be partly GPU-model dependent. 130637753 (factored) < 10^{8} Mills' constant ~ 130637788 < 130637791 (PRP C & cert) 141421333 (PRP C & cert) < 10^{8} sqrt (2) ~ 141421356 < 141421387 (factored) 144818161 (PRP C & cert) < 10^{8} sum of reciprocals of known Mersenne primes' exponents ~ 144818186 < 144818221 (PRP C & cert; this line added 2021-08-18) 147576139 (factored) < 10^{8} 2^(1/e^{gamma}) ~ 147576140 < 147576181 (factored) 157079621 (PRP C & cert) < 10^{8} pi/2 ~ 157079632.7 < 157079633 (factored) 161803393 (factored) < 10^{8} golden ratio ~ 161803399 < 161803403 (PRP C & cert) 173205079 (PRP C & cert) < 10^{8} sqrt (3) ~ 173205081 < 173205089 (factored) 192878201 (factored) < 10^{8} Wright's constant (= 1.928782187...) ~ 192878219 < 192878237 (factored) 223606793 (PRP C & cert) < 10^{8} sqrt (5) ~ 223606798 < 223606807 (PRP C & Cert) 261497207 (factored) < 10^{9} Mertens constant ~ 261497213 < 261497239 (PRP C & Cert) 271828171 (PRP C & cert) < 10^{8} e ~ 271828183 < 271828199 (PRP C & cert) 292005097 (factored) < 10^{8} "Buenos Aires constant" ~ 292005098 < 292005113 (PRP C & cert) 314159257 (PRP C & cert) < 10^{8} pi ~ 314159265 < 314159311 (factored) 316227731 (factored) < 10^{8} sqrt(10) ~ 316227766 < 316227767 (factored) 543656363 (factored) < 2 x 10^{8} e ~ 543656366 < 543656371 (TF, P-1 done, PRP in progress) 577215631 (TF & P-1 done, PRP in progress) < 10^{9} Euler-Mascheroni constant ~ 577215665 < 577215677 (factored) (PrimeNet server limit for automatic processing of proof files is up to ~596M) 624329977 (factored) < 10^{9} Golomb-Dickman constant ~ 624329989 < 624330017 (factored) 628318517 (TF & P-1 done, PRP needed) < 2 x 10^{8} pi ~ 628318531 < 628318583 (TF & P-1 done, PRP needed) 785398129 (factored) < 10^{9} pi/4 ~ 785398163 < 785398169 (factored) 853973387 (factored) < 10^{8} e pi ~ 853973422 < 853973437 (TF & P-1 done, PRP needed) 942477787 (factored) < 3 x 10^{8} pi ~ 942477796 < 942477799 (TF done, P-1 done, PRP needed) 986960431 (factored) < 10^{8} pi^{2} ~ 986960440 < 986960461 (TF & P-1 done, PRP needed) Suggestions for additions to the above list are welcome by PM. (purple font identifies active assignments; green font identifies assignments available) Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2022-09-12 at 16:44 Reason: added Golomb-Dickman constant |
2020-12-24, 21:23 | #7 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7·983 Posts |
Personally significant dates encoded into exponents
The idea of encoding personally significant dates into exponents came up in https://www.mersenneforum.org/showpo...04&postcount=8 and has no more mathematical merit than trying to pick a winning lottery ticket by the same method, which is no merit at all. But if it's fun, and you're not concerned about the leakage of personally identifying information, try it. Birthdates, anniversaries, etc.
Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2021-01-03 at 14:42 |
2021-01-22, 16:45 | #8 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
1101011100001_{2} Posts |
Large exponents
Here, large is defined as an exponent beyond the mersenne.org limit, currently 10^{9}, which is almost 2^{30}
Before considering larger exponents, it's useful to consider the scale of effort needed near the limit of mersenne.org. TF to recommended bit levels for near the 10^{9} limit takes days per exponent on the fastest GPUs and best software. P-1 testing to recommended bounds near the 10^{9} limit takes ~4 days per exponent in GpuOwL on fast GPUs such as Radeon VIIs. Primality testing near the 10^{9} limit takes around 6 months per exponent with GpuOwL on a Radeon VII. Prime95 benchmarks indicate about 13 months each primality test near 10^{9} on a Xeon Phi 7250 (68 cores 1 worker at ~1.4-1.5 GHz clock and 16GB 7200MHz MCDRAM in same chip package). ONLY PRP with Gerbicz error check should be considered for such long tests. (LL testing lacks the Gerbicz error check in all existing software and lacks even the weak Jacobi symbol check in some software, so is unlikely to complete correctly for very long runs.) ONLY PRP with proof generation should be considered for completing such long tests. Short starts on PRP may be performed, on software not yet supporting PRP proof generation, up to ~0.095%, 0.19%, or 0.38% of completion, to allow resumption later with proof power 10, 9, or 8, respectively, assuming the next version of the software will support both PRP proof generation at such powers, and sufficient backward version save-file compatibility. It would be prudent to err on the low side of iteration count, in case software only supports one version back and multiple versions pass before implementation; then sufficient iterations may remain to run an intermediate software version briefly for file version conversion purposes without passing a threshold where the feasible proof power drops and certification effort doubles. (In general, <100%/2^{power} - delta) Primality testing effort scales as roughly exponent^{2.1} over large ranges involving multiple fft lengths. P-1 effort and TF effort scale similarly, with a smaller proportionality constant, ~1/40 that of primality testing, each. Conversely, the probability of finding a prime diminishes per test as exponent increases. Software support for large exponents is limited, and the more so as exponent increases. There is little reason to exert effort in software development for large exponents soon, since the remaining work in mersenne.org will take more than a century at currently projected rates. https://www.mersenneforum.org/showpo...5&postcount=11 A summary of software support is available in the attachment at http://www.mersenneforum.org/showpos...91&postcount=2 Interim residues for a limited wide ranging variety of fft lengths and specified exponents are available at https://www.mersenneforum.org/showpo...4&postcount=12 https://www.mersenne.ca/ covers status for exponents up to 10^{10}, and coordinates trial factoring for exponents over 10^{9} up to 2^{32}. Gigadigit Mersennes are covered in subforum Operation Billion Digits https://mersenneforum.org/forumdisplay.php?f=50. Assignment reservation and result submission page, and display of status for trial factoring is at https://www.mersenne.ca/obd I do not know of any software currently capable of P-1 factoring such large numbers in a reasonable amount of time or with acceptable reliability, other than perhaps Mlucas V20.x on fast hardware, with 20.1.1 recently released, and with sufficient P-1 capability implemented as a byproduct of the current F33 attempt. See https://mersenneforum.org/showthread.php?t=24486 for discussion of run time scaling and requirements. Gigadigit primality tests are technically possible now in Mlucas or certain versions of Gpuowl, but the duration per test on available hardware is longer than the likely hardware lifetime. So the hardware would need to be replaced and work in progress migrated, and great care exerted with backups of work in progress and error checking along the way. There's a forum thread regarding 10-gigadigit numbers, in which even larger are also mentioned. Only trial factoring is feasible for these. There's little or no point in doing so, other than as an amusement. https://mersenneforum.org/showthread.php?t=16801 For 36bit or higher exponents, optimal TF depth takes startlingly long. See the "six very large exponents" section in https://www.mersenneforum.org/showpo...04&postcount=5 Double Mersennes: For Mersenne numbers with Mersenne numbers as exponents, see the Operazione Doppi Mersennes subforum: https://mersenneforum.org/forumdisplay.php?f=99. Also http://www.doublemersennes.org/ There's a thread discussing when it might be feasible to primality test MM61. Assuming Moore's law continues, over 100 years. But Moore's law is slowing and faces hard physics limits. https://mersenneforum.org/showthread.php?t=21522 Some of the challenges and changes required are discussed briefly in https://mersenneforum.org/showthread.php?t=17354 and https://mersenneforum.org/showpost.p...6&postcount=16 There's also a bit of discussion of the difficulty of even attempting TF on the triple Mersenne MMM127. https://mersenneforum.org/showthread.php?t=18522 Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2021-11-06 at 15:51 Reason: added PRP proof consideration, minor updates |
2022-04-21, 01:38 | #9 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7×983 Posts |
Dual digit value palindromic exponents
Consider some palindromic prime exponents with cyclic digit patterns possible with exactly two distinct digit values, a and b, both >0, for 9-digit base 10 exponents, with digit cycle periods, and excluding near-repdigits such as aaaabaaaa:
(1 N/A; repdigit, all of which are composite) 2 ababababa 3 abaabaaba (oops, that is a repdigit too, in base 1000, so composite) 4 abbbabbba 5 abbaaabba (6 aaabbbaaa is always divisible by 3; 111=3 x 37) 7 aabbbbbaa 8 abbbbbbba For the multidigit exponent to be prime in base 10, the rightmost digit a must be 1, 3, 7 or 9. (And for a palindrome, so must the leftmost digit.) Dr. Sardonicus helpfully contributed the following 6 PARI/GP code and output sections by a PM (while this post was in early draft form; edited slightly here, and posted with his permission): 2 ababababa Code:
forstep(a=1,9,[2,4,2],for(b=0,9,n=a*(10^8+10^6+10^4+10^2+1)+b*(10^7+10^5+10^3+10);if(gcd(n,3*7*11*13*17)==1&&ispseudoprime(n),print(n)))) 323232323 383838383 727272727 919191919 929292929 979797979 989898989 Code:
forstep(a=1,9,[2,4,2],for(b=0,9,n=a*(10^8+10^6+10^5+10^3+10^2+1)+b*(10^7+10^4+10);if(gcd(n,3*7*11*13*17)==1&&ispseudoprime(n),print(n)))) ? /*Note: aba*(10^6+10^3+1)*/ Code:
forstep(a=1,9,[2,4,2],for(b=0,9,n=a*(10^8+10^4+1)+b*(10^7+10^6+10^5+10^3+10^2+10);if(gcd(n,3*7*11*13*17)==1&&ispseudoprime(n),print(n)))) ? /*Note: always divisible by 3*/ Code:
forstep(a=1,9,[2,4,2],for(b=0,9,n=a*(10^8+10^5+10^4+10^3+1)+b*(10^7+10^6+10^2+10);if(gcd(n,3*7*11*13*17)==1&&ispseudoprime(n),print(n)))) 133111331 377333773 766777667 944999449 977999779 988999889 Code:
forstep(a=1,9,[2,4,2],for(b=0,9,n=a*(10^8+10^7+10+1)+b*(10^6+10^5+10^4+10^3+10^2);if(gcd(n,3*7*11*13*17)==1&&ispseudoprime(n),print(n)))) 331111133 772222277 779999977 992222299 995555599 Code:
forstep(a=1,9,[2,4,2],for(b=0,9,n=a*(10^8+1)+b*(10^7+10^6+10^5+10^4+10^3+10^2+10);if(gcd(n,3*7*11*13*17)==1&&ispseudoprime(n),print(n)))) 188888881 199999991 322222223 355555553 722222227 323232323 TF NF; P-1 NF; LL C; PRP C & Cert 383838383 TF NF; P-1 NF; LL C; LLDC C match 727272727 TF NF; P-1 NF; no primality test 919191919 3 known factors 929292929 known factor 979797979 known factor 989898989 TF NF; P-1 NF; no primality test 133111331 2 known factors 377333773 2 known factors 766777667 2 known factors 944999449 2 known factors 977999779 known factor 988999889 known factor 331111133 known factor 772222277 2 known factors 779999977 known factor 992222299 TF NF; P-1 NF; no primality test 995555599 known factor 188888881 TF NF; P-1 NF; LL C; LLDC C match 199999991 2 known factors 322222223 TF NF; P-1 NF; LL C; PRP/proof as DC& CERT 355555553 known factor 722222227 3 known factors Here black normal font means completed; black bold means current assigned to someone else; green bold indicates available; blue italic indicates being run by kriesel; underlined indicates without a reservation (probably one could not be obtained); bold purple indicates stalled old assignments Are there more? yes; 4 aabaaabaa 5 abbababba 5 aaaabaaaa 6 aaababaaa 7 aabbabbaa 8 abaaaaaba 8 ababbbaba yielding respectively, 110111011 known factor 112111211 TF NF; P-1 NF; LL C & LLDC C match 113111311 TF NF; P-1 NF; LL C, PRP C & CERT 115111511 2 known factors 331333133 known factor 335333533 known factor 338333833 TF NF; P-1 NF; PRP C & CERT 991999199 known factor 322323223 4 known factors 355353553 TF NF; P-1 NF; PRP C& CERT 722727227 TF NF; P-1 NF; no primality test 911919119 3 known factors 111181111 known factor 111191111 3 known factors 777767777 2 known factors 111010111 known factor 111515111 2 known factors 111616111 2 known factors 333434333 TF NF; P-1 NF; PRP C & CERT 333535333 known factor 112212211 known factor 118818811 2 known factors 338838833 known factor 994494499 known factor 998898899 TF NF; P-1 NF; LL assigned 2014-10-02 tclutter1 & no progress 121111121 2 known factors 131111131 TF NF; P-1 NF; PRP C & CERT 181111181 TF NF; P-1 NF; PRP C & CERT 323333323 TF NF; P-1 NF; PRP C & CERT 131333131 TF NF; P-1 NF; PRP C & CERT 181888181 known factor 313111313 known factor 323222323 known factor 383888383 TF NF; P-1 NF; PRP/proof assigned 959555959 known factor of the 35, 32 are shown composite, 3 are yet to be determined, & 0 need DC or CERT. So overall above, 58, of which 52 are shown composite, 6 are yet to be determined, and 0 need DC or CERT. Are there more? Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2022-08-30 at 21:26 Reason: exponent status update |
2022-08-07, 17:48 | #10 |
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7·983 Posts |
Near-palindromic exponents
Near palindromes differ by one character from a palindrome. These will be more numerous than palindrome exponents. All the following concerns base-ten exponent representations.
Consider an arbitrary palindromic exponent abcdeDCBA. For a palindrome a=A, b=B, c=C, d=D. Any of bcde might have value any digit 0-9. A will be only 1 3 7 or 9 or the exponent would be composite. For a near palindrome exponent, any one of bcdDCB may have any of the other 9 values than for the palindrome, while a may have any of the other 8 excluding 0, and A may have one of three other values and still possibly result in a prime exponent. So it appears 9-digit near palindrome exponents would be about 8+6*9+3 = ~65 times more numerous than palindromes. There are ~5172 nine digit prime palindrome exponents. Nine-digit prime near palindromes may number around 336,180. The above simply derived estimate produces an overcount, an upper bound. Consider these prime palindromes: 100060001 101060101 Either might produce the same near palindromes by changing a single digit in the c or C position, 100060101 or 101060001, and these each get counted twice. Also for 103060301, 106060601, and no doubt many other cases. This applies equally to the b / B or d / D positions. The a / A positions are not as symmetric so not a simple factor of two there. For palindromes: eDCBA with A constrained to 4 values (1 3 7 9) gives 4E4 possible numbers, (abcd matching ABCD respectively), of which 5172 are prime (~12.93%) For abcdeDCBA near palindromes: Consider two cases; interior single symmetric digit mismatch, and exterior (leading/trailing digit) mismatch. Interior: with A constrained to 4 values (1 3 7 9) and a=A gives 1E9 x 0.4 * 0.1 = 4E7 possible numbers. Constraining any 2 of bcd to respectively match BCD reduces the possible numbers by a factor of 3/100 to 1.2E6. And constraining the remaining one of bcd to not match its counterpart provides a further factor of 0.9, to 1.08E6. 4 values a,A x 10 values e x 1000 values bcd x 3*9 BCD single digit mismatches to bcd = 1,080,000. Check. Exterior: For a!=A, for each allowable A to possibly produce a prime there are 8 possible a values >0 & != A; and all of bcd must match their corresponding digits DCB; 1E9 * 0.8 * 0.4 * 0.001 = 320,000. 8 possible values a >0 !=A, x 4 A, x 10,000 bcde = 320,000. Check. The two cases a=A and a!=A are mutually exclusive, so the numbers can be summed. Combining cases, 1,400,000, of which likely ~0.1293 are prime; ~181020. This is ~1.0357 times higher (+6245) than 174775 that axn obtained with a Pari script counting 9-digit near palindrome primes. Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1 Last fiddled with by kriesel on 2022-08-08 at 18:55 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Prime Pages Achievable Forms? | PawnProver44 | Miscellaneous Math | 1 | 2016-04-08 11:27 |
Comprehensible book about modular forms | fivemack | Other Mathematical Topics | 1 | 2015-06-08 15:55 |
Representation by quadratic forms | Raman | Math | 0 | 2013-01-04 00:29 |
Minimum primes of various forms database? | jasong | Information & Answers | 1 | 2007-11-01 01:58 |
Unreserving exponents via manual forms or not? | Boulder | PrimeNet | 3 | 2007-05-29 10:01 |