mersenneforum.org Number of primes 2^n-1 within certain range of n
 Register FAQ Search Today's Posts Mark Forums Read

 2021-02-16, 08:54 #1 bur   Aug 2020 22·29 Posts Number of primes 2^n-1 within certain range of n 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 $2^n/\ln(2^n)$ or $1.4427*2^n/n$. 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 $n/2^n$. 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.
 2021-02-16, 08:59 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23·52·47 Posts See Lenstra-Pomerance conjecture in https://primes.utm.edu/notes/faq/NextMersenne.html or Wiki
 2021-02-16, 09:03 #3 bur   Aug 2020 22×29 Posts 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.
 2021-02-16, 09:17 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 24B816 Posts 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!)
2021-02-16, 10:23   #5
bur

Aug 2020

22×29 Posts

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:

Quote:
 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.

Last fiddled with by bur on 2021-02-16 at 10:24

 2021-02-17, 00:21 #6 slandrum   Jan 2021 California 2×23 Posts 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). Last fiddled with by slandrum on 2021-02-17 at 00:27
2021-02-17, 00:42   #7
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·52·47 Posts

Quote:
 Originally Posted by bur Hence my question where I made a mistake.
Here it is:
Quote:
 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").

2021-02-17, 01:46   #8
LaurV
Romulan Interpreter

Jun 2011
Thailand

2×3×5×313 Posts

Quote:
 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 $n/2^n$. 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.

Last fiddled with by LaurV on 2021-02-17 at 01:47

2021-02-18, 20:54   #9
wblipp

"William"
May 2003
New Haven

3·787 Posts

Quote:
 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 10a and 10b 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post hal1se Miscellaneous Math 1 2018-07-27 08:12 pepi37 Software 6 2013-05-14 15:11 Unregistered Software 2 2006-08-22 22:54 Unregistered Math 10 2006-08-21 19:54 Joshua2 Math 15 2005-06-11 18:46

All times are UTC. The time now is 16:56.

Fri Apr 23 16:56:07 UTC 2021 up 15 days, 11:36, 0 users, load averages: 2.08, 2.09, 1.99