Calculando a probabilidade de escolher aleatoriamente um número primo

ROBERT BROOK / Getty Images

A teoria dos números é um ramo da matemática que se preocupa com o conjunto dos inteiros. Nós nos restringimos um pouco ao fazer isso, pois não estudamos diretamente outros números, como irracionais. No entanto, outros tipos de numeros reais são usados. Além disso, o assunto da probabilidade tem muitas conexões e interseções com a teoria dos números. Uma dessas conexões tem a ver com a distribuição de números primos. Mais especificamente, podemos perguntar, qual é a probabilidade de que um inteiro escolhido aleatoriamente de 1 a x é um número primo?

Premissas e Definições

Como em qualquer problema de matemática, é importante entender não apenas quais suposições estão sendo feitas, mas também as definições de todos os termos-chave do problema. Para este problema estamos considerando os inteiros positivos, ou seja, os números inteiros 1, 2, 3, . . . até algum número x . Estamos escolhendo aleatoriamente um desses números, o que significa que todos x deles têm a mesma probabilidade de serem escolhidos.

Estamos tentando determinar a probabilidade de que um número primo seja escolhido. Assim, precisamos entender a definição de um número primo. Um número primo é um número inteiro positivo que tem exatamente dois fatores. Isso significa que os únicos divisores de números primos são um e o próprio número. Então 2,3 e 5 são primos, mas 4, 8 e 12 não são primos. Notamos que, como deve haver dois fatores em um número primo, o número 1 é não melhor.

Solução para números baixos

A solução para este problema é simples para números baixos x . Tudo o que precisamos fazer é simplesmente contar os números de primos que são menores ou iguais a x . Dividimos o número de primos menor ou igual a x pelo número x .

Por exemplo, para encontrar a probabilidade de que um primo seja selecionado de 1 a 10, é necessário dividir o número de primos de 1 a 10 por 10. Os números 2, 3, 5, 7 são primos, então a probabilidade de um primo ser selecionado é 4/10 = 40%.

A probabilidade de que um primo seja selecionado de 1 a 50 pode ser encontrada de maneira semelhante. Os primos menores que 50 são: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 e 47. Existem 15 primos menores ou iguais a 50. Assim, a probabilidade de que um primo seja selecionado ao acaso é 15/50 = 30%.

Esse processo pode ser realizado simplesmente contando os primos, desde que tenhamos uma lista de primos. Por exemplo, existem 25 primos menores ou iguais a 100. (Assim, a probabilidade de que um número escolhido aleatoriamente de 1 a 100 seja primo é 25/100 = 25%). No entanto, se não tivermos uma lista de primos, pode ser computacionalmente assustador determinar o conjunto de números primos que são menores ou iguais a um determinado número x .

O Teorema dos Números Primos

Se você não tiver uma contagem do número de primos que são menores ou iguais a x , existe uma maneira alternativa de resolver esse problema. A solução envolve um resultado matemático conhecido como teorema dos números primos. Esta é uma afirmação sobre a distribuição geral dos primos e pode ser usada para aproximar a probabilidade que estamos tentando determinar.

O teorema dos números primos afirma que existem aproximadamente x /ln( x ) números primos menores ou iguais a x . Aqui ln( x ) denota o logaritmo natural de x , ou em outras palavras o logaritmo com uma base de o número e . Como o valor de x aumenta a aproximação melhora, no sentido de que vemos uma diminuição no erro relativo entre o número de primos menor que x e a expressão x /ln( x ).

Aplicação do Teorema dos Números Primos

Podemos usar o resultado do teorema dos números primos para resolver o problema que estamos tentando resolver. Sabemos pelo teorema dos números primos que existem aproximadamente x /ln( x ) números primos menores ou iguais a x . Além disso, há um total de x inteiros positivos menores ou iguais a x . Portanto, a probabilidade de que um número selecionado aleatoriamente neste intervalo seja primo é ( x /ln( x ) ) / x = 1 / ln( x ).

Exemplo

Agora podemos usar esse resultado para aproximar a probabilidade de selecionar aleatoriamente um número primo do primeiro bilhão inteiros. Calculamos o logaritmo natural de um bilhão e vemos que ln(1.000.000.000) é aproximadamente 20,7 e 1/ln(1.000.000.000) é aproximadamente 0,0483. Assim, temos cerca de 4,83% de probabilidade de escolher aleatoriamente um número primo entre os primeiros bilhões de inteiros.