Are any Mersenne factors 1 mod p^2?

[alpertron]

The probability of a prime factor to be congruent to 1 (mod q²) 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.

[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*93077² + 1

I put a little work into searching for more factors 2*k*p² + 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.

[Batalov]

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*93077² + 1

I put a little work into searching for more factors 2*k*p² + 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!

[alpertron]

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*93077² + 1

I put a little work into searching for more factors 2*k*p² + 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.

[Andrew Usher]

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?

[alpertron]

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.

[Andrew Usher]

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.

[alpertron]

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:

#!/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:

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.

[kruoli]

You may take advantage of the precompiled factor lists at www.mersenne.ca/export.

[Andrew Usher]

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.

[alpertron]

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.