Geekly articles weekly

Chiffres pairs de Fibonacci

Inspiré par un commentaire sous un post de Fibonacci pour une interview . L'utilisateur pavellyzhin a mentionné la tâche d'interview suivante ( commentaire ):
Il y a plus d'un an, «php-programmer» a répondu à la vacance, ils ont envoyé des savoirs traditionnels et il y avait une tâche de Fibonacci: sélectionner tous les numéros pairs de Fibonacci compris entre 1 et 10000 . Décidé en utilisant une boucle (pour). Là, il était également nécessaire de faire une requête SQL pour sélectionner les anniversaires les plus proches des utilisateurs, pour inventer quelque chose, je ne me souviens tout simplement pas et écrire une sorte de fonction. J'ai tout fait, je l'ai envoyé. Ils ont envoyé une réponse: "selon les résultats de la tâche de test, vous n'êtes pas accepté." Ce qu'ils n'aimaient pas exactement n'était pas écrit. Maintenant je suis assis et je réfléchis, probablement après tout à cause de Fibonacci, j'ai volé ... :)
Dans ce post, je vais montrer comment il a été possible de résoudre ce problème efficacement, et peut-être même efficacement, mais ce n'est pas exact. Dans le même temps, je vais démontrer quelques milliers de faits prouvés sur les chiffres de Fibonacci.


Théoriser



La meilleure façon de commencer est de regarder à travers les yeux des premiers N nombres de Fibonacci et d'essayer de trouver un motif dans l'arrangement des nombres pairs.

1.1, bf2,3.5, bf8,13.21, bf34,55.89, bf144, ldots


Les nombres pairs sont marqués dans la séquence, comme vous pouvez le voir chaque troisième nombre de Fibonacci est pair et, probablement, tous les nombres pairs sont en position de multiples de 3. Ce sera notre supposition, maintenant nous devons le confirmer et élaborer un algorithme de calcul.

La meilleure preuve est simple, donc merci à AllexIn pour l'idée simple que j'ai d'abord manquée. Chaque numéro de Fibonacci suivant est la somme des deux précédents, si les deux numéros précédents sont impairs, alors le suivant sera pair, si dans les deux numéros précédents l'un est impair et l'autre est pair, alors le suivant sera impair. En principe, cette idée seule suffit déjà à «tâtonner intuitivement» le fait avéré. La preuve par induction est évidente, mais je ne résiste pas, pour ne pas la rapporter

Nous prouvons que "chaque troisième nombre de Fibonacci est pair, et les deux précédant chacun de ces nombres sont impairs."
  • Induction de base . Deux premiers nombres de fibonacci 1,1 $ - impair, troisième numéro 2 - même
  • Hypothèse . Supposons que jusqu'à un certain nombre de Fibonacci multiple de 3, il est vrai que chaque tiers est pair et que les deux précédents sont impairs.
  • Étape d'induction . Le nombre suivant le dernier pair de l'hypothèse est impair, car il est obtenu à partir de la somme des impairs avec les pairs, suite à ce nombre déjà est également impair, car il est obtenu à partir de la somme du pair avec le impair, et le suivant après qu'il est pair, car les deux précédents qui viennent de lui être reçus sont impairs, par construction son nombre est un multiple de 3, il est pair, et les deux précédents sont impairs.


C'est ainsi que nous pouvons prouver notre supposition sans même recourir à des calculs mathématiques. Vous pouvez formaliser cette idée, tout en obtenant une formule pour calculer chaque troisième nombre de Fibonacci Fn+3 de Fn et Fn+1 . Utiliser la relation récursive Fn+2=Fn+1+Fn nous obtenons:

Fn+3=Fn+2+Fn+1=2Fn+1+Fn


Donc si Fn - même alors Fn+3 même en vertu de cette formule. Étant donné que F3=2 , alors chaque troisième nombre de Fibonacci est vraiment pair, ce qui confirme une partie de notre supposition. Ici, vous devez vous assurer que nous ne manquons pas d'autres nombres pairs, c'est-à-dire qu'ils ont tous des multiples de 3. Merci à janatem pour son idée simple, car d'après la formule ci-dessus pour Fn+3 il s'ensuit également que si Fn - étrange alors Fn+3 aussi étrange, donc nous obtenons ces nombres avec des nombres 3k−2,3k−1,k in mathbbN - impair (par induction, commencez par F1=F2=1 - impair), et 3k,k in mathbbN - pair, qui couvre tous les nombres de Fibonacci, ce qui signifie que nous couvrons vraiment tous les nombres pairs.

Il y a une autre manière, car il serait possible de montrer qu'il n'y a pas d'autres nombres pairs. Supposons qu'il existe un nombre Fm - même et 0 pas equivm mod3 alors m=3k−1 ou m=3k+1 où k - une sorte de naturel.

Passons à la représentation matricielle des nombres de Fibonacci du post d'origine

\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_n \\ F_n & F_ {n + 1} \ end {pmatrix}

\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_n \\ F_n & F_ {n + 1} \ end {pmatrix}


En calculant le déterminant des deux parties, on obtient

(−1)n=Fn+1Fn−1−F2n


Il s'ensuit que les diviseurs de nombres Fn+1,Fn et Fn−1,Fn séparateurs de match (−1)n , c'est-à-dire les nombres de Fibonacci voisins sont mutuellement simples. Cela signifie également que la simplicité et les chiffres mutuels F3k,F3k−1 et F3k,F3k+1 , c'est-à-dire F3k et Fm . Mais par hypothèse Fm - pair, et F3k - même comme prouvé précédemment. Donc, d'autres nombres pairs que F3k où k in mathbbN dans la séquence de Fibonacci n'existe pas. Et nous avons également établi un fait intéressant que les nombres de Fibonacci voisins sont mutuellement simples.

Enfin, nous montrons au moins une autre façon de prouver notre supposition: utiliser le théorème de Luke.

Théorème de Luc . Entier divise Fm et Fn , si et seulement si c'est un diviseur Fd où d= gcd(m,n) en particulier

 gcd(Fm,Fn)=F gcd(m,n)


Ici  gcd Est le plus grand facteur commun. Si mis m=3 alors  gcd(2,Fn)=F gcd(3,n) . Si Fn - même, alors le côté gauche est 2, de sorte que le côté droit est également égal à 2, il est nécessaire que n divisé par 3 et en même temps l'inverse est vrai. Ainsi, nous obtenons exactement ce que nous voulions prouver.

Donc, chaque troisième nombre de Fibonacci est pair, et chaque pair pair a un multiple de trois. Nous l'avons soigneusement prouvé et personne n'ose en douter maintenant.

Algorithme


Et maintenant, il reste à trouver un algorithme. Vous pouvez bien sûr faire ce que Pavellyzhin a fait à l' origine, mais au lieu de vérifier 0 equivFn mod2 on peut vérifier 0 équivn mod3é , c'est une torsion! Certes, cela n'affecte pas le nombre d'itérations de l'algorithme, car nous venons de changer le filtre de séquence. Il est préférable de générer immédiatement une sous-séquence de nombres de Fibonacci avec la propriété dont nous avons besoin (parité), donc une autre façon évidente est d'utiliser la formule de Binet

F_n = \ left \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ right \ rceil, \ qquad n \ in \ {3,6, \ ldots, 3k \ ldots \}

F_n = \ left \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ right \ rceil, \ qquad n \ in \ {3,6, \ ldots, 3k \ ldots \}


Il y a des difficultés avec l'efficacité des calculs, plus à ce sujet dans le message d'origine. Par conséquent, je propose la meilleure méthode, à mon avis, - calcul itératif Fn+3 , cela peut être fait, comme nous l'avons montré précédemment, par la formule Fn+3=2Fn+1+Fn . Pour construire une transition itérative dans l'algorithme, nous devons calculer Fn+4 , tout est aussi simple

Fn+4=Fn+3+Fn+2=2Fn+1+Fn+Fn+1+Fn=3Fn+1+2Fn


Soit dit en passant, d'une manière générale, il est facile de prouver que

Fn+m=FmFn+1+Fm−1Fn


Alors formellement, l'algorithme est écrit comme suit (le nombre pair de Fibonacci actuel Fn suivi du numéro de Fibonacci Fn+1 , M La limite supérieure des nombres est-elle donnée dans l'état du problème):

  1. Fn leftarrowF3=2, quadFn+1 leftarrowF4=3
  2. Si Fn>M , puis terminer, sinon ajouter au résultat Fn
  3. (Fn,Fn+1) leftarrow(2Fn+1+Fn,3Fn+1+2Fn) passez à l'étape 2.

L'algorithme est assez trivial - nous sautons simplement sur un troisième nombre de Fibonacci et l'imprimons (s'il n'est pas plus M ) La complexité de l'algorithme est toujours linéaire, mais le nombre de répétitions de l'étape 2 est exactement égal au nombre de nombres de Fibonacci pairs dans la plage 1 ldotsM , à titre de comparaison, un algorithme simple avec filtrage nécessite 3 fois plus d'itérations (pour chaque trouvé, il y en aura 2 rejetés).

L'algorithme existe sur le papier, quelle était l'interview, PHP? Eh bien, enfin découvrir PHP signifie

function evenfibs($ubound) { $result = []; [$evenf, $nextf] = [2, 3]; while($evenf <= $ubound) { array_push($result, $evenf); [$nextf, $evenf] = [ 3 * $nextf + 2 * $evenf, 2 * $nextf + $evenf]; } return $result; }


Remarque : Cette méthode peut toujours être améliorée, comme l'a montré, par exemple, l'utilisateur hunroll . L'idée est que pour les calculs, nous n'avons besoin de rien de superflu, à l'exception du résultat partiellement obtenu, c'est-à-dire nous pouvons calculer des nombres pairs en utilisant uniquement les nombres pairs de Fibonacci précédents.

Fn+3=2Fn+1+Fn=3Fn+2Fn−1=3Fn+Fn−1+Fn−1=3Fn+(Fn−1+Fn−2)+Fn−3=4Fn+Fn−3



 function evenfibs($ubound) { if($ubound < 2) return []; $evens = [2]; $next = 8; for($i = 1; $next <= $ubound; $i++) { $evens[$i] = $next; $next = $evens[$i]*4 + $evens[$i-1]; } return $evens; }


Généralisation


Nous avons mentionné ici le théorème de Luke, qui déclare que  gcd(Fm,Fn)=F gcd(m,n) . En conséquence, nous pouvons obtenir que le nombre de Fibonacci Fn multiple de Fm , si et seulement si son numéro n multiple au nombre m . C'est-à-dire chaque 4ème numéro de Fibonacci est divisé par 3, chaque 5ème par 5, chaque 6ème par 8, etc.

Ensuite, de manière simple, nous obtenons un algorithme de calcul de la sous-séquence de Fibonacci, dans lequel les éléments sont des multiples d'un certain nombre donné Fm . En utilisant le fait que

Fn+m=FmFn+1+Fm−1FnFn+m+1=Fm+1Fn+1+FmFn


L'algorithme précédent se transforme en

  1. Fn leftarrowFm, quadFn+1 leftarrowFm+1
  2. Si Fn>M , puis terminer, sinon ajouter au résultat Fn
  3. (Fn,Fn+1) leftarrow(FmFn+1+Fm−1Fn,Fm+1Fn+1+FmFn) passez à l'étape 2.

O Where Fm−1,Fm,Fm+1 peut être défini comme constantes.

Résumé des notes . Comme l'ignorait l'utilisateur à juste titre, dans le cas généralisé, il est également possible de construire un algorithme qui n'utilise que des nombres à partir d'un résultat partiel.

Fn+1=Fn+Fn−1Fn+2=3Fn−Fn−2Fn+3=4Fn+Fn−3Fn+4=7Fn−Fn−4Fn+5=11Fn+Fn−5 cdotsFn+t=(Ft+2Ft−1)Fn+(−1)t−1Fnt



Prouvons cela par la méthode de l'induction mathématique, pour t = 1 et t = 2, l'accomplissement est évident. Supposons qu'il contienne jusqu'à t; puis

Fn+t+1=Fn+t+Fn+t−1=(Ft+2Ft−1)Fn+(−1)t−1Fnt+(Ft−1+2Ft−2)Fn+(−1)t−2Fn−t+1=(Ft+Ft−1+2(Ft−1+Ft−2))Fn+(−1)t−1(Fnt−Fn−t+1)=(Ft+1+2Ft)Fn+(−1)t−1(Fnt−Fnt−Fnt−1)=(Ft+1+2Ft)Fn+(−1)tFnt−1



Quelque chose comme un total


La tâche est bien sûr entièrement synthétique, le nombre d'itérations est très faible (pour M $ = 10 000 $ la réponse ne contient que 6 chiffres, soit 6 itérations auraient été terminées, et l'algorithme «frontal» d'origine aurait nécessité 18), mais de cette manière, un utilisateur qui a découvert quelque chose de nouveau ici peut maintenant montrer un peu plus de connaissances mathématiques dans les nombres de Fibonacci lors de l'interview.

Edit: Merci aux utilisateurs de janatem et d' AllexIn pour les preuves simples, je les ai inclus dans "Theoremizing", ainsi que le hunroll pour l'algorithme en utilisant uniquement les nombres pairs déjà obtenus dans les calculs et à l' ignorance de l'utilisateur pour le généraliser.

Source: https://habr.com/ru/post/fr450594/

More articles:


All Articles