Distribution of prime factors in result of division

[GP2]

Originally Posted by preda

An interesting question, I'd like to know the answer as well.

I did some googling.

Gillies, discoverer of M21, M22 and M23, made a conjecture about the expected number of prime factors of a Mersenne number. (Wikipedia article)

As Wagstaff (1984) mentions, if we put the values A = 2p (smallest possible factor is 2kp + 1 for k = 1) and B = sqrt (M_p) into Gillies' heuristic formula, then we get the result that the number of prime factors is a Poisson distribution with mean λ = log ( log (2^p/2) / log 2p ).= log ( ( p/2 * log 2 ) / log 2p ) = log( p log 2 / 2 log 2p )

And since the probability of 0 events in a Poisson distribution is e^−λ, Gillies derived the probability that M_p is a Mersenne prime is 2 log 2p / p log 2.

The only trouble is that Gillies' conjecture is wrong. A better prediction of the probability that M_p is prime is given by the Lenstra–Pomerance–Wagstaff conjecture: e^gamma log ap / p log 2, where a = 2 if p = 3 mod 4 and a = 6 if p = 1 mod 4, and where gamma is the Euler–Mascheroni constant ≈ 0.577215665.

If we apply the LPW conjecture correction to the Gillies heuristic for the number of prime factors, then I think we get the result that:

The number of prime factors of M_p is Poisson distributed, with mean λ = log ( p log 2 / e^gamma log ap ), where a and gamma are defined as above.

Whereas by the Erdős–Kac theorem, an ordinary number of size 2^p would be expected to have log(log (2^p)) factors, or log (p log 2).

Maybe someone can double-check the math...

I get the following numbers:

    p        no. of factors of    no. of factors of       no. of factors of
              ordinary number    Mp with p = 3 mod 4      Mp with p = 1 mod 4

     10 000      8.84                     5.97                    5.87
    100 000     11.15                     8.07                    7.98
  1 000 000     13.45                    10.20                   10.12
 10 000 000     15.75                    12.35                   12.29
100 000 000     18.05                    14.53                   14.47