Fibonacci Sequence Generator

La suite de Fibonacci est une série de nombres ou chaque terme est la somme des deux termes precedents, commencant par 0 et 1. La suite commencé 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 et continue à l'infini. Nommee d'après le mathematicien italien Leonard de Pise (Fibonacci), qui l'a introduite dans les mathématiques occidentales en 1202 dans son livre Liber Abaci, la suite etait en fait apparue dans les mathématiques indiennes des siecles auparavant. C'est l'une des suites les plus célèbres en mathématiques.

La suite de Fibonacci est profondement liée au nombre d'or (phi = 1.618...), car le rapport de nombres de Fibonacci consecutifs converge vers phi. Ce rapport apparait dans les motifs en spirale des graines de tournesol, des ecailles de pommes de pin et des coquillages. En informatique, les nombres de Fibonacci sous-tendent des algorithmes efficaces comme les tas de Fibonacci. Dans les marches financiers, les niveaux de retracement de Fibonacci sont utilises par les traders pour predire les niveaux de support et de resistance.

Les propriétés importantes incluent : (1) F(n) = F(n-1) + F(n-2) avec F(0) = 0, F(1) = 1. (2) Le rapport F(n+1)/F(n) s'approche de phi. (3) Tout entier positif peut être représenté comme somme de nombres de Fibonacci non consecutifs (théorème de Zeckendorf). (4) PGCD(F(m), F(n)) = F(PGCD(m,n)). (5) La somme des n premiers nombres de Fibonacci est F(n+2) - 1. (6) La formule de Binet donne une expression en forme close utilisant le nombre d'or.

Pour générer de nombreux termes, utilisez le calcul iteratif plutot que la recursion naive qui à une complexité exponentielle. La memoisation ou la programmation dynamique réduit cela à un temps lineaire. Pour les très grands nombres de Fibonacci, l'exponentiation matricielle calcule F(n) en O(log n). Pour vérifier si un nombre est un nombre de Fibonacci, testez si 5n^2 + 4 ou 5n^2 - 4 est un carre parfait.