プロジェクトオイラー104.

この記事の所要時間: 34

No. 104 Pandigital Fibonacci ends

問題.

フィボナッチ数列とは次の漸化式によって定義される数列です:

\begin{align*}
F_n &= F_{n-1} + F_{n-2}\\
F_1 &= 1\\
F_2 &= 1.
\end{align*}

113 桁の数である\(F_{541}\) は末尾の 9 桁が 1 から 9 の並べ替えになっているような最初のフィボナッチ数です.

また,575 桁の \(F_{2749}\) は先頭の 9 桁が 1 から 9 までの並べ替えになっている最初のフィボナッチ数です.

では,\(F_k\) が先頭の 9 桁と末尾の 9 桁がそれぞれ 1 から 9 までの並べ替えになっているような最初のフィボナッチ数であるとき,その \(k\) を求めよ.

考え方とプログラム例.(Python3)

フィボナッチ数は添字が大きくなると指数関数的に大きくなっていくので,実際に漸化式に従って \(F_n\) を求めていくことはできません.(先頭がはじめて 1 から 9 の並べ替えになるのが \(F_{2749}\) ですから,この問題の答えはかなり大きな数と考えられます.)

まず,末尾の 9 桁についてですが,これは漸化式を使って末尾の 9 桁だけを計算していく(10 桁を超えたときは 10 桁目以上をすてる)ことで判定できます.

末尾の 9 桁が並べ替えになっているようなものに対してだけ,先頭も並べ替えになっているかを確認していくことにします.

先頭の 9 桁については,先程述べたように漸化式は使えないので,フィボナッチ数の一般項を使います.

\begin{align*}
F_n &= \frac{\phi^n – (1-\phi)^n}{\sqrt{5}}\\
\phi &= \frac{1+\sqrt{5}}{2}
\end{align*}

この一般項の第 2 項 \((1-\phi)^n\) は \(n\) が大きくなるにつれてその絶対値は小さくなっていきます.十分大きな \(n\) のとき,さらには \(F_n\) の先頭の 9 桁のみが必要な今回はこの項を無視しても問題ありません.

すると,

\begin{align*}
F_n \approx \frac{\phi^n}{\sqrt{5}}
\end{align*}

とシンプルな形になるので,高校で習った方法を使って桁数が

\begin{align*}
k = \lfloor\log_{10}{F_n}\rfloor+1
\end{align*}

上位 9 桁を \(X\) とすると

\begin{align*}
\log_{10}{X}\leq \log_{10}{N}-k+9<\log_{10}(X+1)
\end{align*}

となることを利用して求めます.

先頭と末尾の両方が並べ替えになっている数までに,末尾が並べ替えになっているフィボナッチ数は 111 個もありました.

答えはこの下にあります.反転してください.

A. 329468 (pypy で0.26sec.)

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加