Possible Ways to Predict Prime Numbers

[sontag]

Why is it so difficult to predict prime numbers?
And has Riemann's conjecture been solved yet?

 

[matt grime]

In what sense do you mean difficult? We could, if given enough time work out all prime numbers less than any given number, of course the universe may end at some point in the interim. I suspect you mean "why is there no nice formula", well, there are several formulae that spit out prime numbers, again all computationally inefficient. So, we get down to: why are there no "closed" generating formulae that mean I can work out the n'th prime on my computer in a matter of seconds.

I think the best answer I have there is that the primes, despite being so carefully governed behave in a way that is almost exactly as if they were "randomly" distributed. We just do not understand enough about them to be able to deal with them properly.

No one has produced an accepted proof of the Riemann Hypothesis.

 

[shmoe]

The primes look pretty random (of course they actually aren't) and don't follow any simple patterns that we're used to. While it's not so easy to predict where individual primes are, the prime number theorem does a good job on their asymptotic density.

The Riemann Hypothesis has not been solved yet.

 

[sontag]

What does "asymptotic density" mean?
Does it amount to the number of primes for every
ten integers (1-10,10-20,20-30 etc.).

 

[dx]

Is it impossible to have a nice formula for the nth prime? or did we just not find one yet?

 

[shmoe]

If $$\pi(x)$$ is the number of primes less than or equal to x, then $$\pi(x)\sim\frac{x}{\log{x}}$$. This is what I meant by asymptotic density.

It depends on what you mean by "nice formula", but there are many that produce the nth prime. There's a bunch at http://mathworld.wolfram.com/PrimeFormulas.html you can decide if any fit your definition of "nice".

 

[CTS]

By the prime number theorem, the nth prime is about n*log(n).

 

[chingkui]

There are many questions about Riemann Hypothesis I always like to ask about:
1) I always hear that RH is important in providing information to the distribution of prime. In particular, how important is it? Why is the distribution of zeros of a function so important? I heard that prime distribution behave nicely if RH is true, but what is meant by "nice"? What if RH turn out to be false? How "badly" will prime distribution behave?
2) Let say if RH fail to be true, does anyone know if it would fail for only finitely many points or infinitely many points? Does the "bad" behavior of prime distribution depend on where the RH fail? Will the "bad behavior" behave "nicer" if RH fail only at small number of points? And does it depend on the magnitude of the complex part of the failed points?

 

[Zurtex]

Of course the same holds true for natural numbers, given a certain limit of time required to work it out, most natural numbers are too large to be calculated in this time.

And we can safely say this by the frivolous theorem of arithmetic.

 

[shmoe]

There are many questions about Riemann Hypothesis I always like to ask about:
1) I always hear that RH is important in providing information to the distribution of prime. In particular, how important is it? Why is the distribution of zeros of a function so important? I heard that prime distribution behave nicely if RH is true, but what is meant by "nice"? What if RH turn out to be false? How "badly" will prime distribution behave?

The prime number theorem in a more accurate form is $\pi(x)=\int_2^x\frac{dt}{\log{t}}+R(x)$, where R(x) is small compared to the integral term (which is known as the logarithmic integral) as x gets large. Really if we define R(x) by this equation then the prime number theorem says R(x) is "small" compared to the logarithmic integral.

The size of R(x) is very intimately connected with the location of the zeros of zeta. The best bounds for it's magnitude are proven from the best known zero free region of zeta. Vice versa would be true (bound on R(x) giving a zero free region), but as far as I know it's never been the case that the best bound for R(x) was proved by a method other than improving the zero free region (though an interesting note in this direction is that the proof of the prime number theorem by elementary methods yields a zero free region given by elementary methods).

Something of this flavour but a pipe dream at the moment (the zero free regions considered are vastly stronger than what's currently provable): if $$1/2\leq\theta<1$$ then $$R(x)=O(x^\theta\log{x})$$ if and only if zeta has no zeros with real part greater than $$\theta$$. So the closer all the zeros of zeta lie to the critical line, the better the logarithmic integral approximation is to $$\pi(x)$$. If RH is true then we get the best possible error term (note that $$\theta=1/2$$ is the best we can hope for due to the obstruction of even one zero on the critical line) and the primes are as nicely behaved as we could hope, meaning the asymptotic is as close as possible to the logarithmic integral.

2) Let say if RH fail to be true, does anyone know if it would fail for only finitely many points or infinitely many points? Does the "bad" behavior of prime distribution depend on where the RH fail? Will the "bad behavior" behave "nicer" if RH fail only at small number of points? And does it depend on the magnitude of the complex part of the failed points?

As far as I know, one miscreant zero doesn't automatically lead to more, except the natural ones from symmetry. They will come in fours off the critical line (and in the critical strip) from the symmetry about the point 1/2 (from the functional equation) and over the real axis.

I haven't thought too much about what effect the magnitude of the complex part of a miscreant zero would do. On one hand it will cause faster oscillations, on the other the magnitude of these oscillations will be less (see Riemann's explicit formula). My first guess would be that the higher the complex part, the less disruptive it is. It might depend on what finer scale you actually use to measure how 'bad' things are. In any case, on the large scale of simply the magnitude of the error term R(x), it doesn't affect it.

The bad behavior (meaning worse bounds on the error term R(x)) will be as bad as the real part of the largest nasty zero. About the number of zeros going wrong and how bad things get, the same thing applies as in the paragraph above, it might depend on the scale you use (probably more bad zeros, the worse off you are) but with the crude measurement of the best possible bound of the error term, it won't matter.

 

[neurocomp2003]

whats faster thatn the simplest algorithm and just as accurate:
SimplestAlgorithm:
iterate from 2 to prime number less than sqrt of N.
check if prime number is a factor.

eg. elliptic curve algorithsm...can anyone describe them? by only using 2nd year university math?

 

[dx]

by "nice forumula", I meant some function in which you could plug in 'n', and it would give you the nth prime.

 

[Data]

There are such formulae, as others have indicated. They're just so inneficient that they aren't practical for actual use. Some are listed at the mathworld link in post #6.

 

[noslen]

Whats which of these are possible

a) finding this "nice formula"

or

b) finding a proof that this "nice formula" does not exist

 

[noslen]

which of these are possible

a) finding this "nice formula"

or

b) finding a proof that this "nice formula" does not exist