mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2023-01-06, 00:15   #23
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

5F216 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2023-01-06, 17:04   #24
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

345010 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2023-01-06, 19:52   #25
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

27D416 Posts
Lightbulb

Quote:
Originally Posted by ATH View Post
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!
Batalov is offline   Reply With Quote
Old 2023-01-07, 00:11   #26
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

27628 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
alpertron is offline   Reply With Quote
Old 2023-01-07, 15:03   #27
Andrew Usher
 
Dec 2022

26×7 Posts
Default

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
Andrew Usher is offline   Reply With Quote
Old 2023-01-07, 15:53   #28
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×761 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2023-01-07, 18:57   #29
Andrew Usher
 
Dec 2022

26×7 Posts
Default

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.
Andrew Usher is offline   Reply With Quote
Old 2023-01-11, 00:03   #30
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

5F216 Posts
Default

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 = $_[0];
  my @factors = @{$_[1]};
  my $fh = $_[2];
  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.
alpertron is offline   Reply With Quote
Old 2023-01-11, 13:00   #31
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

1,559 Posts
Default

You may take advantage of the precompiled factor lists at www.mersenne.ca/export.
kruoli is offline   Reply With Quote
Old 2023-01-11, 13:52   #32
Andrew Usher
 
Dec 2022

26·7 Posts
Default

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.
Andrew Usher is offline   Reply With Quote
Old 2023-01-11, 23:44   #33
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101111100102 Posts
Default

Quote:
Originally Posted by kruoli View Post
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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factors of Mersenne numbers bhelmes Number Theory Discussion Group 21 2021-09-15 02:07
Mersenne factors 2*k*p+1 ATH Miscellaneous Math 7 2020-10-09 11:09
factors of Mersenne numbers bhelmes Miscellaneous Math 8 2020-09-14 17:36
Distribution of Mersenne Factors tapion64 Miscellaneous Math 21 2014-04-18 21:02
Known Mersenne factors 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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