Oferecido por
O matemático grego Euclides pode muito bem ter provado, por volta de 300 A.C, que existem infinitos números primos. Mas foi o matemático britânico Christian Lawson-Perfect quem, mais recentemente, criou o jogo de computador “Is this prime?”
Lançado há seis anos, o jogo ultrapassou três milhões de tentativas em 16 de julho de 2021 — ou, mais precisamente, 2.999.999 — depois que um post do Hacker News gerou um aumento de cerca de 100.000 tentativas.
O objetivo do jogo é classificar o maior número possível de números como “primos” ou “não primos” em 60 segundos (como Lawson-Perfect descreveu originalmente no The Aperiodica l, um blog de matemática do qual ele é fundador e editor).
Um número primo é um número inteiro com precisamente dois divisores, 1 e ele mesmo.
“É muito simples, mas irritantemente difícil”, diz Lawson-Perfect, que trabalha na unidade de e-learning da Escola de Matemática e Estatística da Universidade de Newcastle, Reino Unido. Ele criou o jogo em seu tempo livre, mas achou útil em seu trabalho: Lawson-Perfect escreve software de avaliação eletrônica (sistemas que avaliam o aprendizado). “O sistema que faço é projetado para gerar aleatoriamente uma pergunta de matemática e receber uma resposta do aluno, que marca o resultado e automaticamente recebe um feedback”, diz ele. “Você pode ver o jogo dos números primos como uma espécie de avaliação”, complementa, e admite já o ter usado ao fazer sessões de divulgação nas escolas.
Ele tornou o jogo um pouco mais fácil com atalhos de teclado (as teclas y e n clicam nos botões sim-não correspondentes na tela) para economizar tempo de movimentação do mouse.
Confira o site “aqui”
Algoritmos de verificação de primalidade
Os números primos têm utilidade prática na computação como códigos de correção de erros e criptografia. No entanto, enquanto a fatoração primária é difícil (daí seu valor na criptografia), verificar a primalidade de um número é mais fácil, embora complicado. O matemático alemão vencedor da Medalha Fields, Alexander Grothendieck, infamemente confundiu 57 com um primo (o que deu origem a alcunha “o número primo de Grothendieck”). Quando Lawson-Perfect analisou os dados do jogo, descobriu que vários números exibiam um certo tipo de erro no estilo Grothendieck. O número mais frequentemente confundido com um primo era 51, seguido por 57, 87, 91, 119 e 133, o inimigo de Lawson-Perfect (ele também criou um serviço útil de verificação de primalidade: https://isthisprime.com/2).
O algoritmo mais minimalista para verificar a primazia de um número é a divisão experimental: divida o número por cada número até sua raiz quadrada (o resultado de dois números maiores que a raiz quadrada seria maior que o número em questão).
No entanto, esse método simples não é muito eficiente, assim como algumas outras técnicas criadas ao longo dos séculos, como observado em 1801 pelo matemático alemão Carl Friedrich Gauss, elas “exigem trabalho intolerável mesmo para a calculadora mais infatigável”.
O algoritmo que Lawson-Perfect programou para o jogo é chamado de teste de primalidade de Miller-Rabin que se baseia em um método muito eficiente, mas não infalível, do século XVII, o teste de primalidade de Fermat. O teste de Miller-Rabin funciona surpreendentemente bem. No que diz respeito a Lawson-Perfect, é “basicamente mágico”, que afirma: “Eu realmente não entendo como isso funciona, mas estou confiante de que poderia, se tivesse tempo para analisá-lo mais atentamente”, diz ele.
Como o teste usa aleatoriedade, ele produz um resultado probabilístico. O que significa que às vezes o teste mente. “Há uma chance de identificar um impostor, um número composto que está tentando se passar como primo”, diz Carl Pomerance, matemático do Dartmouth College (EUA) e coautor do livro Prime Numbers: A Computational Perspective. As chances de um impostor passar pelo mecanismo de verificação inteligente do algoritmo são talvez uma em um trilhão, então o teste é “bastante seguro”.
Mas no que diz respeito aos algoritmos inteligentes de verificação de primalidade, o teste de Miller-Rabin é “a ponta do iceberg”, diz Pomerance. Há 20 anos, três cientistas da computação do Indian Institute of Technology Kanpur (Índia), Manindra Agrawal, Neeraj Kayal e Nitin Saxena, notavelmente anunciaram o teste de primalidade AKS (mais uma vez baseado no método de Fermat), que finalmente forneceu um teste para provar inequivocamente que um número é primo, sem randomização e (teoricamente, pelo menos) com velocidade impressionante. Infelizmente, rápido na teoria nem sempre se traduz em rápido na vida real, então o teste AKS não é útil para fins práticos.
O recorde mundial não-oficial
Mas a praticidade nem sempre é o ponto. Ocasionalmente, Lawson-Perfect recebe e-mails de pessoas interessadas em compartilhar suas pontuações mais altas no jogo, como o caso de um jogador que identificou 60 primos em 60 segundos, mas o recorde mais provável na época era de 127. (Lawson-Perfect não registra pontuações altas; ele sabe que existem alguns trapaceiros, com tentativas auxiliadas por computador que produzem picos nos dados.)
A pontuação 127 foi alcançada por Ravi Fernando, estudante de pós-graduação em matemática da Universidade da Califórnia, em Berkeley (EUA), que divulgou o resultado em julho de 2020. Até então, é seu recorde pessoal e, segundo ele, o “recorde mundial não-oficial”.
Após o seu recorde não-oficial, Fernando tentou jogar com as configurações personalizadas, selecionando números maiores e permitindo prazos mais longos: ele marcou 240 com um limite de cinco minutos. “O que exigiu muita adivinhação, porque os números chegaram à faixa de quatro dígitos e eu só memorizei primos abaixo de 3.000”, diz ele. “Acho que alguns até diriam que isso é excessivo”.
A pesquisa de Fernando é sobre geometria algébrica, que envolve até certo ponto números primos. Mas, diz ele, “minha pesquisa tem mais a ver com o motivo pelo qual parei de jogar do que com o motivo pelo qual comecei” (ele começou seu doutorado em 2014). Além disso, ele acha que a marca de 127 seria muito difícil de alcançar. E, conclui, “parece certo parar em um recorde de números primos que é em si um número primo”.
MIT Technology Review
