What would be the immediate implications of a formula for prime numbers?

What would be the immediate implications for Math (or sciences as a general) if someone developed a formula capable of generating every prime number progressively and perfectly, also able to prove (or disprove) the primality of every N-th number. I know this is a very large and subjective answer, however, I would like to know some of these implications – like the breaking of many security systems based on the primes. Moreover, there are examples of practical Math’s implication, not just theoretical, of a possible prime number formula discovery? There is for example in Physics, Chemistry, Geography or Astronomy any field which would be very improved with a so great and dreamed Eureka?

Solutions Collecting From Web of "What would be the immediate implications of a formula for prime numbers?"

There are in fact many ‘formula’s which always generate prime numbers. Among the simplest ones listed by Wikipedia are:

  • There is some real number $A$ such that $\left\lfloor A^{3^n}\right\rfloor$ is always prime.
  • There is some real number $\alpha$ such that $\left\lfloor 2^{2^{\cdots^{\alpha}}} \right\rfloor$ is always prime.
  • The formula $2 + [2(n!) \bmod (n+1)]$ always gives a prime, where here ‘$\bmod$’ (nonstandardly) denotes the remainder.

The third in particular generates every prime.

These formulas are mathematically valid, fun to prove, and highly interesting. However, they are actually completely useless, and not just because we don’t know the values of $A$ and $\alpha$. So (as some have suggested in the comments) a better question is how fast one can generate primes.

The ability (or inability) to generate or check for primes in a certain amount of time is fundamentally important to cryptographic systems such as RSA. However, the “practical” applications of prime numbers (to fields like physics, chemistry, etc.) are, as far as I understand, very few — cryptography is the major application.

As others have mentioned there are many formulas for primes.

I can’t pass up the opportunity to mention my favorite:

$$p_n=1+\sum^{2^n}_{m=1}\left\lfloor \sqrt[n]n \left( \sum^{m}_{x=1}\left\lfloor \cos^2\left( \pi \frac{(x-1)!+1}{x}\right) \right\rfloor \right)^{-1/n} \right\rfloor$$

Maybe it’s just my favorite because it’s so complicated and unwieldy!

I first found the formula in Hacker’s Delight by Warren. The formula is cited as “Willan’s Formula”. The formula can be derived from the fact that $(x-1)!\equiv -1 (\mod x)$ iff x is 1 or prime. So if $((x-1)!+1)/x$ is an integer, $x$ is prime (or 1), so the cosine of this times $\pi$ will be -1 or 1 iff $x$ is prime or 1. $\cos^2$ gets rid of the negative, floor keeps only the values for which the $\cos^2$ is 1.

This formula appears to be described on the mathworld page for prime formulas.

There are dozens, probably hundreds, of formulas for prime numbers. It’s a very well-studied problem. Guy’s Unsolved Problems in Number Theory has a section devoted to this, and Ribenboim’s books cover this in some depth. Many formulas have been published in mathematical journals, and I’ve seen at least one survey paper in a journal dedicated to giving an overview of the various types of formulas for primes.

Finding a new formula for the primes might be interesting enough to be published, but not in a first-rate journal unless there’s something special about it.

As for security concerns, what would be much more important would be a way to solve integer factorization quickly — say, in polynomial time. (At the risk of verbosity, this means the time needed to factor $n$ is less than $(\log n)^k$ for some fixed $k$.) Proving that a number is prime can already be done in polynomial time, see the famous AKS algorithm (or the more practical ECPP).