Fórmula geradora de primos

Ao dividir um inteiro positivo qualquer $n$ por um inteiro positivo $d$, o resultado somente será inteiro se $d$ for divisor de $n$. Se $n$ for um número primo, os divisores são apenas $1$ e o próprio $n$. Se quisermos saber se um $n$ é primo, basta verificar se a divisão resulta num inteiro para divisores $d$ de $2$ até o maior inteiro menor ou igual à raiz quadrada de $n$. Para $n$ primo, nenhuma das divisões por $k \in [2,\lfloor \sqrt{n} \rfloor]$ resulta em inteiro. Se multiplicarmos as partes fracionárias de todas as divisões, o valor somente será zero quando pelo menos um dos fatores for zero, isto é, quando o número for composto. Então a função abaixo, para $n$ maior que $3$, vale zero apenas para os números compostos, e $1$ caso contrário:

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

Para $n$ de $1$ a $3$, o produtório vazio vale $1$. Como $1$ não é primo, podemos multiplicar o valor por

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

que só vale zero para $n=1$. Então a função abaixo, definida para inteiros positivos, devolve $1$ para qualquer primo $n$, e $0$ caso contrário:

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

A função $\pi(n)$ conta quantos números primos existem de $1$ a $n$, usando a função $f$ anterior:

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

O valor de $\pi(0)$ é definido como zero, correspondente ao somatório vazio.

Vamos definir uma função $d_m(k)$ que vale $1$ quando $k=m$, e zero caso contrário:

$$d_m(k)=\left\lfloor \frac{1}{1+(m-k)^2} \right\rfloor$$

Quando $k\neq m$, o denominador fica maior que $1$, e a expressão inteira vale zero. Caso contrário, vale $1$. Então $d_{n}(k)$ vale $1$ apenas quando $k=n$, para algum $n$ fixo.

Se tivermos um limitante superior $N$ para o n-ésimo primo, podemos construir uma função que devolve o n-ésimo primo somando os candidatos $k$ que podem ser o n-ésimo primo, multiplicados por uma função que seleciona apenas o primeiro $k$ tal que $\pi(k)=n$.

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

Quando o índice $k$ for tal que $\pi(k)=n$ e $\pi(k-1)=n-1$, teremos encontrado exatamente o n-ésimo primo.

Sabendo que $p(n)$ cresce aproximadamente como $n \ln n$, podemos usar limitantes superiores como:
$$\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}$$

O primeiro baseia-se no fato de que $p(n)$ é menor que $n⋅(\ln n+\ln(\ln n))$ para $n \geq 6$, sendo os casos menores verificáveis diretamente. O último cresce bastante rápido, e serve como garantia quando não se tem uma boa noção de quanto vale o primo $p(n)$.

Obviamente a fórmula não é eficiente. Ela nada mais é que a notação matemática para o algoritmo de teste de primalidade que faz uso de divisões sucessivas até a raiz quadrada do número sendo testado.

Esta fórmula foi criada (descoberta?) em 2026-05-04 por José Eduardo Gaboardi de Carvalho (edu.a1978 at gmail).