#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/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
}

{ |m|
    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")
} << (2..60 -> lazy.grep{ .is_prime }, 929)
