 mersenneforum.org Are any Mersenne factors 1 mod p^2?
 Register FAQ Search Today's Posts Mark Forums Read  2023-01-06, 00:15 #23 alpertron   Aug 2002 Buenos Aires, Argentina 5F216 Posts The probability of a prime factor to be congruent to 1 (mod q2) is 1/q where q is the exponent. I read from PrimeNet all factors found in the last year and then I added the inverses of the exponents. The sum is 0.0116. This means that we could find one prime factor in 86 years, assuming that the rate of prime factor discovery is constant. Last fiddled with by alpertron on 2023-01-06 at 00:48   2023-01-06, 17:04 #24 ATH Einyen   Dec 2003 Denmark 345010 Posts There is a 10 year old thread about this issue starting at post #74 in this thread: https://mersenneforum.org/showthread...ighlight=93077 I found that factor back then: 2*674487*930772 + 1 I put a little work into searching for more factors 2*k*p2 + 1 of Mp, but never found any others. Not a big effort, and it was a home made program using GMP, so not very fast.   2023-01-06, 19:52   #25
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

27D416 Posts Quote:
 Originally Posted by ATH There is a 10 year old thread about this issue starting at post #74 in this thread: https://mersenneforum.org/showthread...ighlight=93077 I found that factor back then: 2*674487*930772 + 1 I put a little work into searching for more factors 2*k*p2 + 1 of Mp, but never found any others. Not a big effort, and it was a home made program using GMP, so not very fast.
Ecclesiastes 1:10 strikes out again!    2023-01-07, 00:11   #26
alpertron

Aug 2002
Buenos Aires, Argentina

27628 Posts Quote:
 Originally Posted by ATH There is a 10 year old thread about this issue starting at post #74 in this thread: https://mersenneforum.org/showthread...ighlight=93077 I found that factor back then: 2*674487*930772 + 1 I put a little work into searching for more factors 2*k*p2 + 1 of Mp, but never found any others. Not a big effort, and it was a home made program using GMP, so not very fast.
The difference between this thread and the old thread is that I found that none of the prime factors stored by PrimeNet during these 10 years generates a new example.   2023-01-07, 15:03 #27 Andrew Usher   Dec 2022 26×7 Posts Why, yes, nothing new indeed. The poster raising that issue, also thought like me, that there was a possible connection to Wieferich primes! 10 more years and no one finding another such factor is of course not surprising; there may not be another to be found in the Primenet range, as the sum of reciprocals of all primes <1G corresponding to numbers not fully factored is about 1 (log log 1G - log log 1200 < 1.1). I think the English idiom Batalov was trying for was "strikes again", not "strikes out again" which means almost the opposite to me. If it were possible I'd want to have that unique fact enshrined on the exponent page for M93077 - where else? Last fiddled with by Dr Sardonicus on 2023-01-07 at 15:37 Reason: Indicating the kind of empty egotism nobody wants to read   2023-01-07, 15:53 #28 alpertron   Aug 2002 Buenos Aires, Argentina 2×761 Posts A Mersenne number with exponent q has k*log(q) factors in average. So there are lots of examples in the Primenet range. The main problem is that we do not know how to get large prime factors (say, more than 70 digits) of Mersenne numbers, so most candidates are out of reach.   2023-01-07, 18:57 #29 Andrew Usher   Dec 2022 26×7 Posts I took that into account, yes, but it's impossible to put exact figures on. I'm not particularly interested in trying to predict when or if the next one will be found, only saying the odds aren't good. You're right that full factorisation of all the Mersenne numbers <1G would almost surely reveal more.   2023-01-11, 00:03 #30 alpertron   Aug 2002 Buenos Aires, Argentina 5F216 Posts This week I wrote a program in Perl to solve the original problem, so the factor does not need to be prime. The program is the following: Code: #!/usr/bin/perl use LWP::Simple; use LWP::Protocol::https; use bigint; use Math::BigInt; my $maxExponent = 10000000;$solutionsFound = 0; # Use Gray codes to generate all composite factors. sub generateFactors { my $expon =$_; my @factors = @{$_}; my$fh = $_; my$factorLen = @factors; my $square =$expon * $expon; my$currReducedFactor = 0; my $currFactor; my$factorNbr = 0; my $grayCode = 0; my @reducedFactors = (); for (my$index = 0; $index <$factorLen; $index++) { @reducedFactors[$index] = ((@factors[$index]-1) /$expon) % $expon; } do {$factorNbr++; #Get lowest non-zero bit number. my $currBit = 1; my$bitNbr = 0; my $temp =$factorNbr; while ($temp % 2 == 0) {$temp = $temp / 2;$bitNbr++; $currBit *= 2; } return if ($bitNbr == $factorLen);$grayCode = $grayCode ^$currBit; if ($grayCode &$currBit) { $currReducedFactor += @reducedFactors[$bitNbr]; } else { $currReducedFactor -= @reducedFactors[$bitNbr]; } if (($currReducedFactor %$expon) == 0) { # Solution found. Find factor for solution. $currFactor = 1;$currBit = 1; if ($grayCode & (2 ** ($factorLen-1))) { ## Using cofactor. for ($bitNbr = 0;$bitNbr < $factorLen - 1;$bitNbr++) { if (($grayCode &$currBit) == 0) { $currFactor *= @factors[$bitNbr]; } $currBit *= 2; } if ($expon > 2000) { if ($currFactor == 1) { print$fh "$expon, 2^$expon-1\n"; } else { print $fh "$expon, (2^$expon-1)/$currFactor\n"; } } else { $currFactor = (2**$expon - 1)/$currFactor; print$fh "$expon,$currFactor\n"; } } else { for ($bitNbr = 0;$bitNbr < $factorLen;$bitNbr++) { if ($grayCode &$currBit) { $currFactor *= @factors[$bitNbr]; } $currBit *= 2; } print$fh "$expon,$currFactor\n"; } $solutionsFound++; select()->flush(); } } while (1); } open(my$fh, '>', "factors.txt") or die $!; my$initialExp = 2; while ($initialExp <$maxExponent) { print "Current exponent = $initialExp, solutions found:$solutionsFound\r"; select()->flush(); my $factorsHTML = get("https://www.mersenne.org/report_factors/?exp_hi=999999937&exp_lo=$initialExp&txt=1"); my $currExp = -1; my @factors = (); my$nbrElems = 0; while ($factorsHTML =~ /^(\d+),(\d+)$/gm) { if ($1 !=$currExp) { if ($currExp > 1) { ## add cofactor mod currExp^2 to array. my$square = $currExp *$currExp; my $base = 2; my$cofactor = $base -> copy() -> bmodpow($currExp, $square);$cofactor--; # cofactor = (2^currExp - 1) mod currExp^2 for (my $index = 0;$index < $nbrElems;$index++) { my $reducedFactor = (@factors[$index] - 1) % $square;$cofactor = $cofactor -$reducedFactor; } $factors[$nbrElems] = $cofactor; ## Add cofactor to array. generateFactors($currExp, \@factors, $fh); }$currExp = $1; @factors = ();$nbrElems = 0; } $factors[$nbrElems] = $2;$nbrElems++; } $initialExp =$currExp; } close(\$fh); The code queries PrimeNet for the known factors of Mersenne numbers. The output of the program is a list of pairs of numbers separated by commas. First the exponent and then the factor. The 21 factors found by this program for exponents from 2 to 10 million are: Code: 191, 2350896688821832838803657 251, 31023471745943714523187601 397, 8278905362357819790631 773, 20479040582507467524577451248703690547707678649852388248171967557919731517696375740392451630382795252028981663 1093, 106117072581983269474793080340567717078397956791542542949103099197485397871425144431292125650059067127332642679326932683398740043306522890399652721428129911889732527339112424467053626126286568209115915316611118566506237779469765285573088172126586565474810622908751554571053781281789969711594905276852997331777071476162426193313791 1097, 213886786357517070010157900697588917983722563702416516853618061455249823180002350234027798857781692593958639752437864942054409912177671575082240841370204161745143984363354298735328256829750325404762295802988234794253720312024861170192676506373985143478674737024175235416458450244548225837036407 2657, 6842603331598723085139967038590349619933734338796297337 2749, 32139650481921830748201373445409812135258533056022268195856131635549963686050472814758690401236748877049534953593236129 3511, 2^3511-1 4933, 13068972589597943333501462259641440038961245223194687711701610322482701606473616195395039775478299368095009401390104062593 4933, (2^4933-1)/224511272686596258575239781670114845104761092882011698304774343242211288212183049080917537915945003999610865316669512636442509034802819183 5903, (2^5903-1)/62294387377270041301850205844448404537447 12589, 1476904537653444135567018573451506749559318506256521254370064554901903793 13679, 215987765863109582969368764285127 49043, 2793867913346006061243250557890178547455820179063693988666659546381913 52903, (2^52903-1)/6014511703679 93077, 11686604129694847 114997, (2^114997-1)/5487788058879444869875833737220515285054819569158076014108922089048502126210444928681 189547, (2^189547-1)/93678757374407097759047380767455119 329299, (2^329299-1)/1888002674835838116631 1895809, (2^1895809-1)/2259804329 Please let me know if there are errors.   2023-01-11, 13:00 #31 kruoli   "Oliver" Sep 2017 Porta Westfalica, DE 1,559 Posts You may take advantage of the precompiled factor lists at www.mersenne.ca/export.   2023-01-11, 13:52 #32 Andrew Usher   Dec 2022 26·7 Posts That list looks reasonable; of course, the exponents with the whole number 1 mod p^2 are exactly the Wieferich primes. Composite factors with the property should be O(log p) instead of O(log log p), but again that assumes full factorisation. Those factor lists just linked to by kruoli are, I assume, intended to allow expanding your searches beyond 1G if desired.   2023-01-11, 23:44   #33
alpertron

Aug 2002
Buenos Aires, Argentina

101111100102 Posts Quote:
 Originally Posted by kruoli You may take advantage of the precompiled factor lists at www.mersenne.ca/export.
To process the SQL queries embedded in the compressed files, I would need to perform several changes to the code. I need the data to be sorted by exponent, not by date. At this moment I have no time to do those changes.

In the meantime I found no more solutions for exponents below 100M.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Number Theory Discussion Group 21 2021-09-15 02:07 ATH Miscellaneous Math 7 2020-10-09 11:09 bhelmes Miscellaneous Math 8 2020-09-14 17:36 tapion64 Miscellaneous Math 21 2014-04-18 21:02 CRGreathouse Math 5 2013-06-14 11:44

All times are UTC. The time now is 00:03.

Wed Jun 7 00:03:40 UTC 2023 up 292 days, 21:32, 0 users, load averages: 0.85, 0.92, 0.86 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔