Number of primes 2^n-1 within certain range of n

[bur]

I wanted to calculate how many primes of the form 2^n - 1 can be exptected within a certain range of n based purely on the prime number theorem x/ln(x), no special considerations such as n has to be prime.

Expected number of primes smaller than 2^n - 1 is roughly or .

But we are not looking at all numbers smaller than 2^n - 1, but only at n of them. So the fraction of numbers we consider would be .

Now to my understanding multiplying these two values should yield the expected number of primes of form 2^n - 1, and obviously the multiplication results in a constant: 1.4427.

Is that really the correct answer? I don't think so, but can't figure out where I'm wrong.

[Batalov]

See Lenstra-Pomerance conjecture in https://primes.utm.edu/notes/faq/NextMersenne.html or Wiki

[bur]

Thanks, I read that article before and it seems to deal specifically with Mersenne primes.

I am more generally interested in the number of primes. I just chose the Mersenne form because it's so simple. My question applies also to k * 2^n - 1. I'd run into the same problem of ending up with a constant.

[Batalov]

You ask one question, and then you ask a different question.

For you question about k * 2^n - 1, obviously depends on k. There exist some k values for which the answer is a constant. (zero!)

[bur]

I guess I didn't make clear what my issue is.

As I wrote, I am not looking for special treatment of Sierpinski or Mersenne. I am looking at a general question involving only the Prime Number Theorem:

based purely on the prime number theorem x/ln(x), no special considerations such as n has to be prime.

Thus, it shouldn't matter if we consider 3 * 2^n + 1 or 2^n - 1. Under these circumstances, we should have 2^n/ln(2^n) primes, but we only look at a fraction of these, i.e. n/2^n. And I end up with n/2^n * 2^n/ln(2^n) = 1.4221 which would mean we have a constant expected number of primes which seems strange to me. Hence my question where I made a mistake.

[slandrum]

You are not selecting n "random" numbers below 2^n with an even distribution. If you were, then the constant you are coming up with would be about right. Instead you are selecting a distribution that's very biased toward the low end (where primes are denser).

[Batalov]

Originally Posted by bur

Hence my question where I made a mistake.

Here it is:

Originally Posted by bur

... based purely on the prime number theorem x/ln(x), no special considerations.

Let's demonstrate this on a greatly simplified example:
1. I want to find the density of primes of kind k * n with k=4 (for example), "... based purely on the prime number theorem x/ln(x), no special considerations"
2. I expect ....<blah>.... but in reality it is simply 0.
3. Where is my mistake?
And the answer is (just like the previous speaker said): "You are not selecting "random" numbers". so PNT is either grossly violated (and you can no longer use it), or (if you use some other forms) somewhat mildly (or strongly) violated (and you can no longer use it "correctly").

[LaurV]

Originally Posted by bur

But we are not looking at all numbers smaller than 2^n - 1, but only at n of them. So the fraction of numbers we consider would be .
Now to my understanding multiplying these two values should yield the expected number of primes of form 2^n - 1, and obviously the multiplication results in a constant: 1.4427.

That would be so, if you select n random numbers. But your numbers are not random, they have some properties which make them not to follow the random rule. For example, in all your reasoning, substitute "mersenne numbers" with "even numbers", and see that all your reasoning still apply. For sure, you won't expect to select 2^n/2 even numbers lower than 2^n, and then an inverse-logarithmic fraction of them to be prime.

[wblipp]

Originally Posted by bur

I am more generally interested in the number of primes.

This might be what you want:

The expected number of primes between 10^a and 10^b is ln( a/b ). Also true when replacing "10" with any other base. Now offline, but the wayback machine shows this covered as part of Question #30.