Nombre de Perrin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, un nombre de Perrin est un terme de la « suite de Perrin », cas particulier de la suite de Padovan, définie par récurrence de la manière suivante :

u_0 = 3, u_1 = 0, u_2 = 2
et pour tout  n \geq 3,u_n=u_{n-2}+u_{n-3}.

Les 20 premiers termes de la suite sont :

u_0 u_1 u_2 u_3 u_4 u_5 u_6 u_7 u_8 u_9 u_{10} u_{11} u_{12} u_{13} u_{14} u_{15} u_{16} u_{17} u_{18} u_{19}
3 0 2 3 2 5 5 7 10 12 17 22 29 39 51 68 90 119 158 209


Propriétés[modifier | modifier le code]

  • Si n est un nombre premier, un est un multiple de n[1].
  • Pour la réciproque, R. Perrin avait conjecturé en 1899 que n est premier si et seulement si n divise un.

Cependant, le premier contre exemple, autre que 1 a été trouvé en 1980 : il s'agit de 271 441. En effet, 271 441 divise u271 441, et 271 441 = 5212. u271 441 a 33150 chiffres. Un tel nombre est appelé nombre pseudo-premier de Perrin. Il y en a une infinité[2].

Implémentation informatique[modifier | modifier le code]

Voici une implémentation possible de la suite en ocaml :

let perrin n = 
  let rec aux u1 u2 u3 = function 0 -> u3 | n -> aux u2 u3 (u1+u2) (n-1) in
    match n with
      | 1 -> 0
      | 2 -> 2
      | 3 -> 3
      | n -> aux 0 2 3 (n-3)

Résultat (utilise Ocaml Batteries), en filtrant les n qui ne divisent pas Un :

# List.of_enum **> filter (fun (n, un) -> un mod n = 0) **> map (fun n -> (n, perrin n)) (2--50);;
- : (int * int) list =
[(2, 2); (3, 3); (5, 5); (7, 7); (11, 22); (13, 39); (17, 119); (19, 209); (23, 644); (29, 3480); (31, 6107); (37, 33004); (41, 101639); (43, 178364); (47, 549289)]

Notes et références[modifier | modifier le code]

  1. suite A001608 de l'OEIS.
  2. (en) Jon Grantham, « There are infinitely many Perrin pseudoprimes », Journal of Number Theory, vol. 130, no 5,‎ 2010, p. 1117-1128 (lien DOI?, lire en ligne).

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Texte sur les pseudo-premiers de Perrin