Por que a mediana do segundo fator primo de um inteiro é 37
(grossack.site)- Como não é possível escolher uniformemente entre todos os números naturais, define-se um “inteiro aleatório” escolhendo uniformemente de 1 até N e então observando o limite quando N → ∞
- Em Those Fascinating Numbers, aparece o fato de que a probabilidade de o segundo fator primo de um inteiro aleatório ser menor que 37 é aproximadamente 1/2, o que pode ser confirmado por cálculo de densidade e por experimentos
- Fatores primos pequenos aparecem com frequência como fatores primos pequenos de inteiros, o que cria a intuição de que um número pequeno como 37 pode ser a mediana
- O método de De Koninck e Tenenbaum calcula λ₂(p) combinando condições de divisibilidade por primos específicos, de forma parecida com o crivo de Eratóstenes
- Somando λ₂(p) para cada primo, a densidade acumulada atinge cerca de 0,5002 em 37, muito próxima também do valor calculado diretamente para N=10⁷, 0,5002501
De onde vem o número 37
- No prefácio de Those Fascinating Numbers, há a frase de que 37 é a mediana do segundo fator primo de um inteiro
- Ou seja, a probabilidade de que o segundo fator primo de um inteiro escolhido aleatoriamente seja menor que 37 é aproximadamente 1/2
- À primeira vista, 37 parece pequeno demais para ser crível, mas isso fica plausível quando se considera que primos pequenos aparecem com frequência como fatores primos pequenos de inteiros
- Por exemplo, cerca de metade dos inteiros tem 2 como menor fator primo
- O objetivo é testar esse fato diretamente por experimento e, com base no artigo de De Koninck e Tenenbaum, calcular por que 37 aparece
Como definir um “inteiro aleatório”
- Não existe distribuição uniforme sobre todos os números naturais, então primeiro se fixa um N grande
- Escolhe-se aleatoriamente um inteiro entre 1 e N e, depois, observa-se o limite da probabilidade quando N → ∞
- Quando N é pequeno, é possível encontrar diretamente o segundo fator primo de cada inteiro e verificar a mediana
- Executando com N=10⁷, obtém-se uma aproximação da probabilidade acumulada de 0,5002501
- No SageCell online, fatorações desse tamanho podem demorar demais e causar timeout, então é preciso executar localmente
λ₂(p): a densidade de p ser o segundo fator primo
- No artigo de De Koninck e Tenenbaum Sur la loi de répartition du k-ième facteur premier d’un entier, a densidade dos inteiros para os quais p é o segundo fator primo é denotada por λ₂(p)
- O ponto central do cálculo é contar densidades combinando se há divisibilidade por certos primos, de modo semelhante ao crivo de Eratóstenes
- No caso em que o segundo fator primo é 5, há apenas duas possibilidades
2^a 3^0 5^b ...: números múltiplos de 2 e 5, mas não de 32^0 3^a 5^b ...: números múltiplos de 3 e 5, mas não de 2
- A densidade do primeiro caso é
1/2 × 2/3 × 1/5 = 1/15 - A densidade do segundo caso é
(1 - 1/2) × 1/3 × 1/5 = 1/30 - Como os dois conjuntos não se sobrepõem, podemos somá-los, e a densidade dos inteiros cujo segundo fator primo é 5 fica em 1/10
Fórmula para um primo geral p
- Para que p seja o segundo menor fator primo, deve haver um primo q menor que p presente, enquanto os primos r menores que p, exceto q e p, não devem aparecer
- Essa condição pode ser expressa por uma fatoração prima da forma
[ p^b q^a \prod_{q \neq r \lt p} r^0 ]
- Calculando a densidade para cada q < p e somando, chega-se à seguinte fórmula
[ \lambda_2(p) = \sum_{q \lt p} \frac{1}{p} \frac{1}{q} \prod_{q \neq r \lt p} \left ( 1 - \frac{1}{r} \right ) ]
- A mesma expressão pode ser reorganizada da seguinte maneira
[ \lambda_2(p) = \frac{1}{p} \left[ \prod_{q \lt p} \left(1 - \frac{1}{q}\right) \right] \sum_{q \lt p} \frac{1}{q} \left(1 - \frac{1}{q}\right)^{-1} ]
O cálculo que faz 37 ser a mediana
- O primo (p^) que queremos encontrar é o ponto em que a soma das densidades de o segundo fator primo ser menor ou igual a (p^) fica aproximadamente em 1/2
[ \lambda_2(2) + \lambda_2(3) + \lambda_2(5) + \ldots + \lambda_2(p^*) \approx \frac{1}{2} ]
- Implementando λ₂(p) e somando por primo, a densidade acumulada chega a aproximadamente 1/2 em 37
- A densidade esperada calculada é de cerca de 0,5002
- O valor obtido no experimento direto, baseado em fatoração, para N=10⁷, 0,5002501, também é muito próximo
Extensão para o k-ésimo fator primo
- A fórmula geral para a densidade λₖ(p) de o k-ésimo fator primo ser p é a seguinte
[ \lambda_k(p) = \frac{1}{p} \left[ \prod_{q \lt p} \left(1 - \frac{1}{q}\right) \right] s_{k-1}(p) ]
- Aqui, (s_j(p) = \sum \frac{1}{m}), em que a soma é tomada sobre os m que têm exatamente j fatores primos e cujos fatores primos são todos menores que p
- A assíntota para a mediana do k-ésimo fator primo, (p_k^*), é a seguinte
[ \log \log p_k^* = k - b + O\left(\frac{1}{\sqrt{k}}\right) ]
- Aqui, b é o valor abaixo
[ b = \frac{1}{3} + \gamma - \sum_p \left( \log((1-1/p)^{-1}) - 1/p \right) ]
- (\gamma) é a constante de Euler-Mascheroni
1 comentários
Opiniões no Hacker News
Isso não quer dizer que haja algo particularmente interessante no 37 em si
O fato interessante, na verdade, é que aqui existe uma mediana finita. Se isso vale, como a mediana foi definida como um elemento da lista, ela necessariamente tem que ser algum número primo. Nesta lista, por acaso é 37, mas poderia ser outro valor
Para o 37 ficar realmente interessante, seria preciso relaxar a definição para que a mediana pudesse ser um valor fora do conjunto e, ainda assim, o limite continuasse convergindo para 37. Aí sim seria bem surpreendente
Os valores menores que 37 são apenas cerca de 49,061%, e os maiores que 37 são apenas cerca de 49,975%. A partir de certo ponto, para N par, sempre haverá dois 37 dos dois lados da marca de 50%, então a mediana é exatamente 37, e não outro valor. Deixei uma explicação mais longa em outro comentário [0]
[0] https://news.ycombinator.com/item?id=38245162
A existência da mediana sugere que todos os outros percentis também podem ter limites. Indo além, para qualquer número, pode existir uma proporção-limite dos inteiros cujo segundo fator primo é maior que esse número; no caso de 37, essa proporção por acaso é 0,5
Gostei de como o texto explica claramente a resposta à pergunta que me ocorreu primeiro: “como diabos se prova isso?”
Curiosamente, 37 também aparece no problema de parada ótima / problema da secretária
Coincidentemente, 37 também é o primeiro primo irregular. Isso tem relação com o motivo de o Último Teorema de Fermat ser difícil
https://en.wikipedia.org/wiki/Regular_prime
O texto diz que “os números cujo segundo primo é 2 são 0,000000000000000”; o título continua correto mesmo sem explicitar sem repetição?
Isso porque escrever a notação de forma totalmente explícita em inglês tende a ficar prolixo. Se estivesse escrito “segundo primo sem repetição”, alguém poderia dizer que também deveria estar escrito “segundo menor” ou “em ordem crescente”. Em artigos, esses termos costumam ser definidos formalmente junto com uma notação matemática mais precisa, mas ainda não totalmente rigorosa
Não estou querendo implicar; é porque, em matemática, fazer a pessoa inferir as partes “invisíveis”, em vez de exigir que tudo seja explicitado uma a uma, aumenta muito a usabilidade de assistentes de prova. Há uma boa apresentação relacionada do Andrej Bauer: https://www.youtube.com/watch?v=wZSvuCJBaFU
Fico curioso se há algum teorema ou resultado interessante em funções L ou formas modulares que abarque esse resultado
Estou estudando isso ultimamente, e o tema é fascinante
Descobri assistindo ao vídeo https://www.peakmath.org/quest-for-f1, e http://lmfdb.org também vale explorar
Acho que esse fato torna 37 bem interessante
Pelo menos é certamente mais interessante que 31
31 também é primo, então tem certo interesse, mas não é tão interessante quanto 37, que, como acabamos de aprender, é a mediana do segundo fator primo dos inteiros
Haveria algum candidato a inteiro mais interessante? E será que existe um número que se possa chamar de inteiro mais interessante?
São, respectivamente, as versões big-endian e little-endian da string ASCII “the most interesting”
É interessante que ele apareça tão tarde, apesar de primos irregulares corresponderem a cerca de 41% de todos os primos. Referência: https://encyclopediaofmath.org/wiki/Irregular_prime_number#:~:text=An%20odd%20prime%20number%20p,prime%20numbers%20are%20called%20regular
Qual é o primo mais interessante depende do que você considera mais interessante. Se gosta da mediana do segundo fator primo, 37 é o melhor; se gosta do primeiro primo irregular, 37 também é o melhor. No fim, é uma questão de ponto de vista
Outro motivo para 37 ser bom é que termina em 7, então soa “aleatório” quando alguém pede para você dizer um número, e é melhor que 27 porque é primo. 7 é baixo demais, e 17 tem uma conotação de azar. Ainda assim, 37 também é um número meio assustador. Só por ser primo já é bastante irregular, e ainda por cima é um primo irregular
Por isso o sistema de tempo e a trigonometria provavelmente se basearam em 60. 360 = 6*60, e 360 tem 24 divisores
É surpreendente que a prova seja tão simples. 37 virou meu novo primo favorito
Fico curioso sobre a taxa de crescimento do valor médio do segundo fator primo. Imagino que vá para o infinito, mas talvez cresça bem devagar
Passei a vida toda encucado com esse número. Sempre que olho para o relógio, sempre que vejo a placa do carro da frente, parece que vejo 37
Há também várias associações aleatórias, como o Channel 37: https://en.wikipedia.org/wiki/Channel_37