Médiane du 4ième facteur premier des nombres naturels

Ce billet s’adresse aux mathématiciens et adeptes très intéressés. J’ai retrouvé récemment mon algorithme (ou une partie de celui-ci).

À l’Université, j’ai travaillé momentanément pour Jean-Marie De Koninck afin de programmer un algorithme permettant de découvrir la médiane du 4ième facteur premier des nombres naturels en un temps raisonnable. C’est un problème en théorie des nombres, et dont la solution pourrait être utile à ceux faisant de la recherche en cryptographie ou en factorisation des grands nombres premiers.

J’ai égaré beaucoup de documentation (notamment la formule découverte par Jean-Marie De Koninck), mais comme je viens tout juste de retrouver mon algorithme, je me disais que je me devais de le publier pour la prospérité.

Ma découverte, le nom 5 737 580 066 077 (de mémoire) a été publié dans un livre de Jean-Marie De Koninck que vous pouvez vous procurer ici sur Amazon.

Qu’est ce que ce nombre représente ?

Le nombre est la médiane du 4ième facteur premier. Je vais vous expliquer ce que représenterait le 1er facteur premier.

Prenons tous les nombres naturels supérieurs à 1. Décomposons-les en leurs facteurs premiers (^ veut dire exposant). Exemple:

2=2
3=3
4=2^2
5=5
6=2*3
7=7
8=2^3
9=3*3
10=2*5

Prenons le premier nombre premier de chaque décomposition (en ignorant son exposant) et faisons une statistique dessus. On obtiendra:

2, 3, 2, 5, 2, 7, 2, 3, 2, …

Ordonnons-les en ordre croissant

2, 2, 2, 2, 2, 3, 3, 5, 7, …

Clairement, la médiane (le nombre du milieu) est 2. C’est plutôt trivial car la moitié des nombres naturels sont pairs. On obtiendra donc 2 comme premier facteur premier de la moitié des nombres.

Ce que mon algorithme a permis de trouver, c’est la médiane du 4ième facteur premier (la statistique obtenue en ne prenant que les 4ièmes facteurs, pour les nombres ayant 4 facteurs ou plus, cela va de soi).

L’algorithme trivial

Il était facile de construire un algorithme permettant de résoudre l’équation découverte par Jean-Marie De Koninck. Par contre, cet algorithme devait être exécuté sur chacun des nombres premiers jusqu’à ce que la valeur de l’équation dépasse une certaine valeur.

Mon algorithme initial aurait pris, selon mes calculs, plus de trois mois avant d’arriver au nombre. Trois mois, si seulement il ne s’arrête pas, et s’il ne rencontre pas d’obstacle !

J’ai donc dû trouver une meilleure solution. J’ai optimisé chaque commande IF, la librairie de calculs en grands nombres (car un nombre de cette taille ne se gérait pas avec les ordinateurs 32 bits de l’époque et il était impossible de faire des calculs avec les nombres) mais malgré tout, l’exécution était fastidieuse. Le problème résidait aussi dans la grande quantité de mémoire requise pour trouver les nombres premiers.

J’ai utilisé le crible d’Ératosthène pour prévoir d’avance une certaine plage de nombres premiers (20 000, de mémoire).

Le code de l’algorithme

J’ai programmé le tout en language C, en 2006 lorsque j’étais moins avancé en programmation qu’aujourd’hui. Je vous demande donc d’être indulgent :-)

Aussi, je n’ai pas ré-exécuté mon code depuis, ni même avant d’écrire ce billet. Je ne sais pas s’il est partiel ou complet, et s’il fonctionne bien avec cette version.

J’ai utilisé une librairie de « bigDigits » que vous trouverez ici, accompagnée de l’archive de mon algorithme. Cliquez ici pour tout télécharger

Voici le coeur de l’algorithme principal: