mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2021-02-16, 08:54   #1
bur
 
Aug 2020

3×37 Posts
Default 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.
bur is offline   Reply With Quote
Old 2021-02-16, 08:59   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

222668 Posts
Default

See Lenstra-Pomerance conjecture in https://primes.utm.edu/notes/faq/NextMersenne.html or Wiki
Batalov is offline   Reply With Quote
Old 2021-02-16, 09:03   #3
bur
 
Aug 2020

11110 Posts
Default

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.
bur is offline   Reply With Quote
Old 2021-02-16, 09:17   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·37·127 Posts
Default

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!)
Batalov is offline   Reply With Quote
Old 2021-02-16, 10:23   #5
bur
 
Aug 2020

3×37 Posts
Default

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
bur is offline   Reply With Quote
Old 2021-02-17, 00:21   #6
slandrum
 
Jan 2021
California

2·23 Posts
Default

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
slandrum is offline   Reply With Quote
Old 2021-02-17, 00:42   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100101101102 Posts
Lightbulb

Quote:
Originally Posted by bur View Post
Hence my question where I made a mistake.
Here it is:
Quote:
Originally Posted by bur View Post
... 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").
Batalov is offline   Reply With Quote
Old 2021-02-17, 01:46   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5·1,877 Posts
Default

Quote:
Originally Posted by bur View Post
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
LaurV is offline   Reply With Quote
Old 2021-02-18, 20:54   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default

Quote:
Originally Posted by bur View Post
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.
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
quadruplets (so:twin primes) analysis every exponantial range hal1se Miscellaneous Math 1 2018-07-27 08:12
sr2sieve- number of candidates in range pepi37 Software 6 2013-05-14 15:11
Program - primes between number/range Unregistered Software 2 2006-08-22 22:54
Largest range between primes? Unregistered Math 10 2006-08-21 19:54
Twin primes in the 50,000 digit range? Joshua2 Math 15 2005-06-11 18:46

All times are UTC. The time now is 12:03.

Thu Apr 22 12:03:09 UTC 2021 up 14 days, 6:44, 0 users, load averages: 2.42, 2.08, 1.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.