Intereting Posts

Ring class field of $\mathbb{Q}(\sqrt{-19})$
Finding for every parameter $\lambda$ if matrix is diagonalizable
Connected But Not Path-Connected?
Inverse of a composite function from $\mathbb R$ to $\mathbb{R}^p$ to $\mathbb R$ again with a non-zero continuous gradient in a point
Can this product be written so that symmetry is manifest?
How does one prove if a multivariate function is constant?
Prove that $\dfrac{|x+y|}{1+|x+y|}\leq\dfrac{|x|}{1+|x|}+\dfrac{|y|}{1+|y|}$ for any $x,y$
How to prove $\vdash\neg P\to (P\to Q)$?
Let $R$ be a commutative Noetherian ring (with unity), and let $I$ be an ideal of $R$ such that $R/I \cong R$. Then is $I=(0)$?
Orthogonal projection of a point onto a line
Existence of smooth function $f(x)$ satisfying partial summation
Separable First Order Ordinary Differential Equation with Natural Logarithms
Power-reduction formula
Definition of a tensor for a manifold
Classify sphere bundles over a sphere

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*?

- Pairing function for ordered pairs
- Solving the equation $x^{2}-7^{y}=2$
- What are some strong algebraic number theory PhD programs?
- Characterising reals with terminating decimal expansions
- Finding all solutions of $x^{11}\equiv 1\bmod23,$
- What is the Pontryagin dual of the rationals?
- The product of two numbers that can be written as the sum of two squares
- Number of solutions of $x^2_1+\dots+x^2_n=0,$ $x_i\in \Bbb{F}_q.$
- Subset of natural numbers such that any natural number except 1 can be expressed as sum of two elements
- Bounds for Waring's Problem

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).

- preservation of completeness under homeomorphism
- Prove that every group of order $4$ is abelian
- Is the torsion-free subset not always a subgroup?
- Seemingly hard integrals which are made easy via differentiation under the integral sign a.k.a Feynman Integration
- Prove $F_{1}^{2}+F_{2}^{2}+\dots+F_{n}^{2}=F_{n}F_{n+1}$ using geometric approach
- Intermediate value property problem and continuous function
- Why isn't the Ito integral just the Riemann-Stieltjes integral?
- Finding $E(N)$ in this question
- Applications of the Fibonacci sequence
- Challenge: Demonstrate a Contradiction in Leibniz' differential notation
- Function for concatenated semicircles
- Combinatorics, equality, $n$-permutations with $k$ cycles
- $R/Ra$ is an injective module over itself
- Show that the ring of all rational numbers, which when written in simplest form has an odd denominator, is a principal ideal domain.
- Expected number of dice rolls of an unfair dice to roll every side equally many sides