Possible Ways to Predict Prime Numbers

In summary, predicting prime numbers is difficult because they behave almost as if they were randomly distributed, making it hard to find a formula for generating them efficiently. The Riemann Hypothesis, which is important in understanding the distribution of prime numbers, has not yet been proven. The distribution of primes is "nice" when RH is true, meaning that their behavior closely follows a logarithmic integral approximation. If RH were to fail, it is unclear if it would fail for only finitely many points or infinitely many points, and the severity of the "bad" behavior would depend on the location and magnitude of the miscreant zeros.
  • #1
sontag
42
0
Why is it so difficult to predict prime numbers?
And has Riemann's conjecture been solved yet?
 
Mathematics news on Phys.org
  • #2
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.
 
  • #3
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.
 
  • #4
What does "asymptotic density" mean?
Does it amount to the number of primes for every
ten integers (1-10,10-20,20-30 etc.).
 
  • #5
Is it impossible to have a nice formula for the nth prime? or did we just not find one yet?
 
  • #6
If [tex]\pi(x)[/tex] is the number of primes less than or equal to x, then [tex]\pi(x)\sim\frac{x}{\log{x}}[/tex]. 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".
 
  • #7
By the prime number theorem, the nth prime is about n*log(n).
 
  • #8
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?
 
  • #9
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.
 
  • #10
chingkui said:
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 [itex]\pi(x)=\int_2^x\frac{dt}{\log{t}}+R(x)[/itex], 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 [tex]1/2\leq\theta<1[/tex] then [tex]R(x)=O(x^\theta\log{x})[/tex] if and only if zeta has no zeros with real part greater than [tex]\theta[/tex]. So the closer all the zeros of zeta lie to the critical line, the better the logarithmic integral approximation is to [tex]\pi(x)[/tex]. If RH is true then we get the best possible error term (note that [tex]\theta=1/2[/tex] 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.

chingkui said:
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.
 
Last edited:
  • #11
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?
 
  • #12
by "nice forumula", I meant some function in which you could plug in 'n', and it would give you the nth prime.
 
  • #13
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.
 
  • #14
Whats which of these are possible

a) finding this "nice formula"

or

b) finding a proof that this "nice formula" does not exist
 
  • #15
which of these are possible

a) finding this "nice formula"

or

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

What are prime numbers?

Prime numbers are numbers that are only divisible by 1 and themselves. They have no other factors.

Why is predicting prime numbers important?

Predicting prime numbers is important in mathematics and cryptography. Prime numbers are the building blocks of many mathematical concepts and are used in encryption algorithms to keep data secure.

How can prime numbers be predicted?

There are many different methods for predicting prime numbers, including the Sieve of Eratosthenes, the Sieve of Sundaram, and the Miller-Rabin primality test. These methods use various algorithms and mathematical equations to determine whether a number is prime.

Is there a formula for predicting prime numbers?

While there is no simple formula for predicting prime numbers, there are patterns and rules that can help identify prime numbers. However, these patterns are not foolproof and cannot predict all prime numbers.

Can prime numbers be predicted infinitely?

No, it is not possible to predict prime numbers infinitely. As the numbers get larger, it becomes increasingly difficult to accurately predict whether a number is prime or not. Therefore, there is no way to predict all prime numbers with complete certainty.

Similar threads

Replies
8
Views
353
Replies
1
Views
1K
  • General Math
Replies
3
Views
547
Replies
56
Views
5K
Replies
1
Views
750
Replies
2
Views
1K
Replies
8
Views
1K
Replies
4
Views
913
Replies
5
Views
887
Replies
1
Views
728
Back
Top