Distribution of prime numbers

[vlad from moscow]

Is there any theorem in mathematics that proves that if p is a prime number then there must be at least one more prime number between p and 2 * p + 1 (exclusively)?
For example if p = 11 is prime number then there is at least prime number 13 between 11 and 23 ( 2 * p + 1 )

[ResidentBiscuit]

Euclid's theorem? I think that's part of it. If helios were around I'm sure he would know this

EDIT:
Actually, look at Bertrand's postulate. Looks to be exactly that.

http://en.wikipedia.org/wiki/Bertrand%27s_postulate

Wikipedia wrote:

For any integer n > 3, there always exists at least one prime number p with n < p < 2n − 2.

[devonrevenge]

i thought that there was no exact algorithm to find a prime number but there was some mildly consistent patterns for example

N                        primes less than N          N divided by N
/////////////////////////////////////////////////////////////////////////////
1000                         168                            5.9525
1000,000                   78,498                       12.7392
1000,000,000            50,847,534                19.666
                                                                    26.5901
                                                                    33.5069
                                                                    40.4204

see that the average goes up by roughly 7 each time? thats maths apparently!

[vlad from moscow]

@ResidentBiscuit
Actually, look at Bertrand's postulate. Looks to be exactly that.

It is great.:) I asked the question because not so far there was a thread about how to get first 50 prime numbers. The idea to get the next prime number was to check that target number is not divisible by all previous found prime numbers.
So I thought would be it enough to check only those previous found prime numbers that less than target number / 2. That is I can advance the iterator one position ahead and it will guarantee that the next prime number pointed by the iterator will indeed exist and will be greater than target number / 2

[ResidentBiscuit]

vlad from moscow wrote:

The idea to get the next prime number was to check that target number is not divisible by all previous found prime numbers.

In some sieve fashion?

vlad from moscow wrote:

So I thought would be it enough to check only those previous found prime numbers that less than target number / 2. That is I can advance the iterator one position ahead and it will guarantee that the next prime number pointed by the iterator will indeed exist and will be greater than target number / 2.

Not sure what you're getting at here.

[vlad from moscow]

For example I have vector of some first prime numbers.

std::vector<unsigned int> v = { 2, 3, 5, 7, 11, 13 };

Then I take number 15 and check whether it is divisble by one of the existent elements of the vector. If it is divisible I increase the number by 2 and get 17. Then repeat the process. Let assume that 17 is not a prime number. So I will increse it and get 19 and so on.
Now the question is could it be enough to check that 19 is not divisble by elements of the vector values of them are < 19 / 2. Can I increase the iterator?
That is will be valid the following loop

auto it = v.begin();

while ( *it < 19 / 2 && 19 % *it != 0 ) ++it;

That is whether the increment of the iterator will be valid.

Imagine if you have prime numbers only 3, 5, and 19 and you already found prime numbers 3 and 5 and stored them in the vector. Now you are checking whether 19 is a prime number. . Then the loop will be incorrect because after checking the last element with value 5 the iterator will be incremented though there is no such element in the vector. I should guarantee that after all elements in the vector for which *it < 19 /.2 there is at least one next element for which *it > 19 / 2.

[helios]

Now the question is could it be enough to check that 19 is not divisble by elements of the vector values of them are < 19 / 2.

This is one of the worst phrasings ever.

A composite number n will have at least one prime divisor m <= sqrt(n). The reason for this is analogue to how the average of a group of numbers will not be lower than the minimum or higher than the maximum.

[vlad from moscow]

@helios

I think you do not understand the problem.

For example you can write the loop

bool prime = true;
for ( int i = 3; prime && I <=sqrt( n ); i += 2 )
{
   prime = n % i;
}

But how about the vector that contains the previous prime numbers? How will you write the loop

bool prime = true;
for ( auto it = v.begin(); prime && *it <= sqrt( n ); ++it )
{
   prime = n % *it;
} 

Can you guarantee that the operation ++it will be valid and that the vector contains an element for which the condition *it <= sqrt( n ) will be false?
You shall prove that for any primer number n there is already an element in the vector for which *it <= sqrt( n ) will be equal to false.

[helios]

Can you guarantee that the operation ++it will be valid

If v contains all primes below n, yes. It's sufficient if it contains all primes up to sqrt(n), but in that case it'd be better to iterate explicitly up to the end of the vector to avoid edge cases.

and that the vector contains an element for which the condition *it <= sqrt( n ) will be false?

That's what I said in my previous post.

Proof:
Let n be a composite = p1 p2 ... pm such that that sqrt(n) < p1 <= p2 <= ... <= pm.
sqrt(n) < p1
sqrt(p1 p2 ... pm) < p1
p1 p2 ... pm < (p1)^2
p2 ... pm < p1
but p2 >= p1 by definition. Therefore n doesn't exist.

[vlad from moscow]

You can not guarantee this without proving a corresponding theorem that for any given prime number p there is at least one prime number between p and 2 *p + 1.
To organize the loop you should guarantee that the vector contains an element for which the condition *it <= sqrt( n ) will be false that to stop loop iterations..

For example let assume that only the following prime numbers exist: 2, 3, 5 and after 29 and so on. Your vector contains already found prime numbers 2, 3, 5. Then in the loop the condition *it <= sqrt( n ) shall be checked to false that to stop the loop.

for 2, 3, and 5 the condition is true. So you will try to increase the iterator and to dereference it. But there is no such element in the vector after the element with prime number 5. So the code will be invalid.
Of course you can traverse simply the whole vector without setting the condition *it <= sqrt( n ). For example

bool prime = std::all_of( v.begin(), v.end(), [n]( int x ) { return ( n % x ); } );

But it would be more effective to consider only initial elements of the vector that have values satisfying the condition *it <= sqrt( n). In this case you must guarantee that the vector contains an element for which this expression will be false.

That is why I was interested whether such a theorem is already proven in mathematics.

[helios]

for 2, 3, and 5 the condition is true. So you will try to increase the iterator and to dereference it. But there is no such element in the vector after the element with prime number 5. So the code will be invalid.

By the time you get to 26, you will have added all the primes between 6 and 25. I thought it was pretty much a given that you need to keep the vector updated with the newly found primes.
I even said

If v contains all primes below n, yes.

The same is true for any sieve. You can't check an arbitrary number for primality with only a subset of the primes.

[ne555]

@helios: your prove does not apply to the problem.
Show that there is no `n' such that the interval `(sqrt(n); n)' contains no prime numbers

[DeXecipher]

Sounds like an existential problem. Haha ne555 an Idea, an indirect proof where if you prove the contrapositive true or prove the converse/inverse false the your assumptions are true.

[helios]

My understanding is that OP wants to know how many known primes he'll need to check to know if a number is prime. Is that wrong?

[vlad from moscow]

@helios
By the time you get to 26, you will have added all the primes between 6 and 25

It seems that as I said early you do not understand the problem. In my artificial example I meant that there are only prime numbers 2, 3, 5, and 29 and then other prime numbets. There are no prime numbers between 5 and 29. Your should prove that for any given prime number p there is obligatory some prime number between p and 2*p + 1. Only in this case when you will prove this statement you can correctly use the loop I showed.

[ne555]

for(auto p = primes.begin(); p!=primes.end() and *p**p <= n; ++p)
//... 

OP question if `p!=primes.end()' is superfluous

[helios]

Never mind, then.

[Constantine]

I have very recently discovered a formula which generates all Primes, hence it can answer all questions related to prime numbers.

My problem is that all mathematical sites, like arxiv.org , annals.math.princeton.edu etc, I could upload it on and have the evidence I am the first to have solved this for millenniums unsolved problem, are asking me to have one of their own endorse my discovery.

I cannot and should do that, because my discovery could be hijacked or plagiarized.

Any ideas ?

[tntxtnt]

I'm 100% sure your formula is wrong.

or is your trolling mode on?

Use your formula, calculate the 345.678.901th prime for me.

[tition]

A point related to a previous post: the number of primes between 1 and N is approximately ln(N).

http://en.wikipedia.org/wiki/Prime_number_theorem

From what I have heard in various talks and read on Wikipedia, estimating the error term (how far off is the number ln(N) from the actual number of primes below N) is heavily related to the Riemann Hypothesis (the most famous non-solved mathematical problem in modern mathematics).