57 est-il un nombre premier ? Il y a un jeu pour ça.

Mme Tech | Pixabay

Le mathématicien grec Euclide pourrait très bien avoir prouvé, vers 300 avant notre ère, qu'il existe une infinité de nombres premiers. Mais c'est le mathématicien britannique Christian Lawson-Perfect qui, plus récemment, a conçu le jeu vidéo Est-ce premier ?

Lancé il y a cinq ans, le jeu a dépassé les trois millions d'essais le 16 juillet (ou, plus précisément, il a atteint les 2 999 999 essais) après une Article de Hacker News généré une vague d'environ 100 000 tentatives.

Le but du jeu est de trier autant de nombres que possible en premier ou non premier en 60 secondes (comme Lawson-Perfect à l'origine décrit ça sur L'apériodique l, un blog de mathématiques dont il est fondateur et éditeur).

Un nombre premier est un nombre entier ayant précisément deux diviseurs, 1 et lui-même.

C'est très simple, mais d'une difficulté exaspérante, déclare Lawson-Perfect, qui travaille dans l'unité d'apprentissage en ligne de la faculté de mathématiques et de statistique de l'université de Newcastle. Il a créé le jeu pendant son temps libre, mais il s'est avéré utile sur le tas : Lawson-Perfect écrit des logiciels d'évaluation en ligne (des systèmes qui évaluent l'apprentissage). Le système que je fabrique est conçu pour générer de manière aléatoire une question de mathématiques et prendre une réponse de l'élève, qu'il note automatiquement et donne des commentaires, dit-il. Vous pourriez considérer le jeu des nombres premiers comme une sorte d'évaluation - il l'a utilisé lors de séances de sensibilisation dans les écoles.

Il a rendu le jeu légèrement plus facile avec des raccourcis clavier - les touches y et n cliquent sur les boutons oui-non correspondants à l'écran - afin de gagner du temps de déplacement de la souris.

Essayer:

Algorithmes de vérification de primalité

Les nombres premiers ont une utilité pratique en informatique, comme avec les codes de correction d'erreurs et le cryptage. Mais alors que la factorisation première est difficile (d'où sa valeur dans le chiffrement), la vérification de la primalité est plus facile, bien que délicate. Mathématicien allemand médaillé Fields Alexandre Grothendieck tristement célèbre 57 pour premier (le premier de Grothendieck). Quand Lawson-Parfait analysé les données du jeu , il a constaté que divers nombres présentaient une certaine Grothendieckyness. Le nombre le plus souvent confondu avec un nombre premier était 51, suivi de 57, 87, 91, 119 et 133, l'ennemi juré de Lawson-Perfect (il a également conçu un service pratique de vérification de la primalité : https://isthisprime.com/2 ).

L'algorithme le plus minimaliste pour vérifier la primauté d'un nombre est la division d'essai - divisez le nombre par chaque nombre jusqu'à sa racine carrée (le produit de deux nombres supérieurs à la racine carrée serait supérieur au nombre en question).

Cependant, cette méthode naïve n'est pas très efficace, pas plus que certaines autres techniques conçues au cours des siècles - comme l'a observé le mathématicien allemand Carl Friedrich Gauss en 1801, elles nécessitent un travail intolérable même pour le calculateur le plus infatigable.

L'algorithme Lawson-Perfect codé pour le jeu s'appelle le test de primalité Miller-Rabin (qui s'appuie sur une méthode très efficace mais pas à toute épreuve du XVIIe siècle, Le petit théorème de Fermat ). Le test de Miller-Rabin fonctionne étonnamment bien. En ce qui concerne Lawson-Perfect, c'est fondamentalement magique - je ne comprends pas vraiment comment cela fonctionne, mais je suis convaincu que je pourrais si je passais le temps de l'examiner plus en profondeur, dit-il.

Puisque le test utilise le hasard, il produit un résultat probabiliste. Ce qui signifie que parfois le test ment. Il y a une chance de découvrir un imposteur, un nombre composé qui essaie de passer pour premier, dit Carl Pomerance, mathématicien au Dartmouth College et co-auteur du livre Nombres premiers : une perspective computationnelle . Cependant, les chances qu'un imposteur passe à travers le mécanisme de vérification intelligent de l'algorithme sont peut-être d'une sur mille, donc le test est assez sûr.

Mais en ce qui concerne les algorithmes intelligents de vérification de la primalité, le test de Miller-Rabin n'est que la pointe de l'iceberg, dit Pomerance. Notamment, il y a 19 ans, trois informaticiens - Manindra Agrawal, Neeraj Kayal et Nitin Saxena, tous de l'Indian Institute of Technology Kanpur - ont annoncé la Test de primalité AKS (encore une fois en s'appuyant sur la méthode de Fermat), qui a finalement fourni un test pour prouver sans équivoque qu'un nombre est premier, sans randomisation et (théoriquement, au moins) avec une vitesse impressionnante. Hélas, rapide en théorie ne se traduit pas toujours par rapide dans la vie réelle, donc le test AKS n'est pas utile à des fins pratiques.

Le record du monde non officiel

Mais l'aspect pratique n'est pas toujours le but. De temps en temps, Lawson-Perfect reçoit des e-mails de personnes désireuses de partager leurs meilleurs scores dans le jeu. Récemment, un joueur a rapporté 60 nombres premiers en 60 secondes, mais le record est plus probablement de 127. (Lawson-Perfect ne suit pas les meilleurs scores ; il sait qu'il y a des tricheurs, avec des tentatives assistées par ordinateur qui produisent des pics dans les données.)

Le score de 127 a été obtenu par Ravi Fernando, étudiant diplômé en mathématiques à l'Université de Californie à Berkeley, qui a publié le résultat en juillet 2020 . C'est toujours son record personnel et, selon lui, le record du monde non officiel.

Depuis l'été dernier, Fernando n'a pas beaucoup joué au jeu avec les paramètres par défaut, mais il a essayé avec des paramètres personnalisés, en sélectionnant des nombres plus importants et en autorisant des délais plus longs - il a marqué 240 avec une limite de cinq minutes. Ce qui a demandé beaucoup de conjectures, car les nombres sont entrés dans la fourchette haute à quatre chiffres et je n'ai jamais mémorisé les nombres premiers que jusqu'aux 3 000 bas, dit-il. Je suppose que certains diront même que c'est excessif.

Les recherches de Fernando portent sur la géométrie algébrique, qui implique dans une certaine mesure les nombres premiers. Mais, dit-il, mes recherches ont plus à voir avec la raison pour laquelle j'ai arrêté de jouer au jeu qu'avec la raison pour laquelle j'ai commencé (il a commencé son doctorat en 2014). De plus, il pense que 127 serait très difficile à battre. Et, dit-il, il semble juste de s'arrêter à un record de nombres premiers.

cacher