Lucas-Lehmer test: Difference between revisions

<lang Scala>object LLT extends App {

import Stream._

def primeSieve(s: Stream[Int]): Stream[Int] = s.head #::primeSieve(s.tail filter { _ % s.head != 0 }) //primeSieve: (s: Stream[Int])Stream[Int]

def primes = primeSieve(from(2)) //primes: Stream[Int]

def mersenne(p: Int): BigInt = (BigInt(2) pow p)-1 //mersenne: (p: Int)BigInt

val s: (BigInt,Int) => BigInt = (mp,p) => if (p==1) 4 else (((s(mp,p-1) pow 2)-2)%mp) //s: (BigInt, Int) => BigInt = <function2>

(primes takeWhile (_<2300) map {p=>(p,mersenne(p))} map {p=>if (p._1==2) (p,0) else (p,s(p._2,p._1-1))} filter {_._2==0})

.foreach {p=>println("prime M"+(p._1)._1+{if ((p._1)._1<200) ": "+(p._1)._2 else ": ("+(p._1)._2.toString.size+" digits)"})}

}</lang>

Output:

<pre style="height: 40ex; overflow: scroll">prime M2: 3

prime M3: 7

prime M5: 31

prime M7: 127

prime M13: 8191

prime M17: 131071

prime M19: 524287

prime M31: 2147483647

prime M61: 2305843009213693951

prime M89: 618970019642690137449562111

prime M107: 162259276829213363391578010288127

prime M127: 170141183460469231731687303715884105727

prime M521: (157 digits)

prime M607: (183 digits)

prime M1279: (386 digits)

prime M2203: (664 digits)

prime M2281: (687 digits)</pre>