I've made a program in C# that generates Mersenne numbers starting from the current largest known Mersenne prime. It then calculates the modulo between those numbers and smaller ones starting from 3 in order to figure out if it is divisible.
I've used some math tricks to make the process pretty fast, and so I can check the divisibility of what is basically a multi-million digit number against small numbers several times per second. However, I'd like to see if I can make it faster.
Also, if my program does work, it would suggest that the current largest known Mersenne prime (\$2^{74207281} - 1\$) is actually divisible by 7. Therefore I'm hesitant to say that my program actually does work, so if anyone can confirm this for me, I'd also greatly appreciate that!
using System;
using System.IO;
using System.Numerics;
namespace Prime
{
public class Prime
{
const double C = 10601040; //this is a constant that I divide the exponent by to split it into the easiest possible chunks to work with
static int exp = 74207281;
static BigInteger big = BigInteger.Pow(2, exp) - 1;
static TextWriter tw = new StreamWriter(@"prime.txt"); //writes confirmed primes to a text file
public static void Main()
{
for (int i = exp; true; i++) //this loop infinitely runs the prime checker, incrementing the exponent as it goes
{
exp++;
primes(i);
}
}
private static void primes(int exp)
{
double div = Math.Floor(exp/C),
exp1 = div,
exp2 = exp - (exp1*C), //this is where the exponent is divided into chunks
result = 0; //anywhere this appears is just to make extra sure that the result stays zero outside the following loop, where the result really matters
for (long i = 3; i <= (big/i); i+=2)
{
double result1 = (Math.Pow(2, exp1) % i)*C;
double result2 = (Math.Pow(2, exp2) % i);
result = (((result1 * result2) - 1) % i);
if (result == 0)
{
Console.WriteLine(exp + ", not prime.");
return;
}
Console.WriteLine(i);
result = 0;
}
Console.WriteLine(exp);
tw.WriteLine(exp);
}
}
}
I modulo the chunks of the tested number against odd numbers because a Mersenne number will never be even, therefore it's a waste to check for that. Also, I made the stopping point for the loop dynamic so that any extra numbers can be cut out. It's like this: 377 isn't divisible by 12, so we know that if it is divisible by something, it will be less than \$\frac{377}{12}\$, which is about 31.4. 377's actual factors are 13 and 29 (aside from itself and 1), which are both less than 37.7.
The technique used to modulo these massive numbers is known as modular exponentiation. It works for all numbers. Here's an example.
$2^7, C = 3, I = 5$
$2^7 = 128$
$Mersenne number being tested: 2^7 – 1 = 127 (this is prime)$
$Exp1 = 2$
$Exp2 = 1$
$Result1 = (2^2 % 5) * 3 = (2^2 % 5) * (2^2 % 5) * (2^2 % 5) = 4 * 4 * 4 = 64$
$Result2 = (2^1 % 5) = 2$
$Result = ( ( (64 * 2) – 1) % 5) = ( ( 128 – 1) % 5) = (127 % 5) = 2$