Suites de Fibonacci, Lucas et autres
Calculs - Primalité

Accueil > Mots > Suites > Fibonacci > Fibonacci 2
précédentesommairesuivante

Généralisations à d'autres suites de Lucas

Suites ayant d'autres termes initiaux et même relation de récurrence

Donnons nous deux entiers a et b et définissons la suite L par L(0)=a, L(1)=b et pour tout n > 1 par L(n) = L(n-1) + L(n-2).

Lorsque a = 0 et b = 1, on obtient la suite de Fibonacci Fn : 0, 1, 1, 2, 3, 5, 8, 13...
Lorsque a = 1 et b = 3 on obtient la suite de Lucas Ln : 2, 1, 3, 4, 7, 11, 18, 29, 47...
Pour d'autres valeurs de L0 = a et L1 = b, on obtient d'autres suites dont on peut calculer les premiers termes en utilisant l'application javascript qui se trouve un peu plus bas dans cette page.

Réutilisation de la suite de Fibonacci

Les termes L(n) de la suite de Lucas sont des combinaisons linéaires des termes consécutifs F(n-1), F(n) de la suite de Fibonacci.

Pour tout n > 1 on a L(n) = a x F(n-1) + b x F(n).

Cette propriété permet de calculer rapidement les termes de n'importe quelle suite L lorsqu'on connaît a, b et les termes de la suite F de Fibonacci.
Elle se démontre aisément en utilisant la notation matricielle de la page 3.

Remarques sur la factorisation

Diviseurs

1) a et b ont un diviseur commun

Le pgcd g de L0=a et de L1=b, divise leur somme L2 et par récurrence Ln=Ln-1+Ln-2.

Lorsque a et b ne sont pas premiers entre-eux, leur pgcd est un entier g ≠ 1 qui divise tous les termes Ln de la suite.

2) a et b premiers entre eux

De même qu'à la page 3, où est obtenue la formule F(n-1)F(n+1) - F2(n) = (-1)n,
on peut définir et calculer le nombre Cn = Ln-1Ln+1 - L2n et en particulier C1 = L0L2 - L21 = a(a+b) -b2

Un calcul semblable montre que pour n > 0 et m > 0 quelconques, Cn = (-1)n-m Cm et en particulier Cn = (-1)n-1 C1.

Le nombre C = |Cn| = |Ln-1Ln+1 - L2n| = |a(a+b) -b2| est donc une constante.

On en déduit une propriété intéressante, lorsque a et b sont premiers entre-eux :

Lorsque L0 = a et L1 = b sont premiers entre-eux, les diviseurs premiers de C = |a(a+b) -b2| ne divisent aucun des termes Lnde la suite.

En effet si le diviseur premier p de C = |Cn| = |Ln-1Ln+1 - L2n|, divisait Ln+1, il diviserait L2n+1 et doc Ln, et donc pour la même raison Ln-1, Ln-2, ... , L1=b, L0=a, ce qui contredit l'hypothèse que L0 = a et L1 = b sont premiers entre-eux.
D'où la conclusion que les diviseurs premiers de C ne divisent AUCUN des termes de la suite, dans le cas où a et b sont premiers entre-eux.

3) Remarque

g2 divise C et donc tout diviseur premier p de C/g2, s'il en existe et s'il ne divise pas g, ne divise pas non plus aucun des termes de la suite.

(Pour le voir, il suffit de considérer la nouvelle suite L' obtenue en prenant L'0=a/g et L'1=b/g. Seuls conviennent les diviseurs premiers de C qui ne divisent pas g).

Javascript rapide, en ligne

Calculez en quelques secondes seulement, les centaines ou milliers de chiffres de Fn lorsque n est grand (n=1000 ou n=10000 ou même plus).
Les termes L(0) L(1) peuvent être être choisis négatifs.

Si vous avez autorisé votre navigateur à utiliser les applets java, cochez la case "primalité" afin de tester les nombres de Lucas L(n) obtenus.
Lorsque L(n) est déclaré "Premier ou premier probable", la probabilité qu'il soit effectivement premier est très proche de 1, elle est supérieure à 1-1/2^200 = 0.9999999999999999999999999999999999999999999999999999999999993776984, dans ce cas il est donc très probable que L(n) soit premier.

L(0) L(1) :    Tester la primalité (applet java) : 

n :         



L'application javascript calcule L(n) à partir des nombres de Fibonacci : L(n) = L(0)*F(n-1)+L(1)*F(n-1).
Les nombres de Fibonacci sont calculés en utilisant la propriété : Pour 0<= k<= n-2, F(n)=F(k+2)*F(n-k-1)+F(k+1)*F(n-k-2). En prenant k+1=50, seuls sont calculés deux termes consécutifs toutes les 50 positions.
Le programme est bien plus rapide que celui qui utilise L(n)=L(n-1)+L(n-2).

Apparitions récurrentes

Termes ayant un même diviseur

Si K divise Ln, alors il existe deux entiers positifs m et r > 0, tels que { Lm + q r/ q positif} soit l'ensemble des termes de la suite divisibles par K. (m et r étant les plus petits possibles).

Il suffit de considérer la suite Ln (modulo K), le nombre m est le premier indice tel que Lm=0 (modulo K) et m+r le suivant est tel que Lm+r=0 (modulo K).

Pour utiliser une autre méthode, on peut généraliser la propriété de la constante C précédente en montrant que pour un entier h donné, A = |LnLn+2hL2n+h| est constant lorsque n varie.
Il est alors simple de montrer que si Ln et Ln+h ont un même diviseur commun K, alors ce diviseur commun K divise aussi Ln+2h. Les autres valeurs de l'indice sont obtenues par récurrence : n+2h, n+3h, ... (tant que l'indice reste positif).

(applet java)


L0 et L1    


précédentesommairesuivante

Documents - références - compléments - liens utiles















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