Crible de Sundaram

Le crible de Sundaram permet de lister les entiers naturels impairs composés grâce à des suites arithmétiques placées en colonnes. Son intérêt est qu'on peut en déduire, par passage au complémentaire, l'ensemble des nombres premiers.

La colonne numéro n a pour premier terme (2n + 1)2 et pour raison 2(2n + 1). Chaque colonne commence donc par le carré d'un nombre impair, et tous les carrés de nombres impairs commencent une colonne.

Chaque colonne comprend tous les multiples impairs du nombre impair (2n+1) dont le carré commence la colonne. En effet pour qu'un nombre soit dans cette colonne, il faut et il suffit qu'il soit de la forme: (2n+1)*(2n+1)+k*(4n+2), soit (2n+1)*(2n+2k+1) ce qui définit, en faisant varier k, tous les multiples impairs de (2n+1)[1].

Par construction, le tableau ne contient que des nombres impairs composés, et il les contient tous car tout nombre composé impair s'écrit (2n + 1)*(2m + 1) avec n ≤ m, et figure au moins dans la colonne n.

Le tableau ci-dessous donne les premières lignes et colonnes construites par le crible:

9
15 25
21 35 49
27 45 63 81
33 55 77 99 121
39 65 91 117 143 169
45 75 105 135 165 195 225
51 85 119 153 187 221 255 289
57 95 133 171 209 247 285 323 361
63 105 147 189 231 273 315 357 399 441
69 115 161 207 253 299 345 391 437 483 529
... ... ... ... ... ... ... ... ... ... ... ...

S. P. Sundaram était un mathématicien indien originaire de la ville de Sathyamangalan dans l'état du Tamil Nadu. Le crible qu'il publia en 1934[2],[3] était un peu différent du modèle ci-dessus. Il contenait les valeurs n telles que 2n + 1 ne soit pas premier. Le tableau de cette page offre directement les valeurs 2n + 1.

Notes et références
  1. Un même nombre peut apparaitre plusieurs fois dans le résultat du crible. Par exemple 45=9*5 apparait dans les colonnes commençant par 9 et 25.
  2. (en) V. Ramaswami Aiyar, « Sundaram's Sieve for Prime Numbers », The Mathematics Student, vol. 2, no 2,‎ , p. 73 (ISSN 0025-5742, lire en ligne).
  3. (en) G., « Curiosa 81. A New Sieve for Prime Numbers », Scripta Mathematica, vol. 8, no 3,‎ , p. 164 (lire en ligne).
  • Arithmétique et théorie des nombres
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.