The Quest for a Prime Number Formula: Why It’s Harder Than You Think

In 2011, Dr. SMRH Moosavi claimed he’d derived a general formula for finding the \(n\)-th prime number. The claim circulated online, sparked a discussion on Math StackExchange, and ultimately didn’t hold up to scrutiny. But the attempt itself is fascinating because it joins a centuries-long line of mathematicians trying to crack the same problem.

Why can’t we find a simple formula that generates all primes? The answer reveals something deep about the nature of numbers themselves.

Why finding a prime formula is so hard

A prime number is a natural number greater than 1 that’s divisible only by 1 and itself. The first few are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… The sequence looks random. And in a very real mathematical sense, it is.

The fundamental problem: primes are defined by what they’re NOT (not divisible by anything except 1 and themselves), which makes them inherently difficult to describe with a positive, constructive formula. You can test whether a number is prime, but generating the next prime from the current one requires knowledge of ALL primes before it.

This is unlike, say, the sequence of perfect squares or triangular numbers, where a simple closed-form expression gives you the \(n\)-th term directly.

The best attempts (and why they all fall short)

Euler’s formula (1772). Leonhard Euler noticed that \(f(n) = n^2 + n + 41\) produces primes for \(n = 0\) through \(n = 39\). That’s 40 consecutive primes from a single quadratic. Impressive. But at \(n = 40\), you get \(40^2 + 40 + 41 = 1681 = 41^2\). Not prime. And it’s provably impossible for any polynomial in one variable to generate all primes. Here’s why: if \(f(0) = p\) for some prime \(p\), then \(f(kp)\) is always divisible by \(p\) for every integer \(k\).

Wilson’s theorem (proved by Lagrange, 1771). A number \(p\) is prime if and only if \((p-1)! \equiv -1 \pmod{p}\). This is mathematically beautiful. It’s a perfect characterization of primality. But it’s computationally useless because computing \((p-1)!\) for large \(p\) is astronomically expensive. Testing whether a 20-digit number is prime using Wilson’s theorem would require computing a factorial with more digits than atoms in the observable universe.

Mills’ constant (1947). W.H. Mills proved that there exists a real constant \(A \approx 1.3064\) such that \(\lfloor A^{3^n} \rfloor\) is prime for all positive integers \(n\). A formula that generates primes. Problem solved? Not quite. Computing the exact value of \(A\) requires you to already know the primes. It’s circular. The formula exists but can’t be used to discover primes you don’t already have.

Mersenne primes. Numbers of the form \(2^p – 1\) where \(p\) is itself prime. Marin Mersenne catalogued these in 1644. Not all produce primes (for example, \(2^{11} – 1 = 2047 = 23 \times 89\)), but the form has yielded every largest known prime for decades. The current record holder, found by Luke Durant in October 2024 through the GIMPS project, is \(2^{136,279,841} – 1\). A number with 41,024,320 digits. The 52nd known Mersenne prime.

The Prime Number Theorem: density without location

In 1896, Jacques Hadamard and Charles-Jean de la Vallée-Poussin independently proved the Prime Number Theorem: the number of primes up to \(x\), written \(\pi(x)\), satisfies

$$ \pi(x) \sim \frac{x}{\ln x} $$

This tells you roughly how many primes exist below any given number. Around 1,000, about 1 in 7 numbers is prime. Around 1,000,000, about 1 in 14. The primes thin out, but they never stop. There are infinitely many of them (Euclid proved this around 300 BC with one of the most elegant proofs in all of mathematics).

But the Prime Number Theorem tells you density, not location. It says “about 620 primes exist between 9,000 and 10,000” without telling you which numbers they are. That’s the fundamental gap.

The Riemann Hypothesis: the deepest connection

The most important unsolved problem in mathematics is directly about prime distribution. In 1859, Bernhard Riemann proposed that all non-trivial zeros of the Riemann zeta function \(\zeta(s)\) have real part \(\frac{1}{2}\). If true, it would give the tightest possible error bound on the Prime Number Theorem:

$$ |\pi(x) – \text{Li}(x)| = O(\sqrt{x} \cdot \ln x) $$

where \(\text{Li}(x)\) is the logarithmic integral. This would mean we’d know the distribution of primes with extraordinary precision, though still not their exact locations.

The Clay Mathematics Institute offers $1 million for a proof. Over 165 years later, it remains open. The first 10 trillion non-trivial zeros have been computed and all lie on the critical line. But that’s not a proof.

Modern primality testing: a different approach

Instead of generating primes, mathematicians shifted to testing whether a given number is prime. The breakthrough came in 2002 when Manindra Agrawal, Neeraj Kayal, and Nitin Saxena (IIT Kanpur) published the AKS primality test. For the first time, there was a deterministic, polynomial-time algorithm that could prove a number prime or composite without relying on any unproven hypothesis.

AKS runs in \(O(\log^{6+\varepsilon}(n))\) time. It earned the Gödel Prize in 2006. In practice, probabilistic tests like Miller-Rabin are faster for most applications, but AKS settled a foundational question: “PRIMES is in P.”

The GIMPS project (Great Internet Mersenne Prime Search, founded 1996 by George Woltman) uses distributed computing with the Lucas-Lehmer test to search for Mersenne primes specifically. It’s found every largest known prime since 1997. Thousands of volunteers donate CPU cycles. The beauty of mathematical collaboration at internet scale.

What Moosavi’s claim tells us

Dr. SMRH Moosavi’s 2011 claim of a general formula for the \(n\)-th prime was not the first such claim, and it won’t be the last. The Math StackExchange discussion quickly identified limitations. These claims typically fall into one of three categories:

1. Formulas that are technically correct but computationally useless (like Mills’ constant or Wilson’s theorem). They encode the primes in their own definition.

2. Formulas that work for a finite range then fail (like Euler’s quadratic). Impressive but incomplete.

3. Formulas with errors or hidden assumptions. Most unverified claims fall here.

The deeper lesson is that primes resist tidy formulas because they’re the building blocks of all integers (via the Fundamental Theorem of Arithmetic). Asking for a formula that generates all primes is like asking for a shortcut that bypasses the structure of multiplication itself.

And that’s not a limitation. It’s what makes primes endlessly fascinating. Every generation of mathematicians takes another run at the problem, and every failure teaches us something new about the deepest patterns in number theory.

Frequently Asked Questions