# Two different ways to count Mersenne Primes

Hi there, the motivation for this question is to better understand the heuristics of Mersenne primes, and I was motivated by the recent questions (Mersenne quasi-primes) and (Primes in generalized Fibonacci sequences). I'd appreciate being told if this approach is misguided or pointless, and I appreciate any effort spent in reading it.

In the paper

S. Wagstaff, "Divisors of Mersenne numbers", Math. Comp., 40(1983), no.161, 385--397,

Wagstaff counts Mersenne primes by already using the knowledge that $2^n-1$ has no chance to be prime when $n$ is composite, and thus he only needs to consider prime factors of $2^n-1$ when $n$ is prime when estimating heuristics.

On the other hand, I wonder if the following is possible. Suppose I pretend that I do not know that $n$ must be prime in order for $2^n-1$ to be prime. Then I would naively conjecture that the number of Mersenne primes less than $x$ is

$$(\mbox{some factor})\sum_{n \leq ( \log x / \log 2)}\frac{1}{n \log 2}.$$

Denis Chaperon de LauziÃ¨res correctly pointed out an earlier mistake I made in the post "Infinitely many primes of the form $2^n+c$ as $n$ varies?" regarding the possible factor in front of the sum, and I will try to modify that later. Now, if you think about it, this approach has some similarity to what is done in the Hardy-Littlewood conjecture F/Bateman-Horn conjecture. For example, we already know that when $n \equiv 2 \bmod 5$, $n^2+1$ will not be prime except when $n=2$, but instead of excluding those $n$, we still count over all $n$ and push that local information into the Hardy-Littlewood/Bateman-Horn constant.

Therefore, the motivation here is simply this: to formulate a conjecture for asymptotics of Mersenne primes which will agree with the Lenstra-Pomerance-Wagstaff heuristics, but in which we deliberately count over all $n$ (instead of excluding composite $n$) and push all the other information into the product before the sum. To phrase it another way - there must be some factor which, if one tries to count Mersenne primes in this way (not excluding composite $n$), can still be multiplied in front of what is obtained so that the resulting estimate must agree with the Lenstra-Pomerance-Wagstaff heuristics - what is that factor?

Now, as mentioned earlier, Denis Chaperon de LauziÃ¨res correctly pointed out that an earlier conjecture I made for the constant was wrong. I did not account for the fact that often, for odd primes $p_1 \not= p_2$, the GCD of the orders of $2$ in $(\mathbb{Z}/p_1\mathbb{Z})^{*}$ and $(\mathbb{Z}/p_2\mathbb{Z})^{*}$ is greater than $1$. But this information can be captured as follows. Let

$$N(x) = \prod_{2< p\leq x}p.$$

Let $M(x)$ be the order of $2$ in $(\mathbb{Z}/N(x)\mathbb{Z})^{*}$. We have $M(x) \leq \lambda(N(x))$ where $\lambda$ is the Carmichael function. Now let $R(x)$ be the number of solutions to $(2^n-1,N(x))>1$, $n\in \mathbb{Z}/M(x)\mathbb{Z}$. Then consider

$$C = \lim_{x \rightarrow \infty}\left(\frac{M(x)-R(x)}{M(x)}\right)\left(\frac{N(x)}{\varphi(N(x))}\right).$$

The first question is, does the limit exist? Now, assuming it does, we say the following:

(a) The constant does not account for the prime $2$, but that can be handled. (b) Part of this constant is not an Euler product, due to the $M(x)$. (c) This constant gives some clue that it can "absorb" some of the inaccuracy from deliberate consideration of $2^n-1$, $n$ composite, when we know better than to do so. For example, we know that we should not bother with $2^{4n}-1$, since $5$ divides those, but this is at least partially adjusted for by the $R(x)$.

Basically, $C$ is an attempt to adjust for local probabilities like in the Hardy-Littlewood/Bateman-Horn constants, also accounting for issues with the GCD of the orders of $2$ in the various $(\mathbb{Z}/p\mathbb{Z})^{*}$. More refined treatment is still probably necessary.

I'd appreciate any comments. Thank you very much.

EDIT:

Thanks very much to all who edited and viewed this. I will make this community wiki. There are two possible generalizations of this, both of which might well be subsumed under an even more general generalization.

Generalization (1): Primes in Lucas sequences $U_n(P,Q)$. (See Wikipedia)

This is completely inherent in the post (Primes in generalized Fibonacci sequences).

Since the Mersenne numbers are $U_n(3,2)$, we set $C = C_{3,2}$, $N(x) = N(3,2;x)$, $M(x) = M(3,2;x)$, and $R(x) = R(3,2;x)$.

For a general Lucas sequence $U_n(P,Q)$, let $\mathbb{P}(P,Q)$ be the set of primes $p$ which never divide any member of $U_n(P,Q)$. For example, $\mathbb{P}(3,2) = \{2\}$. Let

$$N(P,Q;x) = \prod_{\substack{p \leq x\\p \not\in \mathbb{P}(P,Q)}}p.$$

Let $M(P,Q;x)$ be the period of $U_n(P,Q) \bmod N(P,Q;x)$. So $M(P,Q;x)$ is the LCM of the periods of $U_n(P,Q)$ modulo each of the primes dividing $N(P,Q;x)$.

Let $R(P,Q;x)$ be the number of solutions to $(U_n(P,Q), N(P,Q;x))>1$, $n \in \mathbb{Z}/M(P,Q;x)\mathbb{Z}$. Then let

$$C_{P,Q} = \lim_{x \rightarrow \infty}\left(\frac{M(P,Q;x)-R(P,Q;x)}{M(P,Q;x)}\right)\left(\frac{N(P,Q;x)}{\varphi(N(P,Q;x))}\right).$$

Now use the Binet-type formula (See Wikipedia):

$$U_n(P,Q) = \frac{a^n-b^n}{a-b}.$$

Let $c = c_{P,Q} = \max(|a|,|b|)$.

Finally, we naively conjecture (subject to likely future refinement) that the number of primes assumed by $|U_n(P,Q)|$, less than $x$, is asymptotic to

$$(\mbox{factor from future refinement})\prod_{p \in \mathbb{P}(P,Q)}\frac{p}{p-1}C_{P,Q}\sum_{n \leq (\log x/\log c)}\frac{1}{n\log c}.$$

Generalization (2): Primes of the form $A^n+B$, $A,B\in \mathbb{Z}$, $A>1$.

Please also see (Infinitely many primes of the form $2^n+c$ as $n$ varies).

Let $\mathcal{P}(A,B)$ be the set of primes $p$ which never divide $A^n+B$. Let

$$\mathcal{N}(A,B;x) = \prod_{\substack{p \leq x\\p \not\in \mathcal{P}(A,B)}}p.$$

Let $\mathcal{M}(A,B;x)$ be the period of $A^n+B \bmod \mathcal{N}(A,B;x)$. So $\mathcal{M}(A,B;x)$ is the LCM of the periods of $A^n+B$ modulo each of the primes dividing $\mathcal{N}(A,B;x)$.

Let $\mathcal{R}(A,B;x)$ be the number of solutions to $(A^n+B,\mathcal{N}(A,B;x))>1$, $n \in \mathbb{Z}/\mathcal{M}(A,B;x)\mathbb{Z}$. Then let

$$\mathcal{C}_{A,B} = \lim_{x \rightarrow \infty}\left(\frac{\mathcal{M}(A,B;x)-\mathcal{R}(A,B;x)}{\mathcal{M}(A,B;x)}\right)\left(\frac{\mathcal{N}(A,B;x)}{\varphi(\mathcal{N}(A,B;x))}\right).$$

Finally, we naively conjecture (subject to likely future refinement) that the number of primes assumed by $A^n+B$, less than $x$, is asymptotic to

$$(\mbox{factor from future refinement})\prod_{p \in \mathcal{P}(A,B)}\frac{p}{p-1}\mathcal{C}_{A,B}\sum_{n \leq (\log x/\log A)}\frac{1}{n\log A}.$$

The constant $\mathcal{C}_{A,B}$ is able to detect when $A^n+B$ is unable to assume infinitely many prime values, and will be zero in those cases. (Example: $3^n-1$).

-