フィボナッチ偶数

インタビューのためのフィボナッチ投稿の下でのコメントに触発されました。 ユーザーpavellyzhinは、次のインタビュータスク（ comment ）に言及しました。

1年以上前、「php-programmer」が空席に対応し、TKを送信し、フィボナッチからのタスクがありました： 1から10000の範囲のすべての偶数フィボナッチ数を選択します 。 （for）ループを使用して決定。 そこでは、ユーザーの最も近い誕生日のサンプルでSQLクエリを作成し、何かをする必要がありました。私は覚えていませんし、何らかの関数を書いています。 私はすべてをやりました。 彼らは答えを送りました：「あなたは受け入れられないテストタスクの結果によると。」 彼らがまったく好きではなかったものは書かれていませんでした。 たぶんフィボナッチが飛んだために、おそらく私は座って考えています... :)

この投稿では、この問題を効果的に、おそらくは効率的に解決する方法を示しますが、これは正確ではありません。 同時に、フィボナッチ数について証明された数千の事実を実証します。

理論化

開始する最良の方法は、最初のN個のフィボナッチ数の目を見て、偶数の配列のパターンを見つけようとすることです。

$$

$$1.1、{\ bf 2}、3.5、{\ bf 8}、13.21、{\ bf 34}、55.89、{\ bf 144}、\ ldots$$

すべての3番目のフィボナッチ数が偶数であり、おそらくすべての偶数が3の倍数の位置にあることがわかるように、偶数がシーケンスにマークされています。これは推測であるため、これを確認して計算アルゴリズムを計算する必要があります。



最良の証明は単純なので、最初に見逃していた単純なアイデアに感謝します。 後続の各フィボナッチ数は前の2つの合計で、前の2つの数が奇数の場合、次は偶数になり、前の2つの数で一方が奇数でもう一方が偶数の場合、次は奇数になります。 原理的には、このアイデアだけですでに実証済みの事実を「直感的に模索」するのに十分です。 帰納法による証明は明らかですが、私はそれをもたらさないように抵抗することはできません



「3番目のフィボナッチ数はすべて偶数であり、そのような各数に先行する2つは奇数であること」を証明します。

• ベース誘導 。 最初の2つのフィボナッチ数 $$$1.1$ -奇数、3番目の数字 $$$2$ -さえ
• 仮説 。 3のフィボナッチ数倍まで、3分の1が偶数で、その前の2つが奇数であると仮定します。
• 誘導ステップ 。 仮説の最後の偶数に続く数は奇数です、なぜなら 奇数と偶数の合計から取得されます。その数の後の次も奇数です。 偶数と奇数の合計から取得され、偶数の次は偶数であるため、 彼のために受け取った2つの前のものは奇妙であり、彼の数は3の倍数であり、それは偶数であり、前の2つは奇数です。

これは、数学的な計算に頼ることなく推測を証明する方法です。 このアイデアを形式化すると同時に、3つごとのフィボナッチ数を計算するための式を取得できます。 $$$F_ {n + 3}$ から $$$F_n$ そして $$$F_ {n + 1}$ 。 再帰関係を使用する $$$F_ {n + 2} = F_ {n + 1} + F_ {n}$ 私達は得る：

$$

$$F_ {n + 3} = F_ {n + 2} + F_ {n + 1} = 2 F_ {n + 1} + F_n$$

だから $$$F_n$ -それでも $$$F_ {n + 3}$ また、この式のおかげで。 それを考えると $$$F_3 = 2$ 、フィボナッチ数の3分の1ごとが本当に偶数であり、推測の一部を裏付けています。 ここでは、他の偶数を見逃さないようにする必要があります。 それらはすべて3の倍数であることがわかりました。彼の単純なアイデアに対するjanatemに感謝します。 $$$F_ {n + 3}$ また、次の場合 $$$F_n$ -奇数 $$$F_ {n + 3}$ また、奇数なので、数字でその数字を取得します $$$3k-2,3k-1、k \ in \ mathbb {N}$ -奇数（誘導により、で始まる $$$F_1 = F_2 = 1$ -奇数）、および $$$3k、k \ in \ mathbb {N}$ -偶数、すべてのフィボナッチ数をカバーします。つまり、すべての偶数をカバーします。



他の偶数がないことを示すことができるため、別の方法があります。 番号が存在すると仮定します $$$F_m$ -そして $$$0 \ not \ equiv m \ mod 3$ それから $$$m = 3k-1$ または $$$m = 3k + 1$ どこで $$$k$ -ある種の自然。



元の投稿からのフィボナッチ数の行列表現を見てみましょう

$$

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

両方の部分の行列式を計算すると、

$$

$$（-1）^ n = F_ {n + 1} F_ {n-1} -F_n ^ 2$$

その結果、数の約数 $$$F_ {n + 1}、F_n$ そして $$$F_ {n-1}、F_n$ マッチディバイダー $$$（-1）^ n$ 、つまり 隣接するフィボナッチ数は相互に単純です。 これはまた、相互の単純さと数字 $$$F_ {3k}、F_ {3k-1}$ そして $$$F_ {3k}、F_ {3k + 1}$ 、つまり $$$F_ {3k}$ そして $$$F_m$ 。 しかし、仮定によって $$$F_m$ -偶数、そして $$$F_ {3k}$ -以前に証明されたように。 それ以外の偶数 $$$F_ {3k}$ どこで $$$k \ in \ mathbb {N}$ フィボナッチ数列には存在しません。 また、隣接するフィボナッチ数が相互に単純であるという興味深い事実を確立しました。



最後に、推測を証明するための少なくとももう1つの方法、ルークの定理を使用する方法を示します。



ルークの定理 。 整数除算 $$$F_m$ 、そして $$$F_n$ 、それが除数である場合にのみ $$$F_d$ どこで $$$d = \ gcd（m、n）$ 特に

$$

$$\ gcd（F_m、F_n）= F _ {\ gcd（m、n）}$$

ここに $$$\ gcd$ 最大の共通要因です。 入れたら $$$m = 3$ それから $$$\ gcd（2、F_n）= F _ {\ gcd（3、n）}$ 。 もし $$$F_n$ -さらに、左側が2であるため、右側も2に等しくなるようにする必要があります。 $$$n$ 3で除算すると同時に、逆も同様です。 したがって、証明したかったものを正確に取得します。



そのため、フィボナッチ数の3分の1は偶数であり、1でも3の倍数です。 私たちはこれを慎重に証明しましたが、誰もそれを疑う勇気はありません。

アルゴリズム

そして今、アルゴリズムを思い付くことが残っています。 あなたは確かにpavellyzhinが元々やったことを行うことができますが、チェックする代わりに $$$0 \ equif F_n \ mod 2$ チェックできます $$$0 \ equin n \ mod 3$ 、これはひねりです！ 確かに、シーケンスフィルターを変更しただけなので、これはアルゴリズムの反復回数には影響しません。 必要なプロパティ（パリティ）を使用して、フィボナッチ数のサブシーケンスをすぐに生成することをお勧めします。したがって、もう1つの明らかな方法は、Binet式を使用することです

$$

$$F_n = \左\ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \右\ rceil、\ qquad n \ in \ {3,6、\ ldots、3k \ ldots \}$$

計算の効率には問題があります。これについては、元の記事で詳しく説明しています。 したがって、私の意見では、最良の方法-反復計算を提案します $$$F_ {n + 3}$ 、これは以前に示したように、式 $$$F_ {n + 3} = 2F_ {n + 1} + F_n$ 。 アルゴリズムで反復遷移を構築するには、計算する必要があります $$$F_ {n + 4}$ 、すべてが同じくらい簡単です

$$

$$F_ {n + 4} = F_ {n + 3} + F_ {n + 2} = 2F_ {n + 1} + F_n + F_ {n + 1} + F_n = 3F_ {n + 1} + 2F_n$$

ところで、一般的に言えば、それを証明するのは簡単です

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n$$

正式には、アルゴリズムは次のように記述されます（現在の偶数フィボナッチ数 $$$F_n$ 続いてフィボナッチ数 $$$F_ {n + 1}$ 、 $$$M$ 問題の状態で与えられた数値の上限です）：

1. $$$F_n \ leftarrow F_3 = 2、\ quad F_ {n + 1} \ leftarrow F_4 = 3$
2. もし $$$F_n> M$ 、それから終了、そうでなければ結果に追加 $$$F_n$
3. $$$（F_n、F_ {n + 1}）\ leftarrow（2F_ {n + 1} + F_n、3F_ {n + 1} + 2F_n）$ ステップ2に進みます。

アルゴリズムは非常に簡単です-フィボナッチ数の3つごとにジャンプして印刷します（それ以上でない場合） $$$M$ ） アルゴリズムの複雑さは依然として線形ですが、ステップ2の繰り返し回数は、範囲内の偶数フィボナッチ数に正確に等しくなります。 $$$1 \ ldots M$ 、比較のために、フィルタリングを使用した単純なアルゴリズムでは、3倍の反復が必要です（見つかったそれぞれに対して、2回の破棄があります）。



アルゴリズムは紙の上にありますが、インタビューは何でしたか、PHP？ さて、最後にPHPの意味を明らかに

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; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注 ：たとえば、ユーザーhunrollが示したように、この方法はいつでも改善できます。 アイデアは、計算のために、部分的に得られた結果を除いて、余分なものを必要としないということです。 前の偶数フィボナッチ数のみを使用して偶数を計算できます。

$$

$$F_ {n + 3} = 2F_ {n + 1} + F_ {n} = 3F_n + 2F_ {n-1} = 3F_n + F_ {n-1} + F_ {n-1} = \\ 3F_n +（ F_ {n-1} + F_ {n-2}）+ F_ {n-3} = 4F_n + F_ {n-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; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一般化

ここでルークの定理に言及しました。 $$$\ gcd（F_m、F_n）= F _ {\ gcd（m、n）}$ 。 その結果、フィボナッチ数を取得できます $$$F_n$ の倍数 $$$F_m$ 、その番号の場合のみ $$$n$ 倍数 $$$m$ 。 つまり 4番目ごとのフィボナッチ数が3で除算され、5番目ごとに5ごと、6番目ごとに8ごとなどです。



次に、簡単な方法で、フィボナッチサブシーケンスを計算するアルゴリズムを取得します。このアルゴリズムでは、要素は特定の数の倍数です $$$F_m$ 。 という事実を使用して

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n \\ F_ {n + m + 1} = F_ {m + 1} F_ {n + 1} + F_mF_n$$

前のアルゴリズムは

1. $$$F_n \左矢印F_m、\クワッドF_ {n + 1} \左矢印F_ {m + 1}$
2. もし $$$F_n> M$ 、それから終了、そうでなければ結果に追加 $$$F_n$
3. $$$（F_n、F_ {n + 1}）\ leftarrow（F_mF_ {n + 1} + F_ {m-1} F_n、F_ {m + 1} F_ {n + 1} + F_mF_n）$ ステップ2に進みます。

どこで $$$F_ {m-1}、F_m、F_ {m + 1}$ 定数として設定できます。



メモの概要 。 ユーザーの無知が正しく指摘されているように、一般化されたケースでは、部分的な結果からの数字のみを使用するアルゴリズムを構築することも可能です。

$$

$$F_ {n + 1} = F_n + F_ {n-1} \\ F_ {n + 2} = 3F_ {n}-F_ {n-2} \\ F_ {n + 3} = 4F_ {n} + F_ {n-3} \\ F_ {n + 4} = 7F_ {n}-F_ {n-4} \\ F_ {n + 5} = 11F_ {n} + F_ {n-5} \\ \ cdots \\ F_ {n + t} =（F_t + 2F_ {t-1}）F_n +（-1）^ {t-1} F_ {nt}$$

t = 1およびt = 2の場合、数学的な帰納法によってこれを証明しましょう。 あるtまで保持すると仮定すると、

$$

$$F_ {n + t + 1} = F_ {n + t} + F_ {n + t-1} = \\（F_t + 2F_ {t-1}）F_n +（-1）^ {t-1} F_ {nt} + \\（F_ {t-1} + 2F_ {t-2}）F_n +（-1）^ {t-2} F_ {n-t + 1} = \\（F_t + F_ { t-1} + 2（F_ {t-1} + F_ {t-2}））F_n +（-1）^ {t-1}（F_ {nt} -F_ {n-t + 1}）= \\（F_ {t + 1} + 2F_t）F_n +（-1）^ {t-1}（F_ {nt} -F_ {nt} -F_ {nt-1}）= \\（F_ {t + 1} + 2F_t）F_n +（-1）^ tF_ {nt-1}$$

合計のようなもの

もちろん、タスクは完全に合成であり、反復回数は非常に少ないです（ $$$M = $ 10,00$ 答えには6つの数字しか含まれていません。 6回の反復が完了し、元の「正面」アルゴリズムには18）が必要でしたが、この方法で、ここで新しい何かを発見したユーザーは、フィボナッチ数のインタビューで少し深い知識を示すことができます。



編集： janatemとAllexInのユーザーの簡単な証明のおかげで、私はそれらを「理論化」に加え、計算で既に得られた偶数のみを使用するアルゴリズムの探索と、それを一般化するためのユーザーの無知に参加しました。