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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
long double pk(long double pkPrec, long long p, int k) { //p est premier et ‡ ajouter ‡ la somme p1 //pkPrec contient la valeur de la somme sur les q < p //k est l'indice de P(p) long double s; int i; s= (1.0L/(p-1)); for(i=1;i<k;i++) s*=s; s = pkPrec + s; return s; } long double alpha(long double alphaPrec, long long p) { //p est premier et ‡ ajouter au produit alphPrec //alphaPrec contient dÈj‡ la valeur du produit q < p long double prod = alphaPrec; prod*= (long double) (1.0L-(1.0L/p)); return prod; } long double somme(long long fin, int*tab,int card) { //on fait la somme jusqu'‡ l'indice fin sur les nombres premiers dans le tableau (de 0) //dans notre cas, il faut commencer ‡ 7. Ajustons les valeurs de dÈpart. long long p; //le nombre premier sur lequel on travaille long double s; //somme gÈnÈrale long double al; long double p1, p2, p3; long long j; //compteur de premiers FILE*fichier; fichier=fopen("premlog.txt", "wt"); s=0.0L; al=1.0L; p1=0.0L;p2=0.0L;p3=0.0L; p=2L; al=alpha(al, p); p1=pk(p1,p,1); p2=pk(p2,p,2); p3=pk(p3,p,3); p=3L; al=alpha(al, p); p1=pk(p1,p,1); p2=pk(p2,p,2); p3=pk(p3,p,3); p=5; al=alpha(al, p); p1=pk(p1,p,1); p2=pk(p2,p,2); p3=pk(p3,p,3); printf("a=%f,p1=%f,p2=%f,p3=%f\n",(float) al,(float) p1,(float) p2,(float) p3); //on commence //p va certainement Ítre 7! j = 4L; for(p=7L; p < fin; p+=2) { if(IsPrime(p,0,tab,card) == 1) {//printf("%lld\t",p); s+=(1.0L/p)*al*(p1*p1*p1/6.0L-p1*p2/2.0L+p3/3.0L); //s=s+(1.0L/p)*al*((1.0L/2)*p1*p1-(1.0L/2)*p2); //s+=al*p1/p; if(j%1000000==0) { printf("%.15f - %lld\n",(float) s, p); fprintf(fichier,"%lld - %.27f\t%.27f\ta=%.27f,p1=%.27f,p2=%.27f,p3=%.27f\n",j,(float) s,p,(float)al,(float)p1,(float)p2,(float)p3);} if(s>=0.5L) {printf("\t%.20f et p=%lld - no.%lld\n",(float) s,p,j); return s;} al=alpha(al, p); p1=pk(p1,p,1); p2=pk(p2,p,2); p3=pk(p3,p,3); j++; }} close(fichier); return s; } |
