Erlang版的计算Mersenne(LucasLehmer)第二版

跟第一版比较，重写了math:pow/2方法，这个方法可以支持很大的幂运算。

-module(mersenne).
-export([run/1,mersenne/1,lucasLehmer_sequence/2,pow/2]).

-spec pow(integer(), non_neg_integer()) -> integer()
      ; (float(), non_neg_integer()) -> float().

pow(X, N) when is_integer(N), N >= 0 -> pow(X, N, 1).

pow(_, 0, P) -> P;
pow(X, N, A) -> pow(X, N-1, A*X).

lucasLehmer_sequence (0, M) -> 4 rem M;
lucasLehmer_sequence (N, M) when N>0 ->
        erlang:round((pow(lucasLehmer_sequence(N-1,M),2)-2)) rem M.

mersenne(N) when N>0 ->
   erlang:round(pow(2,N))-1.

lucasLehmer_test(N) ->
   lucasLehmer_sequence(N - 2, mersenne(N)) =:=0.

run(2) ->
    case lucasLehmer_test(2) of
        true ->
                io:format("M(~w) => ~w~n", [2,mersenne(2)]);
        false ->
                false
    end;
run(N) ->
    case lucasLehmer_test(N) of
        true ->
                io:format("M(~w) => ~w~n", [N,mersenne(N)]);
        false ->
                false
    end,
    run(N-1).

计算梅森数可以算好多，只是效率还有待提高，因为算到M(2281)还是花了一点时间的，不知道Haskell和C#算到M(2281)花了多少时间，ps：这个Erlang版本还是单进程，只用到CPU的一个核。

结果如下：

3> mersenne:run(3000).
M(2281) => 446087557183758429571151706402101809886208632412859901111991219963404685792820473369112545269003989026153245931124316702395758705693679364790903497461147071065254193353938124978226307947312410798874869040070279328428810311754844108094878252494866760969586998128982645877596028979171536962503068429617331702184750324583009171832104916050157628886606372145501702225925125224076829605427173573964812995250569412480720738476855293681666712844831190877620606786663862190240118570736831901886479225810414714078935386562497968178729127629594924411960961386713946279899275006954917139758796061223803393537381034666494402951052059047968693255388647930440925104186817009640171764133172418132836351
M(2203) => 1475979915214180235084898622737381736312066145333169775147771216478570297878078949377407337049389289382748507531496480477281264838760259191814463365330269540496961201113430156902396093989090226259326935025281409614983499388222831448598601834318536230923772641390209490231836446899608210795482963763094236630945410832793769905399982457186322944729636418890623372171723742105636440368218459649632948538696905872650486914434637457507280441823676813517852099348660847172579408422316678097670224011990280170474894487426924742108823536808485072502240519452587542875349976558572670229633962575212637477897785501552646522609988869914013540483809865681250419497686697771007
M(1279) => 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
M(607) => 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127
M(521) => 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
M(127) => 170141183460469231731687303715884105727
M(107) => 162259276829213363391578010288127
M(89) => 618970019642690137449562111
M(61) => 2305843009213693951
M(31) => 2147483647
M(19) => 524287
M(17) => 131071
M(13) => 8191
M(7) => 127
M(5) => 31
M(3) => 7