Fórmula geradora de primos

Para descobrir se um número é primo, podemos fazer as divisões por candidatos a fatores do número até a raiz quadrada desse número. Se o resto de alguma divisão por fator maior que $1$ for zero, então o número não é primo. Caso contrário, é primo.

Para detectar quando um quociente é inteiro, faremos uso da função $d_m(n)$ definida abaixo para um inteiro $m$ qualquer. $d_m$ vale $1$ quando o inteiro $n$ for igual a $m$, e zero caso contrário:

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

Quando $n \neq m$, o denominador fica maior que $1$, e a expressão inteira vale zero. Quando $n=m$, o valor é $1$. A função $d_m$ também poderia ser definida para reais $m$ e $n$ e funcionaria da mesma forma, mas não será necessário para o uso a seguir.

A função $P(n)$ abaixo faz uso da função $d_0$ para verificar se o número $n$ possui algum fator inteiro $k = 2, 3, \dots, \lfloor \sqrt{n} \rfloor$, passando para $d_0$ o resto da divisão de $n$ por $k$, dado por $n-k \left\lfloor\frac{n}{k}\right\rfloor$:

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

Para $n \ge 4$, todos os fatores de $P(n)$ são iguais a $1$ se $n$ for primo, portanto $P(n)=1$. Se $n$ for composto, algum fator $0$ fará com que $P(n)=0$.

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.

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 \cdot (\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).