Mersenne primes

Mersenne primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Mersenne primes:

Challenge:

Create code that will list all of the Mersenne primes until some limitation is reached. For information on what a Mersenne prime is, go to this link: [[1]]

AppleScript

<lang> on isPrime(integ) set isComposite to "" if (integ / 2) = (integ / 2 div 1) then log integ & " is composite because 2 is a factor" as string --buttons {"OK", "Cancel"} default button 1 cancel button 2

else set x to 2 set sqrtOfInteg to integ ^ 0.5 repeat until x = integ ^ 0.5 + 1 as integer if (integ / x) = integ / x div 1 then log integ & " is composite because " & x & " & " & (integ / x div 1) & " are factors" as string --buttons {"OK", "Cancel"} default button 1 cancel button 2 set isComposite to 1 set x to x + 1 else

set x to x + 1 end if

end repeat log integ & " is prime" as string --buttons {"OK", "Cancel"} default button 1 cancel button 2 if isComposite = 1 then log integ & "is composite" else display dialog integ end if end if

end isPrime set x to 2 repeat isPrime(((2 ^ x) - 1) div 1) set x to x + 1 end repeat </lang>

Kotlin

This task is similar to the Lucas-Lehmer test task except that you can use whatever method you like to test the primality of the Mersenne numbers. Here, I've chosen to use the JDK's BigInteger.isProbablePrime(certainty) method which appears to be based on the Miller-Rabin test and (for larger numbers) the Lucas-Lehmer test as well.

A 'certainty' parameter of 10 is enough to find the first 20 Mersenne primes but as even this takes about 90 seconds on my modest machine I've not bothered going beyond that. <lang scala>// version 1.2.10

import java.math.BigInteger

const val MAX = 20

val bigOne = BigInteger.ONE val bigTwo = 2.toBigInteger()

/* for checking 'small' primes */ fun isPrime(n: Int): Boolean {

   if (n < 2) return false
   if (n % 2 == 0) return n == 2
   if (n % 3 == 0) return n == 3
   var d : Int = 5
   while (d * d <= n) {
       if (n % d == 0) return false
       d += 2
       if (n % d == 0) return false
       d += 4
   }
   return true

}

fun main(args: Array<String>) {

   var count = 0
   var p = 2
   while (true) {
       val m = bigTwo.shiftLeft(p - 1) - bigOne
       if (m.isProbablePrime(10)) {
           println("2 ^ $p - 1")
           if (++count == MAX) break
       }
       // obtain next prime, p
       while(true) {
           p = if (p > 2) p + 2 else 3
           if (isPrime(p)) break
       }
   }

}</lang>

Output:

2 ^ 2 - 1
2 ^ 3 - 1
2 ^ 5 - 1
2 ^ 7 - 1
2 ^ 13 - 1
2 ^ 17 - 1
2 ^ 19 - 1
2 ^ 31 - 1
2 ^ 61 - 1
2 ^ 89 - 1
2 ^ 107 - 1
2 ^ 127 - 1
2 ^ 521 - 1
2 ^ 607 - 1
2 ^ 1279 - 1
2 ^ 2203 - 1
2 ^ 2281 - 1
2 ^ 3217 - 1
2 ^ 4253 - 1
2 ^ 4423 - 1

zkl

Uses libGMP (GNU MP Bignum Library) and its Miller-Rabin probabilistic primality testing algorithm. <lang zkl>var [const] BN=Import("zklBigNum"); // libGMP fcn mprimes{

  n,m := BN(2),0;
  foreach e in ([2..]){
     n,m = n.shiftLeft(1), n-1;
     if(m.probablyPrime()) println("2^%d - 1".fmt(e));
  }

}() // gets rather slow after M(4423)</lang>

Output:

2^2 - 1
2^3 - 1
2^5 - 1
2^7 - 1
2^13 - 1
2^17 - 1
2^19 - 1
2^31 - 1
2^61 - 1
2^89 - 1
2^107 - 1
2^127 - 1
2^521 - 1
2^607 - 1
2^1279 - 1
2^2203 - 1
2^2281 - 1
2^3217 - 1
2^4253 - 1
2^4423 - 1
2^9689 - 1
2^9941 - 1
2^11213 - 1
...