Polynômes donnant des nombres premiers


Polynôme d'Euler

Le polynôme d'Euler P(n)=n2+n+41 permet de n'obtenir que des nombres premiers lorsque n prend les valeurs consécutives n=0, 1, 2, ..., 39.
Les nombres premiers p tels que n2+n+p soit un nombre premier pour tous les p-1 naturels n = 0, ...,(p-2) sont appelés 'nombres chanceux' par François Le Lionnais. Ces nombres chanceux forment la suiteA014556 de Neil A. Sloane.

Autres polynômes du second degé

Quels sont les polynômes P(n)=a n2+b n+ c qui permettent pour n=0,1,2,...,K-1 d'obtenir K nombres premiers distincts ?

Le programme pprime.c, disponible sur cette page, permet de trouver quelques uns de ces polynômes, en particulier les records du moment :
Q(n) = 36 n2 - 810 n + 2753 et Q(44-n) = 36 n2 - 2358 n + 36809 permettent de déterminer successivement 45 nombres premiers.
Un choix arbitraire a été opéré parmi les très nombreux polynômes produits, aussi certains polynômes comme 2n2 + 29 (Legendre) ou n2 + n + 17 ne figurent pas sur cette page pais on peut trouver d'autres polynômes dans un fichier texte.

Cliquez sur les polynômes du tableau ci-dessous pour voir les nombres premiers engendrés.
N°Nombre K d'entiers
premiers obtenus
en calculant
P(0), P(1) ... P(K-1)		PolynômesSuite n°Inventeur
 1  5  37*n^2 - 3187*n + 6229  
 2  6  50*n^2 - 3154*n + 3109  
 3  7  110*n^2 - 3994*n + 14221  
 4  9  220*n^2 - 4984*n + 16421  
 5  10  144*n^2 - 4014*n + 10753  
 6  12  518*n^2 - 9740*n + 39799  
 7  13  326*n^2 - 7216*n + 31567  
 8  14  1225*n^2 - 14035*n + 36551  
 9  15  2233*n^2 - 23079*n + 56599  
 10  17  100*n^2 - 4280*n + 22091  
 11  20  55*n^2 - 4045*n + 34961  
 12  21  11*n^2 - 229*n + 1201  
 13  23  193*n^2 - 4757*n + 28283  
 14  24  n^2 - 49*n + 431  
 15  30  12*n^2 - 438*n + 3797  
 16  30  12*n^2 - 258*n + 1187  
 17  30  23*n^2 - 709*n + 5437  
 18  30  9*n^2 - 267*n + 1871  
 19  30  9*n^2 - 255*n + 1697  
 20  30  8*n^2 - 414*n + 4259  
 21  30  - 8*n^2 + 50*n + 1019  
 22  30  16*n^2 - 300*n + 1447  
 23  30  16*n^2 - 628*n + 6203  
 24  30  3*n^2 - 1299*n + 17659  
 25  30  - 3*n^2 - 1125*n + 17489  
 26  30  97*n^2 - 2975*n + 21059  
 27  30  97*n^2 - 2651*n + 16361  
 28  30  67*n^2 - 2673*n + 24379  
 29  30  16*n^2 - 522*n + 3709  
 30  30  16*n^2 - 406*n + 2027  
 31  30  67*n^2 - 1213*n + 3209  
 32  30  86*n^2 - 3128*n + 24103  
 33  30  86*n^2 - 1860*n + 5717  
 34  30  106*n^2 - 2930*n + 16787  
 35  30  59*n^2 - 1433*n + 5821  
 36  30  59*n^2 - 1989*n + 13883  
 37  30  542*n^2 - 19756*n + 180181  
 38  30  542*n^2 - 11680*n + 63079  
 39  30  337*n^2 - 9277*n + 61469  
 40  30  137*n^2 - 2271*n + 8171  
 41  30  137*n^2 - 5675*n + 57529  
 42  30  141*n^2 - 3303*n + 6353  
 43  30  1116*n^2 - 31572*n + 222163  
 44  30  12*n^2 - 792*n + 7649  
 45  30  - 12*n^2 - 96*n + 5227  
 46  30  n^2 - 917*n + 9479  
 47  30  - n^2 - 859*n + 16273  
 48  30  155*n^2 - 3465*n + 9431  
 49  30  263*n^2 - 6883*n + 45553  
 50  30  263*n^2 - 8371*n + 67129  
 51  30  106*n^2 - 3218*n + 20963  
 52  30  157*n^2 - 6867*n + 70297  
 53  30  142*n^2 - 3668*n + 15467  
 54  30  129*n^2 - 3963*n + 11411  
 55  30  328*n^2 - 12652*n + 119183  
 56  30  1388*n^2 - 35132*n + 219301  
 57  30  173*n^2 - 6523*n + 56473  
 58  30  62*n^2 - 1478*n + 3637  
 59  30  142*n^2 - 4568*n + 28517  
 60  30  157*n^2 - 2239*n + 3191  
 61  30  62*n^2 - 2118*n + 12917  
 62  30  337*n^2 - 10269*n + 75853  
 63  30  158*n^2 - 5202*n + 37511  
 64  30  158*n^2 - 3962*n + 19531  
 65  30  173*n^2 - 3511*n + 12799  
 66  30  129*n^2 - 3519*n + 4973  
 67  30  328*n^2 - 6372*n + 28123  
 68  30  141*n^2 - 4875*n + 29147  
 69  30  155*n^2 - 5525*n + 39301  
 70  30  215*n^2 - 8765*n + 58573  
 71  30  61*n^2 - 1621*n + 13007  
 72  30  61*n^2 - 1917*n + 17299  
 73  30  186*n^2 - 6108*n + 36083  
 74  30  1116*n^2 - 33156*n + 245131  
 75  31  16*n^2 - 292*n + 1373  
 76  31  16*n^2 - 668*n + 7013  
 77  31  32*n^2 - 944*n + 6763  
 78  31  8*n^2 - 488*n + 7243  
 79  31  - 8*n^2 - 8*n + 197  
 80  31  32*n^2 - 976*n + 7243  
 81  31  53*n^2 - 1579*n + 9319  
 82  31  53*n^2 - 1601*n + 9649  
 83  31  146*n^2 - 3558*n + 16193  
 84  31  103*n^2 - 2259*n + 10009  
 85  31  103*n^2 - 3921*n + 34939  
 86  31  4*n^2 - 428*n + 5081  
 87  31  - 4*n^2 - 188*n + 4159  
 88  31  61*n^2 - 2233*n + 18959  
 89  31  61*n^2 - 1427*n + 6869  
 90  31  148*n^2 - 5802*n + 46183  
 91  31  101*n^2 - 2699*n + 15607  
 92  31  109*n^2 - 4133*n + 37991  
 93  31  109*n^2 - 2407*n + 12101  
 94  31  1042*n^2 - 29526*n + 208393  
 95  31  83*n^2 - 2727*n + 18521  
 96  31  283*n^2 - 9609*n + 75289  
 97  31  101*n^2 - 3361*n + 25537  
 98  31  283*n^2 - 7371*n + 41719  
 99  31  83*n^2 - 2253*n + 11411  
 100  31  219*n^2 - 5235*n + 26833  
 101  31  219*n^2 - 7905*n + 66883  
 102  31  206*n^2 - 5336*n + 32467  
 103  31  206*n^2 - 7024*n + 57787  
 104  31  146*n^2 - 5202*n + 40853  
 105  31  662*n^2 - 31626*n + 378893  
 106  31  267*n^2 - 15675*n + 217409  
 107  31  662*n^2 - 8094*n + 25913  
 108  31  148*n^2 - 3078*n + 5323  
 109  31  1042*n^2 - 32994*n + 260413  
 110  32  25*n^2 - 365*n + 1373  
 111  32  25*n^2 - 1185*n + 14083  
 112  32  27*n^2 - 753*n + 4649  
 113  32  27*n^2 - 921*n + 7253  
 114  32  134*n^2 - 4012*n + 26821  
 115  32  291*n^2 - 15279*n + 197641  
 116  32  134*n^2 - 4296*n + 31223  
 117  32  53*n^2 - 1369*n + 2767  
 118  32  53*n^2 - 1917*n + 11261  
 119  32  202*n^2 - 8980*n + 96461  
 120  32  67*n^2 - 3889*n + 48953  
 121  32  11*n^2 - 1441*n + 23197  
 122  32  - 11*n^2 - 759*n + 10903  
 123  32  291*n^2 - 2763*n + 3643  
 124  32  202*n^2 - 3544*n + 12203  
 125  32  199*n^2 - 6927*n + 55921  
 126  32  199*n^2 - 5411*n + 32423  
 127  33  53*n^2 - 1885*n + 15061  
 128  33  53*n^2 - 1507*n + 9013  
 129  33  81*n^2 - 2247*n + 15383  
 130  33  81*n^2 - 2937*n + 26423  
 131  33  41*n^2 - 1373*n + 7753  
 132  33  41*n^2 - 1251*n + 5801  
 133  33  86*n^2 - 2110*n + 8677  
 134  33  237*n^2 - 3645*n + 6659  
 135  33  365*n^2 - 17675*n + 212587  
 136  33  89*n^2 - 3177*n + 23357  
 137  33  47*n^2 - 1355*n + 7669  
 138  33  47*n^2 - 1653*n + 12437  
 139  33  109*n^2 - 3899*n + 30269  
 140  33  86*n^2 - 3394*n + 29221  
 141  33  109*n^2 - 3077*n + 17117  
 142  33  89*n^2 - 2519*n + 12829  
 143  33  708*n^2 - 18072*n + 116293  
 144  33  6*n^2 - 2112*n + 44959  
 145  33  271*n^2 - 8601*n + 63247  
 146  33  365*n^2 - 5685*n + 20747  
 147  33  708*n^2 - 27240*n + 262981  
 148  33  237*n^2 - 11523*n + 132707  
 149  33  271*n^2 - 8743*n + 65519  
 150  34  16*n^2 - 446*n + 2777  
 151  34  16*n^2 - 610*n + 5483  
 152  34  514*n^2 - 22938*n + 256117  
 153  34  514*n^2 - 10986*n + 58909  
 154  34  127*n^2 - 6183*n + 73327  
 155  34  137*n^2 - 7529*n + 99871  
 156  34  137*n^2 - 1513*n + 607  
 157  34  58*n^2 - 1600*n + 6089  
 158  34  127*n^2 - 2199*n + 7591  
 159  34  38*n^2 - 2698*n + 38593  
 160  34  58*n^2 - 2228*n + 16451  
 161  34  541*n^2 - 19445*n + 172223  
 162  34  541*n^2 - 16261*n + 119687  
 163  35  4*n^2 - 284*n + 3449  
 164  35  - 4*n^2 - 12*n + 1583  
 165  35  24*n^2 - 666*n + 3943  
 166  35  24*n^2 - 966*n + 9043  
 167  35  197*n^2 - 7189*n + 58711  
 168  35  83*n^2 - 1825*n + 5821  
 169  35  83*n^2 - 3819*n + 39719  
 170  35  43*n^2 - 537*n + 2971  
 171  35  43*n^2 - 2387*n + 34421  
 172  35  197*n^2 - 6207*n + 42017  
 173  36  101*n^2 - 3153*n + 17159  
 174  36  37*n^2 - 2975*n + 49121  
 175  36  - 37*n^2 - 385*n + 9679  
 176  36  94*n^2 - 3530*n + 24623  
 177  36  94*n^2 - 3050*n + 16223  
 178  36  101*n^2 - 3917*n + 30529  
 179  37  89*n^2 - 2091*n + 9479  
 180  37  89*n^2 - 4317*n + 49547  
 181  37  67*n^2 - 3849*n + 48481  
 182  37  94*n^2 - 3632*n + 23981  
 183  37  157*n^2 - 5919*n + 47161  
 184  37  193*n^2 - 6251*n + 51899  
 185  37  193*n^2 - 7645*n + 76991  
 186  37  94*n^2 - 3136*n + 15053  
 187  37  157*n^2 - 5385*n + 37549  
 188  39  139*n^2 - 3453*n + 11701  
 189  39  123*n^2 - 4173*n + 29611  
 190  39  59*n^2 - 2213*n + 19081  
 191  39  59*n^2 - 2271*n + 20183  
 192  39  123*n^2 - 5175*n + 48649  
 193  39  139*n^2 - 7111*n + 81203  
 194  39  188*n^2 - 4626*n + 10529  
 195  40  111*n^2 - 3123*n + 10753  
 196  40  8*n^2 - 326*n + 2659  
 197  40  n^2 + n + 41  A005846Euler
 198  40  4*n^2 - 154*n + 1523  
 199  40  4*n^2 - 158*n + 1601  
 200  40  9*n^2 - 471*n + 6203  
 201  40  9*n^2 - 231*n + 1523  
 202  40  8*n^2 - 298*n + 2113  
 203  40  n^2 - 79*n + 1601  
 204  40  59*n^2 - 2729*n + 25633  
 205  40  59*n^2 - 1873*n + 8941  
 206  40  137*n^2 - 4043*n + 27277  
 207  40  137*n^2 - 6643*n + 77977  
 208  40  111*n^2 - 5535*n + 57787  
 209  43  103*n^2 - 4707*n + 50383  
 210  43  103*n^2 - 3945*n + 34381  
 211  43  47*n^2 - 2247*n + 21647  
 212  43  47*n^2 - 1701*n + 10181  A050267Fung et Ruby
 213  45  36*n^2 - 810*n + 2753  A050268Fung et Ruby
 214  45  36*n^2 - 2358*n + 36809  


Logiciels

Téléchargez et compilez le [Programme C] de construction des polynômes de la table ci-dessus. (Au début du code de ce programme, la constitution d'un crible de nombres premiers).
L'exécutable : pprime (déjà compilé linux pentium debian 2)

Concours de polynômes

Un concours [Al Zimmermann's Programming Contests] doté de 500$ de prix est organisé depuis le 13 mars 2006 et se termine le 13 juin 2006.
La description du concours par Ed Pegg Jr se trouve sur la page [Prime Generating Polynomials].

De manière abrégée et donc très incomplète :
Il s'agit de trouver pour chaque degré n de 1 à 10, trois polynômes f(x) = an*xn+an-1*xn-1+...+a1*x+a0.
Pour chacun des trois polynômes on calcule f(0), f(1), ... (polynôme 1) ou leurs valeurs absolues (polynômes 2 et 3), en dénombrant les nombres premiers rencontrés. L'arrêt s'effectue dès qu'on rencontre un nombre composé (polynômes 1 et 2) ou lorsque x atteint une limite maximale imposée (polynôme 3) (la limite est telle que xd<264, sa valeur précise est donnée dans un tableau).
Un score est calculé en effectuant la somme des valeurs calculées pour les différents polynômes de degrés d : (nombre de premiers produits par f(x)) + (1/log(10+abs(f(0)*f(1)*..*f(d))))
Le meilleur score éventuellement possible est 30 et à l'heure où j'écris cette page, le meilleur score déjà atteint est 26.6314.
Chaque semaine un prix de 10$ est attribué.

Ressources, références, liens

Formules et nombres premiers cnrs info Il existe des formules qui donnent tous les nombres premiers, mais...
Les formules simples qui donnent des nombres premiers en grande quantité.
Prime-Generating Polynomial Eric Weistein MathWorld et Prime Arithmetic Progression
Puzzle 232. Primes and Cubic polynomials et Problem 12.- Prime producing polynomials sur le site The prime puzzles & problems connections par Carlos Rivera


















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014