NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 27/09/2016

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Nombres PREMIERS

 

Débutants

Nombres

Premiers

Formules

 

Glossaire

Nombres

Premiers

 

 

INDEX

 

Nombres premiers – Formules

 

Formules

n² + n + 41

Tables

Efficacité

Séquence 31, 24

a . n² + b

 

Sommaire de cette page

>>> Point de la situation

>>> Objet de la recherche

>>> Formules vedettes

>>> Formules générales

>>> Polynômes quadratiques

>>> Formule de récurrence

>>> Formule de Mills

>>> Polynômes pour composés

>>> Analyse d'une formule

 

 

 

 

 

 

FORMULES produisant des

nombres premiers 

 

*    Un rêve !

*    Euler et Ulam ont trouvé des formules (des polynômes) donnant certains nombres premiers.

*    Aucune formule simple et surtout pratique ne donne que des nombres premiers.

*    On a bien p² = 24k + 1 (le carré de tout nombre premier supérieur à 3 est de la forme 24k + 1). Mais, hélas de nombreux nombres de cette forme ne sont pas premiers.

Anglais: Formula for primes

 

 

 

POINT de la situation

 

En 1772, Euler trouve un polynôme très productif: n(n+1) + 41.

En 1798, Legendre propose n(n-1) + 41.

 

Legendre montre qu'une fonction algébrique rationnelle ne peut pas produire que des nombres premiers.

 

En 1752, Goldbach prouve qu'un polynôme à coefficients entiers ne peut pas donner que des premiers pour toutes les valeurs entières.

 

Il existe un polynôme à coefficients entiers et à dix variables qui ne produit que des nombres premiers, mais il s'agit en fait d'un jeu d'équations diophantiennes. Il en existe un autre de degré 25 avec 26 variables qui ne produit que des premiers.

 

Le record est détenu par François Dress et Bernard Landreau (2012) avec 58 premiers successifs pour un polynôme du 6e degré.

Certains polynômes ont été redécouverts dans la compétition Internet : Al Zimmermann’s Programming Contest, Prime Generating Polynomials, organisée par Ed Pegg Jr en juillet 2006.

 

 

 

Objet de la recherche

 

Les nombres premiers sont sous de la forme en 6n  1. Mais hélas tous les nombres de cette forme ne sont pas premiers.

Voir La fameuse barre magique

 

On connait la propension des mathématiciens à caractériser divers types de premiers. Les nombres premiers de Mersenne sont les plus célèbres (P = 2p – 1), car c'est sous cette forme que l'on connait les plus grands nombres premiers.

 

 

Concernant la production polynomiale, les mathématiciens se posent deux types de problèmes:

*    le problème n sur n: le polynôme doit délivrer n premiers successifs pour une séquence de n valeurs consécutives de la variable. Record en 2012:

*    n = 45 avec des polynômes quadratiques (2e degré).

*    n = 58 avec des polynômes de degré supérieur à 2.

*    le problème k sur n: le polynôme produit k premiers pour une séquence de n valeurs consécutives de la variable.

 

 

 

 FORMULES vedettes – Polynômes quadratiques

 

 QUATRE FORMULES donnant une grande quantité de nombres premiers

 

 

La célèbre formule trouvée par Euler en 1772 (n² + n + 41), pourtant très simple, produit une extraordinaire quantité de nombres premiers dont les 40 premiers de la liste.

 

Voir Tables des premiers selon ces formules / Spirale d'Ulam 

 

 

 

FORMULES  Générales

 

Quelques expressions qui caractérisent:

*    tous les nombres premiers (et, hélas, aussi des composés), ou

*    certains types de nombres premiers.

 

Formules

Jusqu'à

Remarque

4n + 1 ou 4n – 1

n > 2

*   Propriétés générales

6n + 1 ou 6n – 1

n > 3

*   Propriétés générales

30n +

{1, 7, 11, 13, 23, 29)

n > 5

*   Propriétés générales

(2n – 2) / n

n < 5

*   Chine

(22)n + 1

n < 4

*   Nombre de Fermat

k . 2n  1

*   Premiers de Proth

n . 2n  1

*   Premiers de Woodall

n . 2n  + 1

*   Premiers de Cullen

n . bn  + 1  (n+2 >b)

*   Cullen généralisés

Mp = 2p – 1

avec p premier

*   Nombre de Mersenne

Polynômes

Voir ci-dessous

 

 

  

POLYNÔMES QUADRATIQUES

 

Polynômes du deuxième degré qui produisent des nombres premiers successifs. Ex: pour n de 0 jusqu'à 13, le polynôme 4n² + 4n + 59 produits 14 premiers distincts. Le graphe de ces polynômes est une parabole, alors on peut retrouver la même valeur pour deux valeurs différentes de n.



Polynôme

Jusqu'à / Distinct

Auteur / Remarque

Lien

n3 +

n2

 

+ 17

10 / 11

 

2n2

 

+ 11

10 / 11

 

4n2

+ 4n

+ 59

13 / 14

Honaker

Rendement: 0,437 jusqu'à 10 millions

 

n2

+ n

+ 17

15 / 16

Legendre

 

3n2

+ 39n

+ 37

17 / 18

A. Bruno (pers. comm., 2009)

 

n4

+ 29 n2

 

+ 101

19 / 20

E. Pegg, Jr. (pers. comm., 2005)

 

7n2

– 371n

+ 4 871

23 / 24

F. Gobbo (pers. comm.,  2005)

 

n2

+ 3n

– 167

23 / 24

Marius Coman (2012)

42 premiers ente 0 et 46

 

n2

– 49n

+ 431

23 / 24

Marius Coman (2012)

Idem à celle en  - 167, mais dans l'ordre inverse

 

13n2

– 331n

+ 1 847

23 / 24

Marius Coman (2012)

 

13n2

– 469n

+ 4 217

23 / 24

Marius Coman (2012)

 

2n2

 

+ 29

28 / 29

Legendre (1798)

 

16n2

– 300n

+ 1 447

30

Marius Coman

 

16n2

– 628n

+ 6 203

36

Idem à celui en  1447, mais en ordre inverse

 

8n2

+ 8n

+ 197

32 / 31

Marius Coman

 

16n2

– 292n

+ 1 373

32 / 31

Marius Coman

 

16n2

– 668n

+ 7 013

32 / 31

Idem à celle en 1 373, mais en ordre inverse

 

25n2

– 1 185n

+ 14 083

33 / 32

Marius Coman

 

25n2

– 365n

+ 1 373

33 / 32

Idem à celle en 14 083, mais en ordre inverse

 

81n2

– 2 247n

+ 15 383

34 / 33

Marius Coman

 

81n2

– 2 937n

+ 26 423

34 / 33

Idem à celle en 15 383, mais en ordre inverse

 

4n2

– 2 247n

+ 15 383

34 / 33

Marius Coman

 

4n2

+ 12n

– 1 583

36 / 35

Marius Coman

 

4n2

– 284n

+ 3 449

36 / 35

Idem à celle en – 1 583, mais en ordre inverse

 

4n2

– 152n

+ 1 607

 / 40

Marius Coman

 

6n2

– 342n

+ 4 903

57 / 29

J. Brox (pers. comm.,  2006)

 

8n2

– 488n

+ 7 243

61 / 31

F. Gobbo (pers. comm.,  2005)

 

43n2

– 537n

+ 2 971

34 / 35

J. Brox (pers. comm., 2006)

 

42n3

+ 270n2

– 26 436n

+ 250 703

39 / 40

Wroblewski and Meyrignac

 

n2

+ n

+ 41

40 / 40

Euler, 1772

Rendement: 0,475 jusqu'à 10 millions

>>>

n2

– 79n

+ 1 601

40 / 40

Excott

Idem Euler avec n  n – 40

>>>

103n2

– 4 707n

+ 50 383

/ 43

Speiser (pers. comm., 2005)

 

103n2

+ 31n

– 3 391

/ 43

Ruby

 

47n2

– 1701n

+ 10 181

/ 43

Fung and Ruby

 

47n2

+ 9n

– 5 209

-22 à 18

 /43

Fung

 

36n2

+ 18n

– 1 801

-33 à 11

/ 45

Ruby (1989) – Le record

 

 

 

 

POLYNÔMES de degré > 2

 

Alors que la quantité de premiers consécutifs semble plafonner autour de 45 avec les polynômes quadratiques, les mathématiciens ont trouvé des suites de premiers plus longues en recourant aux degrés élevés (jusqu'à 6 actuellement).



Polynôme

Jusqu'à / Distinct

Auteur / Remarque

Lien

3n3

+ 183n2

– 3 318n

  18 757

46 / 43

S. M. Ruiz (pers. comm., 2005)

 

36n2

– 810n

+ 2 753

44  / 45

Fung and Ruby (1989)

 

– 66n3

+ 3 845n2

– 6 0897n

  25 1831

45 / 46

Kazmenko and Trofimov (2006)

 

n5 – 99n4 + 3 588n3 – 56 822n2

+ 348 272n –  286 397

46 / 47

Wroblewski and Meyrignac (2006)

 

6n3

+ 83n2

– 13 735n

+ 30 139

-26 à 19

/46

Dress et Landreau

 

n4 – 97n3 + 3 294n2

– 45 458n –  213 589

49 / 49

Beyleveld (2006)

 

/ 49

Dress et Landreau

J. Wroblewski et J.-C. Meyrignac

 

/ 49

Dress et Landreau

 

1/4 (n5  133n4 +  6 729n3

  158 379n2

+  1 720 294n +  6 823 316)

56 / 57

Dress and Landreau (2002), Gupta (2006)

 

/ 57

Dress et Landreau

Shyam Sunder Gupta

 

1/36 (n6 – 126n5 + 6 217n4

  153 066n3 + 1 987 786n2

  13 055 316n +  34 747 236)

54 / 55

Wroblewski and Meyrignac (2006)

 

/ 57

Dress et Landreau

 

/ 57

Dress et Landreau

 

-25 à 31

/ 58

Dress and Landreau (2010)

>>>

 

 

 

Autres POLYNÔMES –

Premiers dans la plage (mais pas tous)

 

Ces polynômes produisent des nombres premiers en grandes quantité, mais pas forcément consécutifs.

NB. Ce classement mériterait une vérification que je n'ai pas encore effectuée.

Polynôme

Jusqu'à / Distinct

Auteur / Remarque

Lien

n2

+ 3n

  167

46 / 42

Marius Coman

n2

  49n

+ 431

46 / 42

Idem à celui en  - 167, mais en ordre inverse.

2n2

+ 4n

+ 117

Ulam / Stein / Wells

Rendement: 0,05 jusqu'à 10 millions

 

n2

+ n

+ 1

Ulam / Stein / Wells

Rendement: 0,29 jusqu'à 300 000

 

36n2

+ 18n

– 1 801

50 /49

Dress et Olivier (1999)

 

2n2

– 212n

+  5 419

99 / 57

Marius Coman

 

4n2

– 284n

+  3 449

95 / 60

Marius Coman

 

4n2

+ 12n

– 15 83

95 / 60

Idem à celui en  3 449, mais en ordre inverse.

 

2n2

– 108n

+  1 259

101 / 66

Marius Coman

 

4n2

– 482n

+  14 561

99 / 88

Marius Coman (2012)

 

41n2

– 4 641n

+  88 007

100 / 90

Boston et Greenwood (1995)

 

41n2

+ 33n

– 43 321

Idem à celui en 88 007

 

n2

– 69n

+  1 231

Euler pour  n = m – 35

 

 

9n2

+ 3n

– 16 229

200 / 166

Dress et Olivier

 

 

n2

+ n

– 1 354 363

1000 / 698

Dress et Olivier

 

 

4n2

+ 170n

+ 1 847

1560 / 727

Ulam / Stein / Wells

Rendement: 0,466 jusqu'à 10 millions

Forme cousine de celle d'Euler avec

n  2n + 42

>>>

 

n3  + n2

– 468 610 n

+ 4 021

1000 / 601

Dress et Landreau

 

 

1000 / 539

Dress et Landreau

 

Tables d'après: Prime-Generating PolynomialMathWorld--A Wolfram Web Resource.

A Visual Display of Some Properties of the Distribution of Primes

Ten prime generaing quadratic polynomial – Marius Coman

Polynômes prenant beaucoup de valeurs premières

Sloane A212325 / Sloane A213810

 

 

Dress et Landreau

 

François Dress est professeur émérite en mathématique à l’université de Bordeaux.

 

Bernard Landreau est maître de conférences à l’université d’Angers.

 

Record en 2010 avec un polynôme produisant 58 premiers consécutifs. Six mois de calcul avec une quarantaine de processeurs en parallèle du Centre de Calcul Intensif des Pays de Loire et du CNRS. Test de plus de 300 milliards de milliards de polynômes.

 

 

 

 

Formule de récurrence

 

La formule suivante engendre des nombres premiers:

 

En commençant avec a1 = 7.

 

Le terme en PGCD est égal soit à 1, soit à un nombre premier.

Formule découverte en 2003 par Matthew Frank

Démontrée en 2008 par Eric Rowland (université Rutgers aux États-Unis).

 

Exemples

Extrait de: a simple prime-generating recurrence – Eric Rowland

 

 

 

Formule de Mills

 

En 1947, W. Mills propose une formule qui donne des nombres

premiers à condition de connaître une constante A.

Mais là est le problème: il faut déterminer la constante A, et pour la connaitre avec la précision suffisante, il faut connaître les nombres premiers.

 

Formule de Wills

 

Les crochets désigne la parie entière.

Et la constante de Mills vaut:

1,3063778838 6308069046 8614492602 6057129167 8458515671 3644368053 759966434 ...

 

 

 

 

 

POLYNÔMES qui évitent les premiers

 

L'intérêt premier consiste, bien sûr, à se concentrer sur ces individus particuliers que sont les nombres premiers. Maia, certains ont cherché des polynômes qui produisent de longues séquences de nombres composés.

NB. On sait, par ailleurs, trouver des séquences de nombres composés aussi longue que l'on veut.

 

 

N = 2x – 1 + 4y (x + y)

 

Cette formule engendre quantité de nombres composés, mais sans les donner tous (évidemment); même pas pour les k premiers nombres, par exemple.

La table donne toutes les valeurs possibles pour N de 1 à 105.

Pour x de 1 à 10 000 et y de 1 à 10 000, toutes les valeurs de N sont composées. Alors N = 800 019 999 = 34 .7 .11 .101 .127.

Merci à Christophe pour son aide à la mise à jour de ces pages

 

 

 

Analyse de la  formule        

*    Un exemple de formule et recherches associées.

 

Exemple

 

 

*    Les quatre premières valeurs sont des nombres premiers: kts = 4.

*    Un  test jusqu'à n = 20, montre qu'il y a 11 nombres premiers (kt = 20).

 

 

 

Analyse

 

Pour a de 2 à 20; k de 2 à 20 et n de 1 à 50

kts est la quantité de premiers qui se succèdent depuis le début et kt est la quantité totale sur la plage.

 

*    La formule en 2 x 6n + 1 est la plus performante avec 4 premiers qui se suivent et 11 premiers parmi les 20 nombres (exemple vu ci-dessus).

La formule en 20 x 3n + 1 donne cinq premiers de suite.

 

*    En prenant le signe moins: 2 x 6^n – 1

La formule en 2 x 6n – 1 est plus performante que celle avec les signe plus avec 5 premiers qui se suivent et 13 premiers parmi les 20 nombres.

 

 

Signe positif

a, k, kts, kt

2,  6, 4, 11

10, 15, 4, 9

20, 3, 5, 10

Signe négatif

2,  6, 5, 13

3,  2, 4, 11

10, 3, 4, 14

12, 6, 4, 12

12, 11, 4, 9

 

 

Merci à Cyril N. C.

 

 

 

 

Suite

*    Formule d'Euler en 41

*    Tables des nombres premiers selon ces formules

*    Nombre premiersIndex

Voir

*    Barre magique des nombres premiers

*    Efficacité de ces formules

*    Identités remarquables

*    Liste de nombres premiers

*    Spirale d'Ulam

DicoNombre

*    Nombre 1,306 …

Sites

*    Formules pour les nombres premiers – Jean-Paul Delahaye

*    Formules et nombres premiers – CNRS info

*    Formules pour les nombres premiers – Wikipédia

*    Polynômes prenant beaucoup de valeurs premières – François Dress et Bernard Landreau

*    Prime formula – Eric Weisstein

*    Prime-Generating Polynomial – Wolfram MathWorld

*    A Natural Prime-Generating Recurrence – Eric Rowland – 2008

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Premier/formule.htm