A Prime-Generating Formula

To determine whether a number is prime, one can test divisibility by candidate factors up to its square root. If any division by an integer greater than $1$ yields a zero remainder, then the number is not prime. Otherwise, it is prime.

To detect when a quotient is an integer, we introduce the function $d_m(n)$, defined for any integer $m$. This function returns $1$ when $n=m$, and $0$ otherwise:

$$d_m(n)=\left\lfloor \frac{1}{1+ \left| m-n \right| } \right\rfloor$$

When $n \neq m$, the denominator is greater than $1$, and the expression evaluates to $0$. When $n = m$, the value is $1$. The function $d_m$ could also be defined for real values of $m$ and $n$, and would behave in the same way, but this is not necessary for our purposes.

We now define a function $P(n)$ that checks whether $n$ has any nontrivial integer factor. For each integer $k = 2, 3, \dots, \lfloor \sqrt{n} \rfloor$, we compute the remainder of the division of $n$ by $k$, given by $n - k \left\lfloor \frac{n}{k} \right\rfloor$, and apply $d_0$:

$$P(n)=\prod_{k=2}^{\lfloor \sqrt{n}\rfloor} \left( 1 - d_0 \left(n - k \left\lfloor \frac{n}{k}\right\rfloor\right) \right)$$

For $n \ge 4$, all factors in this product are equal to $1$ when $n$ is prime, so $P(n)=1$. If $n$ is composite, at least one factor is $0$, which makes $P(n)=0$.

For $n = 1, 2, 3$, the product is empty and therefore equal to $1$. Since $1$ is not prime, we introduce a correction factor:

$$z(n)=\left\lceil\frac{n-P(n)}{n}\right\rceil$$

This expression is zero only when $n=1$. We can now define a function that indicates primality:

$$f(n)=z(n) \cdot P(n)$$

This function returns $1$ if $n$ is prime and $0$ otherwise.

The prime-counting function $\pi(n)$ is then given by:

$$\pi(n)=\sum_{m=1}^{n} f(m)$$

We also define $\pi(0)=0$, corresponding to the empty sum.

Given an upper bound $N$ for the $n$-th prime, we can construct a function that returns the $n$-th prime by summing candidate values $k$, weighted by a selector that picks out the first $k$ such that $\pi(k)=n$:

$$p(n)=\sum_{k=1}^{N} k \cdot d_n(\pi(k)) \cdot d_{n-1}(\pi(k-1))$$

This works because the $n$-th prime is precisely the value of $k$ for which $\pi(k)=n$ and $\pi(k-1)=n-1$.

Since $p(n)$ grows approximately as $n \ln n$, we can use upper bounds such as:

$$\begin{array}{l} N = \left\lfloor 2+n \cdot (\ln n + \ln \left( 1 + \ln n \right)) \right\rfloor \\ N = n^2+1 \\ N = 2^{2^n} \end{array}$$

The first bound relies on the fact that $p(n)$ is less than $n \cdot (\ln n+\ln(\ln n))$ for $n \ge 6$, with smaller cases verifiable directly. The last grows very rapidly and serves as a guaranteed bound when no good estimate for $p(n)$ is available.

This formula is not computationally efficient. It is simply a mathematical reformulation of the classical primality test based on successive divisions up to the square root of the number being tested.

This formula was created (discovered?) on 2026-05-04 by José Eduardo Gaboardi de Carvalho (edu.a1978 at gmail).