Le Forum de l'Alliance Francophone

Nouvelles:

Auteur Sujet: Description des projets mathématiques  (Lu 24640 fois)

0 Membres et 1 Invité sur ce sujet

Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
le: 10 September 2014 à 23:49
PAGE EN CONSTRUCTION

Cette page a pour but de décrire et d'expliquer les théorèmes et conjectures mathématiques sur lesquels les différents projets travaillent.

Voici la liste (encore provisoire et risque de diminuer) des différents projets mathématiques décrits :

  • ABC@home
  • Collatz Conjecture
  • Enigma@Home
  • Moo! Wrapper
  • NumberFields@home
  • Primaboinca
  • PrimeGrid
  • PRPNet
  • Rectilinear Crossing Number
  • SubsetSum@Home
  • SZTAKI Desktop Grid
  • Yoyo@home

Je voudrais remercier Sébastien pour avoir mis en place sur le forum les balises jstex permettant d'écrire des formules mathématiques (en LaTex).
Par exemple
[jstex]n! \sim \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n[/jstex] donne
n! \sim \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n
« Modifié: 30 March 2015 à 17:46 par Matt11 »


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #1 le: 10 September 2014 à 23:49
[RESERVE]


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #2 le: 10 September 2014 à 23:49
[RESERVE]


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #3 le: 10 September 2014 à 23:49
[RESERVE]


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #4 le: 10 September 2014 à 23:50
[RESERVE]


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #5 le: 10 September 2014 à 23:50
[RESERVE]


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #6 le: 10 September 2014 à 23:50
Primaboinca

Primaboinca est un projet qui essaye d'infirmer ou à défaut de renforcer deux conjectures de théorie des nombres. Ces conjectures sont utiles dans l'élaboration du meilleur algorithme de primalité déterministe actuellement connu.

Avant d'énoncer ces deux conjectures (conjecture d'Agrawal et conjecture de Popovych) , voici une rapide présentation de l'algorithme AKS.

          L'algorithme AKS

L'algorithme AKS est le premier et actuellement le meilleur algorithme de primalité déterministe (c'est-à-dire qui détermine de façon certaine si un nombre est premier contrairement aux algorithmes probabilistes). Il a été découvert en 2002 par les trois mathématiciens indiens Agrawal-Kayal-Saxena (d'où le nom AKS).
Sa complexité est polynomiale, ce qui est théoriquement très performant pour ce type de problème mais il n'est que très rarement utilisé dans la pratique car il n'est efficace que sur les très grands nombres premiers.

L'algorithme AKS repose sur la généralisation suivante du petit théorème de Fermat :

Théorème  : Soit a et n des entiers naturels premiers entre eux. On a alors
n \text{ est premier } \Leftrightarrow (X+a)^n=X^n+a ~~\text{ dans }~~ \mathbb{Z}/n\mathbb{Z}[X]

Référence : https://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_AKS

          Conjecture d'Agrawal

Le théorème ci dessus nous donne un test de primalité relativement simple. Pour déterminer si n est premier il suffit d'évaluer la relation (X+a)n=Xn+a.
Cependant dans les cas les moins favorables il faut tout de même évaluer les n coefficients du polynôme (X+a)n.
C'est pourquoi Agrawal a proposé en 2002 la conjecture suivante ayant pour but de simplifier le calcul.

Conjecture  : Soit r un nombre premier qui ne divise pas n. On a
(X-1)^n=X^n-1 ~\text{ dans }~ \mathbb{Z}_n[X]/(X^r-1) ~\Rightarrow~ n \text{ est premier ou } n^2 \equiv 1 ~[r]

Hendrik Lenstras et Carl Pomerances ont, par des arguments heuristiques, suggéré qu'il existait une infinité de contre-exemples à cette conjecture et donc que cette conjecture était fausse. Cependant aucun contre-exemple n'a encore été trouvé.
Un des buts de ce projet est de tester cette conjecture. Cela a été fait pour tout n < 1010 sans avoir trouvé de contre-exemple.

Références : http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf  et https://en.wikipedia.org/wiki/Agrawal%27s_conjecture

          Conjecture de Popovych

Cette conjecture est une version avec des hypothèses plus fortes de la conjecture d'Agrawal (dont on pense qu'elle est fausse).

Conjecture  : Soit r un nombre premier qui ne divise pas n.
Si
(X-1)^n=X^n-1 ~\text{ et }~ (X+2)^n=X^n+2 ~\text{ dans }~ \mathbb{Z}_n[X]/(X^r-1) 
alors
n \text{ est premier ou } n^2 \equiv 1 ~[r]


Références : http://eprint.iacr.org/2009/008.pdf


Si l'une de ces conjectures est vraie, la complexité de l'algorithme AKS pourrait être réduite d'un O((log n)6) à un O((log n)3).
« Modifié: 31 March 2015 à 16:02 par Matt11 »


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #7 le: 10 September 2014 à 23:50
Primegrid

Il existe deux types d'applications sur Primegrid :

  • « Sieve » : ce sont des applications utilisant un crible c'est-à-dire utilisant la liste des nombres premiers déjà connues pour en trouver d'autre. Plus précisément le but de ces applications est d'éliminer les nombres non premiers d'une liste de nombres. L'exemple le plus simple et le plus connu (mais pas utilisé dans Primegrid) est le crible d'Ératosthène. Ces applications sont adaptées au parallélisme et donc au GPU.
  • « LLR » ou autre : ces applications utilisent un test de primalité pour déterminer si un nombre donné est premier ou non. « LLR » (acronyme de Lucas–Lehmer–Riesel test) est le nom d'un test de primalité déterministe pour les nombres de la forme N = k⋅2n − 1, avec 2n > k. Pour plus d'information sur les différents algorithmes voir la fin du post.

Pour résumé les applications « Sieve » servent à éliminer rapidement une partie des nombres qui ne sont pas premier et les applications « LLR » permettent de tester si les nombres (restant) sont premiers ou non.

Voici une liste des différents sous-projets de Primegrid répartis par thème.

Projets en cours :

          Autour des nombres de Sophie Germain

Projet concerné :
Sophie Germain Prime Search (SGS) (début de la recherche : août 2009)

Description :

Définition  : On appelle nombre premier de Sophie Germain tout nombre premier p tel que le nombre 2p+1 soit aussi premier.

Exemple  :  5 est un nombre premier de Sophie Germain car 5 est premier et 2 x 5 + 1 = 11 est aussi premier.

Conjecture  : Il existe une infinité de nombres premiers de Sophie Germain.

Ces nombres ont été introduit vers 1825 par la mathématicienne Marie-Sophie Germain qui démontra le dernier théorème de Fermat pour de tels nombres premiers.
Aujourd'hui les nombres premiers de Sophie Germain sont utilisés en cryptographie et jouent un rôle important dans le test de primalité AKS. De plus ils vérifient la propriété suivante.

Proposition  : Si p est un nombre premier de Sophie Germain qui peut s'écrire de la forme p=4k-1 avec k > 1 alors le nombre 2p+1 divise le nombre de Mersenne Mp = 2p - 1.

L'application SGS cherche des nombres premiers p de la forme  k⋅2n - 1 avec (en octobre 2014) n = 1 290 000 et k aux alentours de 1,5x1012 ce qui donne des nombres à environ 380 000 chiffres. Si p est premier, le programme cherchera si les nombres p+2 = k⋅2n + 1,  (p-1)/2 = k⋅2n-1 - 1 et  2p+1 = k⋅2n+1 - 1 sont premiers. A noter que cette application cherche aussi des nombres premiers jumeaux c'est-à-dire des nombres premiers p tel que p+2 soit aussi premier (cf. Twin Prime Search).

État des résultats (2014)  : Le plus grand nombre premier de Sophie Germain est 18 543 637 900 515 x 2666 667 - 1. Il a été trouvé en avril 2012 et possède un peu plus de 200 000 chiffres.
Voici la liste des plus grands nombres premiers de Sophie Germain : http://primes.utm.edu/top20/page.php?sort=SophieGermain
Référence : http://www.primegrid.com/forum_thread.php?id=1450


Biographie : Marie-Sophie Germain (1776 – 1831) est une est une mathématicienne et philosophe française. Elle est connue pour le théorème d’arithmétique qui porte son nom, pour ses échanges avec le mathématicien Carl Friedrich Gauss et pour ses travaux sur l’élasticité des corps.


          Autour des nombres de Proth

Projet concerné :
Proth Prime Search (PPS et PPSE et MEGA et PPS-Sieve) (début de la recherche : février 2008)
321 Prime Search (321 et 321-Sieve) (début de la recherche : juin 2008)

Description :

Définition  : On appelle nombre premier de Proth tout nombre premier de la forme k⋅2n + 1 avec k un nombre impair vérifiant k < 2n.

Exemples  :  3 = 21 + 1 ; 5 = 22 + 1 et 41 = 5 x 23 + 1 sont des nombres premiers de Proth.

L'application PPS s'intéresse aux nombres premiers de Proth avec k < 1200 et n aux alentours de 2 100 000 ce qui donne des nombres à environ 650 000 chiffres.
L'application PPSE s'intéresse aux nombres premiers de Proth avec 1 200 < k < 10 000 et n aux alentours de 1 300 000 ce qui donne des nombres à environ 400 000 chiffres.
L'application MEGA s'intéresse aux nombres premiers de Proth avec 100 < k < 300 et 3 322 000 < n < 3 600 000 ce qui donne des nombres à plus de 1 000 000 chiffres.
L'application 321 s'intéresse aux nombres premiers de Proth de la forme 3 x 2n + 1 et aux nombres premiers de la forme 3 x 2n - 1 avec 11 000 000 < n < 25 000 000 ce qui donne des nombres à plus de 3 400 000 chiffres.

État des résultats (2014)  : Le plus grand nombre premier de Proth connu en septembre 2014 est 19 249 x 213 018 586 + 1. Il a été découvert en mai 2007 et possède un peu plus de 3,9 millions de chiffres.
Le plus grand nombre premier trouvé par le sous-projet 321 Prime Search  est 3 x 210 829 346 + 1. Il a été découvert en janvier 2014 et possède un peu plus de 3,2 millions de chiffres.
Voici la liste des plus grands nombres premiers de Proth : http://primes.utm.edu/top20/page.php?id=66
Référence : http://www.primegrid.com/forum_thread.php?id=2665


Biographie : François Proth (1852 – 1879) est un mathématicien autodidacte français (aussi agriculteur), qui a vécu près de Verdun. Il s'intéressa surtout à l'étude des nombres premiers et établit le théorème de Proth.


          Autour des nombres de Cullen

Projet concerné :
Cullen prime search (CUL) (début de la recherche : août 2007)

Description :

Définition  : On appelle nombre premier de Cullen tout nombre premier de la forme n⋅2n + 1.

Exemple  :  3 est un nombre premier de Cullen car 3 est premier et 3 = 1 x 21 + 1. Le deuxième nombre de Cullen est 141 x 2141 + 1.

Remarques  : Il a été montré en 1976 qu'il y avait très peu de nombres premiers de Cullen.

Conjecture  : Il existe une infinité de nombres premiers de Cullen. De plus on ne sait pas s'il existe un nombre premier p tel que p⋅2p + 1 soit aussi premier.

L'application CUL cherche des nombres premiers de Cullen avec n aux alentours de 12 500 000 ce qui donne des nombres à plus de 3 750 000 chiffres.

État des résultats (2014)  : Le plus grand nombre premier de Cullen est 6 679 881 × 26 679 881 + 1. Il a été trouvé en août 2009 et possède un peu plus de 2 000 000 de chiffres.
Voici la liste des plus grands nombres premiers de Cullen : http://primes.utm.edu/top20/page.php?id=6
Référence : https://en.wikipedia.org/wiki/Cullen_number


Biographie : James Cullen (1867 – 1933)  est un prêtre jésuite irlandais et mathématicien de renom. Il a introduit en 1905 les nombres de Cullen.


          Autour des nombres de Woodall

Projet concerné :
Woodall prime search (WOO) (début de la recherche : juillet 2007)

Description :

Définition  : On appelle nombre premier de Woodall tout nombre premier de la forme n⋅2n - 1.

Exemple  :  7 est un nombre premier de Woodall car 7 est premier et 7 = 2 x 22 - 1.

Remarques  : Comme pour les nombres de Cullen, il y a très peu de nombres premiers de Woodall. Cependant il y a plus de "petits" exemples de nombre de Woodall (1, 7, 23, 63, 159, 383, 895, …).

Conjecture  : Il existe une infinité de nombres premiers de Woodall.

L'application WOO cherche des nombres premiers de Woodall avec n aux alentours de 13 000 000 ce qui donne des nombres à plus de 4 000 000 chiffres.

État des résultats (2014)  : Le plus grand nombre premier de Woodall est 3 752 948 × 23 752 948 − 1. Il a été trouvé en décembre 2007 et possède un peu plus de 1 000 000 de chiffres.
Voici la liste des plus grands nombres premiers de Woodall : http://primes.utm.edu/top20/page.php?sort=Woodall
Référence : https://fr.wikipedia.org/wiki/Nombre_de_Woodall


Biographie : Herbert J. Woodall   est un mathématicien britannique. Il a introduit en 1917 les nombres de Woodall.


          Autour des nombres de Sierpiński

Projets concernés :
Seventeen or Bust (SOB) (début de la recherche : janvier 2010)
Prime Sierpinski Problem (PSP) (début de la recherche : juillet 2008)
Extended Sierpinski Problem (ESP et ESP-Sieve) (début de la recherche : mars 2010)

Description :

Définition  : On dit que k est un nombre de Sierpiński s'il est impair et si pour tout entier naturel n, le nombre k⋅2n + 1 n'est pas premier.

Exemples  : 3 n'est pas un nombre de Sierpiński car pour n = 2 on a 3 x 22 +  1 = 13 qui est un nombre premier.
En 1962, John Selfridge démontre que 78 557 est un nombre de Sierpiński. Pour cela il démontre que pour tout entier naturel n, le nombre 78557 x 2n + 1 est divisible par (au moins) l'un de ces nombres : 3, 5, 7, 13, 19, 37, 73.

En 1960, Wacław Sierpiński montre la proposition suivante
Proposition  : Il existe une infinité de nombre de Sierpiński.

Résoudre le problème de Sierpiński consiste à trouver le plus petit nombre de Sierpiński.

Conjecture  : 78 557 est le plus petit nombre de Sierpiński.

On sait que 78 557 est bien un nombre de Sierpiński. Il reste donc à montrer que pour tout entier impair k inférieur à 78 556, on peut trouver un nombre premier de la forme  k⋅2n + 1.

État des résultats (2014)  : Pour montrer la conjecture il ne reste plus qu'à montrer que six nombres ne sont pas des nombres de Sierpiński.
En voici la liste : 10223 ; 21181 ; 22699 ; 24737 ; 55459 ; 67607.

L'application Seventeen or Bust (SOB) a pour but de résoudre le le problème de Sierpiński en trouvant un nombre premier de la forme k⋅2n + 1 pour chaque k dans la liste de nombres précédente. Ce projet s'appelle « Seventeen or Bust » car au lancement (en 2002) il fallait montrer que 17 nombres n'étaient pas des nombres de Sierpiński. Depuis le projet a réussi à en exclure 11 d'entre eux (il devrait aujourd'hui se nommer « Six or Bust » mais le nom original a été gardé). Le dernier nombre premier trouvé par ce projet est 33 661 x 27 031 232 + 1, qui a été découvert en octobre 2007 et il possède plus de 2 000 000 de chiffres.
Référence : http://www.primegrid.com/forum_thread.php?id=1647

Résoudre le problème des nombres premiers de Sierpiński consiste à trouver le plus petit nombre de Sierpiński qui est premier.

Conjecture  : 271 129 est le plus petit nombre premier de Sierpiński.

On sait que 271 129 est bien un nombre premier de Sierpiński. Il reste donc à vérifier que c'est le plus petit.

État des résultats (2014)  : Pour montrer la conjecture il ne reste plus qu'à montrer que onze nombres ne sont pas des nombres premiers de Sierpiński.
En voici la liste : 10223 ; 22699 ; 67607 ; 79309 ; 79817 ; 152267 ; 156511 ; 168451 ; 222113 ; 225931 ; 237019.

L'application Prime Sierpinski Problem (PSP)  a pour but de résoudre le problème des nombres premiers de Sierpiński en trouvant un nombre premier de la forme k⋅2n + 1 pour chaque k dans la liste de nombres précédente. Depuis le début de la recherche, le projet a réussi à montrer que 18 nombres n'était pas des nombres premiers de Sierpiński. Le dernier nombre premier trouvé par ce projet est 90 527 x 29 162 167 + 1, qui a été découvert en juin 2010 et il possède un peu plus de 2 750 000 chiffres.
Référence : http://www.mersenneforum.org/showthread.php?t=2665

Résoudre le problème étendu de Sierpiński consiste à trouver le deuxième plus petit nombre de Sierpiński.

Conjecture  : 271 129 est le deuxième plus petit nombre de Sierpiński.

En supposant les deux premières conjectures établies, cela n’entraîne pas que 271 129 soit le deuxième plus petit nombre de Sierpiński. C'est pour cela que ce problème étend la recherche des nombres de Sierpiński entre 78 557 et 271 129. De plus comme le problème des nombres premiers de Sierpiński s'intéresse déjà aux nombres premiers de Sierpiński inférieurs à 271 129, ce problème s'intéresse exclusivement aux nombres non premiers entre 78 557 et 271 129 pouvant être de Sierpiński.

État des résultats (2014)  : Pour montrer la conjecture il ne reste plus qu'à montrer que douze nombres ne sont pas des nombres de Sierpiński.
En voici la liste : 91549 ; 99739 ; 131179 ; 161041 ; 163187 ; 193997 ; 200749 ; 202705 ; 209611 ; 227723 ; 229673 ; 238411.

L'application Extended Sierpinski Problem (ESP et ESP-Sieve)  a pour but de résoudre le problème étendu de Sierpiński en trouvant un nombre premier de la forme k⋅2n + 1 pour chaque k dans la liste de nombres précédente. Depuis le début de la recherche, le projet a réussi à montrer que 19 nombres n'était pas des nombres premiers de Sierpiński. Le dernier nombre premier trouvé par ce projet est 211 195 x 23 224 974 + 1, qui a été découvert en mars 2013 et il possède plus de 950 000 chiffres.
Référence : http://www.primegrid.com/forum_thread.php?id=5758


Biographie : Wacław Franciszek Sierpiński (Varsovie, 1882 - Varsovie, 1969) est un mathématicien polonais, connu pour ses contributions à la théorie des ensembles, la théorie des nombres, la théorie des fonctions et la topologie.


          Autour des nombres de Riesel

Projets concernés :
The Riesel Problem (TRP et TRP-Sieve) (début de la recherche : mars 2010)

Description :

Le problème de Riesel est très similaire au problème de Sierpiński mais au lieu de considérer les nombre de la forme k⋅2n + 1, on considère ici les nombres de la forme k⋅2n - 1.

Définition  : On dit que k est un nombre de Riesel s'il est impair et si pour tout entier naturel n, le nombre k⋅2n - 1 n'est pas premier.

Exemples  : 5 n'est pas un nombre de Riesel car pour n = 4 on a 5 x 24 -  1 = 79 qui est un nombre premier.
En 1956, Hans Riesel démontre que 509 203 est un nombre de Riesel. Il démontre par la même occasion que pour tout entier naturel q, le nombre 509 203 + 11 184 810 x q est un nombre de Riesel. On a ainsi la proposition suivante.

Proposition  : Il existe une infinité de nombre de Sierpiński.

Résoudre le problème de Riesel consiste à trouver le plus petit nombre de Riesel.

Conjecture  : 509 203 est le plus petit nombre de Riesel.

On sait que 509 203 est bien un nombre de Riesel. Il reste donc à montrer que pour tout entier impair k inférieur à 509 203, on peut trouver un nombre premier de la forme  k⋅2n - 1.

État des résultats (2014)  : Pour montrer la conjecture il ne reste plus qu'à montrer que 50 nombres ne sont pas des nombres de Riesel.
En voici la liste : 2293 ; 9221 ; 23669 ; 31859 ; 38473 ; 46663 ; 67117 ; 74699 ; 81041 ; 93839 ; 97139 ; 107347 ; 121889 ; 129007 ; 143047 ; 146561 ; 161669 ; 192971 ; 206039 ; 206231 ; 215443 ; 226153 ; 234343 ; 245561 ; 250027 ; 273809 ; 315929 ; 319511 ; 324011 ; 325123 ; 327671 ; 336839 ; 342847 ; 344759 ; 362609 ; 363343 ; 364903 ; 365159 ; 368411 ; 371893 ; 384539 ; 386801 ; 397027 ; 409753 ; 444637 ; 470173 ; 474491 ; 477583 ; 485557 ; 494743.

Les applications TRP et TRP-Sieve ont pour but de résoudre le le problème de Riesel en trouvant un nombre premier de la forme k⋅2n - 1 pour chaque k dans la liste de nombres précédente. Depuis son lancement ce projet a réussi à montrer que 14 nombres n'étaient pas de Riesel. Le dernier nombre premier trouvé par ce projet est 502 573 x 27 181 987 - 1, qui a été découvert en octobre 2014 et il possède plus de 2 150 000 de chiffres.
Référence : http://www.primegrid.com/forum_thread.php?id=1731

Contrairement au problème des nombres premiers de Sierpiński, il n'y a pas de problème des nombres premiers de Riesel puisque 509 203 est premier.


Biographie : Hans Riesel ( Stockholm, 1929 - ) est un mathématicien suédois. Il est célèbre pour avoir trouvé en 1957 le dix-huitième nombre premier de Mersenne, demeuré jusqu'en 1961 le plus grand nombre premier connu. Il a également étudié et donné leur nom aux nombres de Riesel. Cependant les nombres de Sierpiński ont reçu plus d'attention que les nombres de Riesel, peut-être parce que l'article de Riesel était en suédois.
« Modifié: 11 December 2016 à 00:56 par Matt11 »


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #8 le: 10 September 2014 à 23:50
Primegrid (suite)

          Autour des nombres de Sierpiński et de Riesel en base 5

Projets concernés :
Sierpinski/Riesel Base 5 Problem (SR5) (début de la recherche : juin 2013)

Description :

Ce projet est une extension en base 5 des problèmes de Sierpiński et de Riesel. C'est-à-dire qu'au lieu de s'intéresser aux nombres de la forme k⋅2n + 1 et k⋅2n - 1, on s'intéresse ici aux nombres de la forme k⋅5n + 1 et k⋅5n - 1. Le but est toujours de déterminer le plus petit nombre de Sierpiński (resp. Riesel) en base 5.

Définition  : On dit que k est un nombre de Sierpiński (resp. Riesel) en base 5 s'il est impair et si pour tout entier naturel n, le nombre k⋅5n + 1 (resp. k⋅5n - 1) n'est pas premier.

Robert Smith a présenté l'idée des nombres de Sierpiński/Riesel en base 5 le 17 September 2004, dans le groupe primeform de yahoo. Il proposa que k = 346 802 est le plus petit nombre de Riesel en base 5. Peu après, Guido Smetrijns proposa que k = 159 986 est le plus petit nombre de Sierpiński en base 5.

État des résultats (2014)  :

Pour les nombres de Sierpiński en base 5 : pour montrer que 159 986 est le plus petit nombre de Sierpiński en base 5 il reste à vérifier que 37 nombres ne sont pas des nombres de Sierpiński en base 5.
En voici la liste : 6436 ; 7528 ; 10918 ; 26798 ; 29914 ; 31712 ; 36412 ; 41738 ; 44348 ; 44738 ; 45748 ; 51208 ; 58642 ; 60394 ; 62698 ; 64258 ; 67612 ; 67748 ; 71492 ; 74632 ; 76724 ; 77072 ; 81556 ; 83936 ; 84284 ; 90056 ; 92158 ; 92906 ; 93484 ; 105464 ; 118568 ; 126134 ; 138514 ; 139196 ; 144052 ; 152588 ; 154222.

Pour les nombres de Riesel en base 5 : pour montrer que 346 802 est le plus petit nombre de Riesel en base 5 il reste à vérifier que 79 nombres ne sont pas des nombres de Riesel en base 5.
En voici la liste : 3622 ; 4906 ; 23906 ; 26222 ; 35248 ; 35816 ; 52922 ; 53546 ; 63838 ; 64598 ; 66916 ; 68132 ; 71146 ; 76354 ; 81134 ; 88444 ; 92936 ; 100186 ; 102818 ; 102952 ; 109238 ; 109838 ; 109862 ; 127174 ; 131848 ; 134266 ; 136804 ; 143632 ; 145462 ; 145484 ; 146264 ; 146756 ; 147844 ; 151042 ; 152428 ; 154844 ; 159388 ; 164852 ; 170386 ; 170908 ; 171362 ; 177742 ; 180062 ; 182398 ; 187916 ; 189766 ; 190334 ; 194368 ; 195872 ; 201778 ; 204394 ; 206894 ; 207494 ; 213988 ; 231674 ; 238694 ; 239062 ; 239342 ; 246238 ; 248546 ; 259072 ; 265702 ; 267298 ; 271162 ; 273662 ; 285598 ; 285728 ; 296024 ; 298442 ; 301562 ; 304004 ; 306398 ; 313126 ; 318278 ; 322498 ; ; 325922 ; 327926 ; 335414 ; 338866.

L'application SR5 a pour but de résoudre le les problèmes de Sierpiński/Riesel en base 5. Le dernier nombre premier trouvé par ce projet est 109 208 · 51 816 285 + 1, qui a été découvert en octobre 2014 et il possède plus de 1 250 000 de chiffres.
Référence : http://www.primegrid.com/forum_thread.php?id=5087


          Autour des nombres premiers de Fermat généralisés

Projets concernés :
Generalized Fermat Prime Search (GFN-Short et GFN-WR) (début de la recherche : janvier 2012)

Description :

Avant de parler de nombres de Fermat généralisés, définissons tout d'abord les nombres de Fermat.

Définition  : On appelle nombre de Fermat tout entier naturel qui peut s'écrire sous la forme 22n + 1. On note alors Fn = 22n + 1 (on pourra aussi noté ce nombre F(2,n)).

Exemples  : Les cinq premiers nombre de Fermat sont F0 = 3 ; F1 = 5 ; F2 = 17 ; F3 = 257 ; F4 = 65537.

Ces nombres ont été introduits par le mathématicien français Pierre de Fermat au XVIIème siècle. A l'époque, les calculs se faisant à la main, il n'a pas pu déterminer que le nombre F5 n'est pas premier et il conjectura que tous les nombres de Fermat sont premiers. Cette conjecture se révéla fausse lorsqu'en 1732 (soit environ un siècle après), le mathématicien suisse Leonhard Euler démontra que F5 = 4 294 967 297 n'est pas premier. Aujourd'hui on a démontré que tous les nombres Fn pour 4 < n < 33 ne sont pas premiers et on ne connaît aucun autre nombre de Fermat qui soit premier hormis les cinq premiers exemples.

Voici aujourd'hui différentes questions non résolues que se posent les mathématiciens sur les nombres de Fermat :
  • Les nombres de Fermat sont-ils tous non premier à partir de n = 5 ?
  • Y a-t-il une infinité de nombres de Fermat qui soient premiers ?
  • Y a-t-il une infinité de nombres de Fermat qui ne soient pas premiers ?

Pour finir sur les nombres de Fermat (non généralisés) voici une propriété qui motive l'étude des nombres premier de Proth dans la recherche de diviseur des nombres de Fermat.

Proposition  : Tout facteur (diviseur) premier du nombre de Fermat Fn est de la forme k⋅2m + 1 où k est un entier impair et m ≥ n + 2.

État des résultats (2014) : En juillet 2014 l'application MEGA du projet Proth Prime Search détermina que 193 x 23 329 782 + 1 divise F3 329 780. Le nombre F3 329 780 est donc le plus grand nombre de Fermat connu (en octobre 2014) qui ne soit pas premier.

Venons-en maintenant aux nombres de Fermat généralisés.

Définition  : On appelle nombre de Fermat généralisé tout entier naturel qui peut s'écrire sous la forme b2n + 1 avec b un entier supérieur à 2. On note alors F(b,n) = b2n + 1.

Remarques  : Lorsque b=2 on retrouve les nombres de Fermat Fn.

Proposition  : Si F(b,n) est premier alors b est pair.

Ces dernières années, les nombres de Fermat généralisés ont pris une place importante dans la recherche de grands nombres premiers en raison de la facilité à prouver leur primalité. Ainsi bon nombre des plus grands nombres premiers connus aujourd'hui sont des nombres premiers de Fermat généralisés.

État des résultats (2014)  : Le plus grand nombre premier de Fermat généralisé est F(475 856 , 19) = 475 856524 288 + 1. Il a été trouvé en août 2012 et possède un peu moins de 3 000 000 de chiffres.
Voici la liste des plus grands nombres premiers de Fermat généralisé : http://primes.utm.edu/top20/page.php?id=12

L'application GFN-Short cherche des nombres premiers de la forme F(b,n) avec 480 000 < b < 510 000 et n = 20 ce qui donne des nombres à environ 6 000 000 chiffres.
L'application GFN-WR cherche des nombres premiers de la forme F(b,n) avec 28 500 < b < 33 500 et n = 22 ce qui donne des nombres à environ 18 500 000 chiffres. L'application GFN-WR a donc pour objectif de trouver le plus grand nombre premier connu (qui a actuellement en octobre 2014 un peu moins de 17 500 000 chiffres).
Référence : http://www.primegrid.com/forum_thread.php?id=3980


Biographie : Pierre de Fermat (1601 – 1665)  est un magistrat, polymathe et surtout mathématicien français, surnommé « le prince des amateurs ». Il est aussi poète, habile latiniste et helléniste, et s'est intéressé aux sciences physiques ; on lui doit notamment le principe de Fermat en optique.


Projets terminés :

AP26 Search (AP26) (début de la recherche : décembre 2008 / fin de la recherche : avril 2010)
Cette application avait pour but de déterminer une progression arithmétique de nombres premiers de longueur 26.

Définition  : On appelle progression arithmétique de nombres premiers de longueur k, une suite de k nombres premiers telle que la différence de deux termes consécutifs de cette suite est constante. Autrement dit la suite u1, u2, ... uk est progression arithmétique de nombres premiers si il existe un entier naturel r tel que pour tout entier n compris entre 1 et k-1 on a un+1 - un = r et un est premier.

Exemples :
3, 7, 11 est une progression arithmétique de nombres premiers de longueur 3 (et de raison r=4).
199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089  est une progression arithmétique de nombres premiers de longueur 10 (et de raison r=210).

Théorème de Green-Tao  : Pour tout entier naturel k, il existe une progression arithmétique de nombres premiers de longueur k.
On peut donc en théorie trouver une progression arithmétique de nombres premiers de longueur arbitraire.

État des résultats  : Ce projet a trouvé une progression arithmétique de nombres premiers de longueur 26 :
43 142 746 595 714 191+ 23 681 770*23*n pour n allant de 0 à 25


Primegen (début de la recherche : mars 2006 / fin de la recherche : février 2008)
Ce projet avait pour but d'établir une liste exhaustive des nombres premier à partir de 1.


Twin Prime Search (TPS) (début de la recherche : novembre 2006 / fin de la recherche : juillet 2009)
Ce projet avait pour but de chercher des nombres premiers jumeaux. Il a été remplacer par le projet Sophie Germain Prime Search.

Définition  : On dit que deux nombres premiers sont jumeaux s'ils ont un écart de 2 (leur différence vaut 2).

Exemple : 3 et 5 ou 11 et 13 sont des nombres premiers jumeaux.

Conjecture  : Il existe une infinité de nombres premiers jumeaux.

État des résultats  : Actuellement (octobre 2014) le plus grand nombre premier jumeau est 3 756 801 695 685 x 2666 669 ± 1. Il possède 200 700 chiffres et a été trouvé en décembre 2011 par ce projet.




Annexes :

          Notion du nombre de chiffres et récapitulatif des records de chaque application

Pour mesurer la taille des nombres premiers, on utilise souvent le nombre de chiffres (sous-entendu en base 10).

Définition  : Pour tout entier naturel non nul n, on définit le nombre de chiffres de n comme étant l'unique entier k vérifiant 10k-1 ≤  n < 10k.

Exemples : 12 a 2 chiffres, 100 a 3 chiffres.

On peut très facilement calculer le nombre de chiffres d'un grand nombre grâce à la proposition suivante.
Proposition  : Le nombre de chiffres d'un entier naturel non nul n est égal à
 
\text{E} \left( \frac{\ln(n)}{\ln(10)} \right) + 1

avec ln la fonction logarithme népérien et E la fonction partie entière.

Voici la liste des records de chaque application ou en lien avec les nombres premiers.

  • Plus grand nombre premier connu (en 2014) : 257 885 161 - 1 qui possède 17 425 170 chiffres
  • Plus grand nombre premier connu (en 1980) : 244 497 - 1 qui possède 13 395  chiffres
  • Plus grand nombre premier connu (en 1951) : 180 x (2127 - 1)2 + 1 qui possède 79 chiffres
  • Plus grande liste exhaustive de nombres premiers (en 2014) : tous les nombre premier à moins de 17 chiffres
  • Sophie Germain Prime Search : 18 543 637 900 515 x 2666 667 - 1 qui possède 200 701 chiffres
  • Proth Prime Search : 7 x 25 775 996 + 1 qui possède 1 738 749 chiffres
  • 321 Prime Search : 3 x 210 829 346 + 1 qui possède 3 259 959 chiffres
  • Cullen prime search : 6 679 881 x 26 679 881 + 1 qui possède 2 010 852 chiffres
  • Woodall prime search : 3 752 948 x 23 752 948 - 1 qui possède 1 129 757 chiffres
  • Seventeen or Bust : 19 249 X 213 018 586 + 1 qui possède 3 918 990 chiffres
  • Prime Sierpinski Problem : 90 527 x 29 162 167 + 1 qui possède 2 758 093 chiffres
  • Extended Sierpinski Problem : 211 195 x 23 224 974 + 1 qui possède 970 820 chiffres
  • The Riesel Problem : 502 573 x 27 181 987 - 1 qui possède 2 162 000 chiffres
  • Sierpinski/Riesel Base 5 Problem : 109 208 x 51 816 285 + 1 qui possède 1 269 534 chiffres
  • Generalized Fermat Prime Search : 475856524288 + 1 qui possède 2 976 633 chiffres
  • Twin Prime Search : 3 756 801 695 685 x 2666 669 ± 1  qui possède 200 700 chiffres

A titre de comparaison, on utilise en cryptographie (dans RSA-2048 par exemple) des nombres premiers avec environ 300 chiffres.
Référence : http://primes.utm.edu

          Probabilité de trouver un nombre premier

Après leur découverte, voici deux grandes questions portant sur les nombres premiers que les mathématiciens se sont posées :
  • Y en a-t-il beaucoup / sont-ils rares ?
  • Comment sont-ils répartis ?

En 1896 le mathématicien français Jacques Hadamard et le mathématicien belge Charles-Jean de La Vallée Poussin démontrent indépendamment le Théorème des nombres premiers qui répond en partie à ces deux questions.

Théorème des nombres premiers  : Pour tout nombre réel x, on note π(x) le nombre de nombres premiers inférieur à x (par exemple π(12) = 5 et π(19/3) = 3).
On a alors l'équivalent suivant :

\pi(x)~ \underset{x \to \infty}{\sim} ~\frac{x}{\ln(x)}

Concrètement ce théorème nous donne la quantité de nombres premiers quand on va vers l’infini. Alors y en a-t-il beaucoup ?
La réponse est plutôt oui ! Par exemple il y a énormément plus de nombres premiers que de carrés parfaits.

De plus le théorème précédent nous permet de calculer une estimation de la probabilité de trouver un nombre premier.

Application au calcul de probabilité  : Si on appelle P(x) la probabilité de trouver un nombre premier en piochant un entier entre 0 et x de manière aléatoire (uniforme),
on a P(x) = π(x)/x ≈ 1/ln(x).

Appliquons ce résultat :
On a (d'après le théorème) environ 1 chance sur 7 de trouver un nombre premier entre 1 et 1 000 (en réalité c'est plutôt 1 chance sur 6)
On a (d'après le théorème) environ 1 chance sur 13.8 de trouver un nombre premier entre 1 et 1 000 000 (en réalité c'est plutôt 1 chance sur 12.7)
On a (d'après le théorème) environ 1 chance sur 53 de trouver un nombre premier à moins de 23 chiffres (en réalité c'est plutôt 1 chance sur 52)
Pour les petits exemples voir ici

Maintenant pour les grands nombres premiers (ce qui nous intéresse  :hyperbon:) voici quelques exemples :

On a environ 1 chance sur 4 605 000 de trouver un nombre premier à environ 2 000 000 de chiffres.
On a environ 1 chance sur 11 513 000 de trouver un nombre premier à environ 5 000 000 de chiffres (soit pratiquement autant de chance que de gagner au loto).
On a environ 1 chance sur 45 000 000 de trouver le plus grand nombre premier (connu).


          Les algorithmes de primalité

On appelle algorithme de primalité un algorithme qui détermine si un nombre donné est premier ou non. Il en existe deux types : les déterministes et les probabilistes.
Les algorithmes de primalité déterministes renvoient tout simplement si le nombre est premier ou non de façon certaine.
Les algorithmes de primalité probabilistes sont plus rapide que les déterministes mais ils renvoient :
  • Soit que le nombre testé est de façon certaine non premier
  • Soit qu'il y a une probabilité (en général grande) que le nombre testé soit premier. Dans ce cas (assez rare) on dit que le nombre est pseudo-premier et il faut utiliser un algorithme déterministe pour être certain que le nombre soit premier.

Primegrid utilise trois types d'applications :
  • les applications « Sieve » utilisent des algorithmes de criblage qui ont pour but d'exclure rapidement une partie des nombres non premiers d'une liste de nombres
  • l'application GFN teste la primalité des nombres de Fermat généralisé
  • l'application LRR teste la primalité des nombres de la forme k⋅bn ± 1

Contrairement à ce que laisse penser son nom, l'application LLR n'utilise pas que l'algorithme LLR. Voici les différents algorithmes utilisés par cette application :

Pour les nombres en base 2 :

Pour les nombres en base quelconque :
  • Les nombres de la forme k⋅bn + 1 sont testés par l'algorithme N-1 de Pocklington.
  • Les nombres de la forme k⋅bn - 1 sont testés par l'algorithme N+1 de Morrison.

Pour plus d'information sur l'application LLR voir : http://www.mersenneforum.org/showthread.php?t=19167
« Modifié: 28 October 2014 à 14:06 par Matt11 »


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #9 le: 10 September 2014 à 23:50
[RESERVE]


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #10 le: 10 September 2014 à 23:50
[RESERVE]


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #11 le: 10 September 2014 à 23:50
[RESERVE]


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #12 le: 10 September 2014 à 23:51
[RESERVE]


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne [AF>Libristes>Jip]Augure

  • Méchant modo
  • Boinc'eur devant l'éternel
  • ******
  • Messages: 4703
  •   
Réponse #13 le: 11 September 2014 à 00:03
hé bé... cela augure ( :D et hop plus personne ne peut la faire :D ) un sacré sujet...

bon courage,
nous avons hâte de te lire.
:jap:

>>


Hors ligne JeromeC

  • CàA
  • Boinc'eur devant l'éternel
  • *****
  • Messages: 31061
  •   
Réponse #14 le: 11 September 2014 à 01:09
Chouetos. Et vive le latex :siflotte:

A quoi bon prendre la vie au sérieux, puisque de toute façon nous n’en sortirons pas vivants ? (Alphonse Allais)



Philippe06121966

  • Invité
Réponse #15 le: 11 September 2014 à 06:48
 :plusun:

Merci Beaucoup  :jap:



Hors ligne Spica

  • Méchant modo
  • Boinc'eur devant l'éternel
  • ******
  • Messages: 5144
  •   
Réponse #16 le: 11 September 2014 à 07:30
Super Matt11, J'ai "épinglé" ton sujet, comme cela il restera tout en haut de la rubrique Mathématiques.
Bon courage, prends ton temps et puis si tu as besoin d'aide n'hésites pas

22717 SETI@home classic workunits; Redécouverte pulsar J1916+12 (le 07Nov2009) Einstein@Home.


Hors ligne CeDriCXD

  • Boinc'eur Junior
  • **
  • Messages: 179
  •   
    • E-mail
Réponse #17 le: 25 September 2014 à 12:33
Merci pour ces éclaircissements...!!!  :love:

Bonne journée à l'AF
« Modifié: 25 September 2014 à 12:42 par CeDriCXD »



Non-Governmental Organization need you !!
♥♥ For A Better World ♥♥


Hors ligne [AF>Libristes>Jip] Elgrande71

  • Gentil admin
  • Boinc'eur devant l'éternel
  • *******
  • Messages: 5107
  •   
    • [AF>Libristes] - La Mini-Team Libristes de L'Alliance Francophone sur BOINC
    • E-mail
Réponse #18 le: 25 September 2014 à 19:40
Merci Matt11  :kookoo:  :jap:

Debian - Distribution GNU/Linux de référence
Parabola GNU/Linux - Distribution GNU/Linux Libre
MX Linux
Emmabuntüs

Jabber elgrande71@chapril.org


Hors ligne [AF>Amis des Lapins] Jean-Luc

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 3390
  •   
    • Le calcul partagé en atsronomie sous BOINC
    • E-mail
Réponse #19 le: 25 September 2014 à 20:55
Merci Matt11.
C'est super clair et concis.
J'attends la suite avec impatience !
Jean-Luc



Rédacteur d'un article sur BOINC, adresse :
http://www.astrocaw.eu/?p=605
Créateur d'un site actif de recherche sur les suites aliquotes :
http://www.aliquotes.com/


Hors ligne JeromeC

  • CàA
  • Boinc'eur devant l'éternel
  • *****
  • Messages: 31061
  •   
Réponse #20 le: 15 October 2014 à 23:27
Vous pensez que c'est publiable sur le portail ? même si incomplet, on pourrait dire "à suivre"... ?

A quoi bon prendre la vie au sérieux, puisque de toute façon nous n’en sortirons pas vivants ? (Alphonse Allais)



Hors ligne PhilTheNet

  • Boinc'eur devant l'éternel
  • *****
  • Messages: 2139
  •   
    • E-mail
Réponse #21 le: 16 October 2014 à 08:00
Super bien expliqué




Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #22 le: 16 October 2014 à 10:52
En ce moment j'ai pas trop de temps donc j'ai un peu laissé de coté la description des projets de maths  :desole:
Je vais essayer de finir la description des sous-projets de Primegrid ce week-end pour que tu puisse le mettre sur le portail   :hyperbon:


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Hors ligne Matt11

  • Boinc'eur Respectable
  • ****
  • Messages: 686
  •   
Réponse #23 le: 21 October 2014 à 14:03
Voilà j'ai fini la description de Primegrid. J'ai été plutôt inspiré par le sujet (même si à la base c'est pas trop mon domaine).  :hyperbon:
J'espère être resté assez clair et compréhensible par les non initiés.

Même si j'ai relu je suis sur d'avoir laissé encore des coquilles et surtout des fautes d'orthographes (c'est pas mon fort   :/). De même il doit avoir quelques tournures de phrases malheureuses. J'en suis par avance désolé et je laisse libre quiconque voudrait modifier/améliorer ces descriptions.

Bonne lecture  :)
Prochain projet : sûrement yoyo


Ubuntu Mate 18.04  Intel core i7 6700K 4x4.0GHz 16Gb Nvidia Geforce GTX 1070


Philippe06121966

  • Invité
Réponse #24 le: 21 October 2014 à 14:05
Merci Beaucoup !  :hello: :jap: :jap: :jap: :kookoo:

Vais me plonger dans la lecture  :coffeetime:

NB Pour illustrer ce que tu dis, pendant le dernier challenge PRPNet sur WSS, nous avons trouvé 12 "near hits" sur environ 1.000.000 UT's en 12 jours, ce qui nous donnait 0.6 % de chance de trouver un "vrai nombre premier Wall-Sun-Sun"

Citer
With 12 near hits during the challenge we had a 0.6% chance of finding a true Wall-Sun-Sun prime.

=> 1 chance sur environ 166.666.666 (comme pour l'Euromillion ;)) => plus "que" 165.666.666 UT à calculer pour avoir 1 chance de trouver un résultat positif  :bimo:
« Modifié: 21 October 2014 à 14:22 par Phil1966 »