Factors of a Mersenne number

func mtest(b, p) {
    var bits = b.base(2).digits
    for (var sq = 1; bits; sq %= p) {
        sq *= sq
        sq += sq if bits.shift==1
    }
    sq == 1
}

for m (2..60 -> grep{ .is_prime }, 929) {
    var f = 0
    var x = (2**m - 1)
    var q
    { |k|
        q = (2*k*m + 1)
        q%8 ~~ [1,7] || q.is_prime || next
        q*q > x || (f = mtest(m, q)) && break
    } << 1..Inf
    say (f ? "M#{m} is composite with factor #{q}"
           : "M#{m} is prime")
}

Output:

PreviousFactorionsNextFactors of an integer

Last updated

Was this helpful?