// MersennePrimes.java
// Andrew Davison, ad@coe.psu.ac.th, April 2023

/* Calculate Mersenne primes -- a prime number of the form 2^n - 1 
   for some integer n, checking the result with Nut.isPrime(). 

   The exponents n which give Mersenne primes are 2, 3, 5, 7, 13, 17, 19, 31, ...,
   and the resulting primes are 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, ...
   The smallest composite Mersenne number with prime exponent n is 
                 2^11 - 1 = 2047 = 23 * 89. 

   There are two versions of Nut.isPrime(): one that accepts a long
   value, and the other deals with BigInteger. Internally this second
   function does not use sqrt() in order to be a little faster.

   https://en.wikipedia.org/wiki/Mersenne_prime

   Usage:
     > compile MersennePrimes.java
     > run MersennePrimes

   Outputs and typical timings:

      2: 3 : 0ms
      3: 7 : 0ms
      5: 31 : 0ms
      7: 127 : 0ms
         // Note that 11 was skipped
      13: 8191 : 0ms
      17: 131071 : 2ms   // <<== BigInteger impl ?? 
      19: 524287 : 0ms
         // 23, 29 are skipped
      31: 2147483647 : 6ms
         // 37, 41, 43, 47, 53, 59
      61: 2305843009213693951 : 28379ms
             : // a long wait for 
               // 89: 618970019642690137449562111
*/

import java.math.BigInteger;


public class MersennePrimes
{

  public static void main(String[] args)
  {
    int i = 0;
    while (true) {
      BigInteger powVal = BigInteger.valueOf(2).pow(i).
                               subtract(BigInteger.ONE);  // 2^i-1
      long startTime = System.currentTimeMillis();

      if (Nut.isPrime(powVal))   // BigInteger version
        System.out.println(i + ": " + powVal + " : " +
                (System.currentTimeMillis() - startTime) + "ms");
      i++;
    }
  } /* main */

}  // end of MersennePrimes class