Are any Mersenne factors 1 mod p^2?

[alpertron]

I have not seen the links to the files sorted by exponent because it is linked at the bottom of the exports page. I only saw the links to the files ordered by date, which are not useful for us.

Maybe in the future I will perform a double check.

[alpertron]

I changed the program to use the data from https://www.mersenne.ca/export/

#!/usr/bin/perl
use Math::BigInt lib => 'GMP';

$solutionsFound = 0;
$candidates = 0;
$sumInverses = 0;
$fh = 0;
# Use Gray codes to generate all composite factors.
sub generateFactors
{
  my $expon = $_[0];
  my @factors = @{$_[1]};
  my $factorLen = @factors;
  my $square = $expon * $expon;
  my $currReducedFactor = 0;
  my $currFactor;
  my $factorNbr = 0;
  my $grayCode = 0;
  my $factor;
  my @reducedFactors = ();
  for (my $index = 0; $index < $factorLen; $index++)
  {
    @reducedFactors[$index] = @factors[$index] -> copy() -> bmod($expon) -> numify();
    if ($index < $factorLen - 1)
    {
      @reducedFactors[$index] *= 2;
    }
  }
  $sumInverses += (2 ** $factorLen - 1)/ $expon;
  do
  {
    $factorNbr++;
    #Get lowest non-zero bit number.
    my $currBit = 1;
    my $bitNbr = 0;
    my $temp = $factorNbr;
    my $output;
    while ($temp % 2 == 0)
    {
      $temp = $temp / 2;
      $bitNbr++;
      $currBit *= 2;
    }
    return if ($bitNbr == $factorLen);
    $candidates++;
    $grayCode = $grayCode ^ $currBit;
    if ($grayCode & $currBit)
    {
      $currReducedFactor += @reducedFactors[$bitNbr];
    }
    else
    {
      $currReducedFactor -= @reducedFactors[$bitNbr];
    }
    if (($currReducedFactor % $expon) == 0)
    {   # Solution found. Find factor for solution.
      $currFactor = Math::BigInt->bone();   ## One.
      $currBit = 1;
      if ($grayCode & (2 ** ($factorLen-1)))
      {         ## Using cofactor.
        for ($bitNbr = 0; $bitNbr < $factorLen - 1; $bitNbr++)
        {
          if (($grayCode & $currBit) == 0)
          {
            $factor = @factors[$bitNbr] -> copy() -> bmul(2*$expon) -> binc();
            $currFactor -> bmul($factor);
          }
          $currBit *= 2;
        }
        if ($expon > 2000)
        {
          if ($currFactor == 1)
          {
            print "$expon, 2^$expon-1\n";
            print $fh "$expon, 2^$expon-1\n";
          }
          else
          {
            $output = $currFactor -> bstr();
            print "$expon, (2^$expon-1)/$output\n";
            print $fh "$expon, (2^$expon-1)/$output\n";
          }
        }
        else
        {
          # Compute $currFactor = (2**$expon - 1)/$currFactor.
          my $temp = Math::BigInt->new(2);
          $temp -> bpow($expon) -> bdec() -> bdiv($currFactor);
          $currFactor = $temp;
          $output = $currFactor -> bstr();
          print "$expon, $output\n";
          print $fh "$expon, $output\n";
        }          
      }
      else
      {
        for ($bitNbr = 0; $bitNbr < $factorLen; $bitNbr++)
        {
          if ($grayCode & $currBit)
          {
            $factor = @factors[$bitNbr] -> copy() -> bmul(2*$expon) -> binc();
            $currFactor -> bmul($factor);
          }
          $currBit *= 2;
        }
        print "$expon, $currFactor\n";
        print $fh "$expon, $currFactor\n";
      }
      $solutionsFound++;
      select()->flush();
    }
  } while (1);
}

open($fh, '>', "factors.txt") or die $!;
my $currExp = -1;
my @factors = ();
my $nbrElems = 0;
for ($fileNbr = 0; $fileNbr <= 9; $fileNbr++)
{
  open(my $inputFile, '<', "mersenneca_known_factors_${fileNbr}G.txt") or die $!;
  while (my $line = <$inputFile>)
  {
    if ($line =~ /^(\d+),(\d+)$/gm)
    {    ## $1 = Exponent, $2 = k.
      if ($1 != $currExp)
      {
        if (int($1/1000000) != int($currExp/1000000))
        {
          print "Exponent = $currExp, found: $solutionsFound, candidates: $candidates, sum inverses: $sumInverses\n";
          select()->flush();
        }
        if ($currExp > 1)
        {
          ## add (cofactor mod currExp^2) / currExp to array.
          my $bigExp = Math::BigInt->new($currExp);
          my $bigSquare = $bigExp -> copy() -> bmul($bigExp);
          my $base = Math::BigInt->new(2);
          my $cofactor = $base -> copy() -> bmodpow($currExp, $bigSquare);
            # cofactor = ((2^currExp - 1) mod currExp^2) / currExp
          $cofactor->bdec() -> bdiv($currExp) -> bmod($currExp);
          for (my $index = 0; $index < $nbrElems; $index++)
          {
            my $reducedFactor = @factors[$index] -> copy() -> bmod($currExp) -> bmul(2);
            $cofactor = $cofactor -> bsub($reducedFactor);
          }
          $factors[$nbrElems] = $cofactor -> copy();  ## Add cofactor to array.
          generateFactors($currExp, \@factors);
        }
        $currExp = $1;
        @factors = ();
        $nbrElems = 0;
      }
      $factors[$nbrElems] = Math::BigInt->new($2);    ## Save value of k = (factor-1)/2/exponent.
      $nbrElems++;
    }
  }
  close($inputFile);
}
close($fh);
print "Exponent = $currExp, found: $solutionsFound, candidates: $candidates, sum inverses: $sumInverses\n";
select()->flush();

After almost 20 hours I found the same 22 solutions in the range 0G - 1G and no solutions in the range 1G - 10G using the data updated on 5 Feb.

In the range 1G - 10G there were 873352250 candidates and the sum of inverses was 0.257388, so the probability of finding a solution with 10-digit exponent was a little higher than 25%.

[alpertron]

I'm running PRP for M281903623/known factors. It just passed the iteration #100 million.