Puzzle DE Programming / フィボナッチ数

パズルの説明

フィボナッチ (fibonacci) 数はイタリアの数学者レオナルド・フィボナッチにちなんで名付けられた数です。今回はフィボナッチが考案したウサギの問題を解いてみましょう。

[問題]

１つがいのウサギがいます。ウサギは１ヶ月経つと１つがいの子ウサギを生みます。生まれたウサギは２ヶ月目には子ウサギを生むものとします。ウサギは死なないものとすると、１年後にウサギは何つがいになるでしょうか。

●解答

ウサギを親、子、生まれたウサギに分けて表を作ると次のようになります。

   : 親 : 子 : 生 :  計
---+----+----+----+-----
 0 :  1 :  0 :  0 :   1
 1 :  1 :  0 :  1 :   2
 2 :  1 :  1 :  1 :   3
 3 :  2 :  1 :  2 :   5
 4 :  3 :  2 :  3 :   8
 5 :  5 :  3 :  5 :  13
 6 :  8 :  5 :  8 :  21
 7 : 13 :  8 : 13 :  34
 8 : 21 : 13 : 21 :  55
 9 : 34 ; 21 : 34 :  89
10 : 55 : 34 : 55 : 144
11 : 89 : 55 : 89 : 233
12 :144 : 89 :144 : 377

１月に子ウサギを生むとすると、答えは 377 つがいになります。１月に子を生まない (まだ親ウサギになっていない) とすると 233 つがいになります。\(F_n\) を n ヵ月後のつがいの数とすると、\(F_n = F_{n-1} + F_{n-2}\) の関係が成立していることがわかります。数学では、次の漸化式で生成される数列を「フィボナッチ数列」といいます。

\(\begin{array}{l} F(0) = 0 \\ F(1) = 1 \\ F(n) = F(n - 1) + F(n - 2) \quad \mathrm{if} \ n \gt 1 \end{array}\)

フィボナッチ数列は 0, 1, 1, 2, 3, 5, 8, 13 .... という直前の 2 項を足していく数列になります。

●問題

それでは、ここで問題です。

300,000,000 未満で最も大きいフィボナッチ数 \(F_n\) を求めてください。
初項 \(F_0\) から n 番目までのフィボナッチ数の和 \(F_0 + F_1 + F_2 + \cdots + F_n\) を考えます。300,000,000 未満のフィボナッチ数の総和を求めてください。
300,000,000 未満のフィボナッチ数で、偶数になる項の総和を求めてください。
300,000,000 を 1 つ以上の連続しない相異なるフィボナッチ数の和として表してください。たとえば、7 = 1 + 1 + 2 + 3 と表すことができますが、1 を 2 回使っていることと、1, 2, 3 は連続したフィボナッチ数 \((F_2, F_3, F_4)\) なので条件を満たしていません。7 = 2 + 5 とすると条件を満たします。

●解答１

フィボナッチ数を求めるプログラムは簡単です。Python3 (ver 3.8.10) でプログラムすると次のようになります。

リスト : フィボナッチ数

def fibo(n):
    a1, a2 = 0, 1;
    for _ in range(n):
        a1, a2 = a2, a1 + a2
    return a1

def solver1():
    i = 0
    while True:
        if fibo(i) >= 300000000: break
        i += 1
    print(i-1)
    print(fibo(i-1))

>>> solver1()
42
267914296

答えは F₄₂ = 267914296 になります。また、次のようにメモ化関数を使うと二重再帰のプログラムでも高速に求めることができます。

リスト : メモ化関数

def memoize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def fibo2(n):
    if n < 2:
        return n
    else:
        return fibo2(n - 2) + fibo2(n - 1)

メモ化関数については、拙作のページ Algorithms with Python: 「再帰定義」をお読みくださいませ。

さらに、次の公式を使うと筆算でも簡単に求めることができます。参考 URL 『フィボナッチ数 - Wikipedia』によると、フィボナッチ数は次の近似式で求めることができるそうです。

\(\begin{array}{l} F_n = \dfrac{\varphi^n}{\sqrt 5} \\ \varphi = \dfrac{1 + \sqrt 5}{2} \end{array}\)

したがって、n は次の式で求めることができます。

\( n = \left\lfloor\dfrac{\log {(F_n \times \sqrt 5)}}{\log \varphi}\right\rfloor \)

>>> from math import *
>>> phi = (1 + sqrt(5)) / 2
>>> phi
1.618033988749895
>>> floor(log(300000000 * sqrt(5)) / log(phi))
42

参考 URL 『フィボナッチ数 - Wikipedia』によると、上記近似式の誤差は 0.5 未満になるとのことなので、フィボナッチ数は次の式で求めることができます。

\( F_n = \left\lfloor\dfrac{\varphi^n}{\sqrt 5} + 0.5\right\rfloor \)

>>> floor(phi ** 42 / sqrt(5) + 0.5)
267914296

●解答２

Python3 の場合、内包表記を使うと簡単です。

>>> sum([fibo(x) for x in range(43)])
701408732

次の公式を使うともっと簡単に和を求めることができます。

\( F_{1} + F_{2} + \cdots + F_{n} = F_{n+2} - 1 \)

各項を \(F_n = F_{n+2} - F_{n+1}\) の関係を使って書き直すと次のようになります。

\(\begin{array}{l} F_{1} = F_{3} - F_{2} \\ F_{2} = F_{4} - F_{3} \\ F_{3} = F_{5} - F_{4} \\ \quad \cdots \cdots \\ F_{n-2} = F_{n} - F_{n-1} \\ F_{n-1} = F_{n+1} - F_{n} \\ F_{n} = F_{n+2} - F_{n+1} \\ \hline \displaystyle \sum_{i=1}^n F_{n} = F_{n+2} - F_{2} = F_{n+2} - 1 \end{array}\)

答えは \(F_{44} - 1\) になります。

>>> floor(phi ** 44 / sqrt(5) + 0.5) - 1
701408732

ご参考までに、偶数番目の項の総和と基数番目の項の総和の公式を示します。

\(\begin{array}{l} F_{2} + F_{4} + \cdots + F_{2n} = F_{2n+1} - 1 \\ F_{1} + F_{3} + F_{5} + \cdots + F_{2n-1} = F_{2n} \end{array}\)

これらの公式は項 \(F_n\) を \(F_{n-2} + F_{n-1}\) に書き換えると求めることができます。

\( (F_{0} + F_{1}) + (F_{2} + F_{3}) + (F_{4} + F_{5}) + \cdots + (F_{2n-2} + F_{2n-1}) = F_{2n+1} - 1 \quad \) (\(F_{2n-1}\) までの総和)

\( F_{1} + (F_{1} + F_{2}) + (F_{3} + F_{4}) + \cdots + (F_{2n-3} + F_{2n-2}) = F_{2n} \quad \) (\(F_{2n-2}\) までの和 + \(F_{1}\))

●解答３

フィボナッチ数列は \(F_{1}\) = 1 (奇), \(F_{2}\) = 1 (奇) なので、\(F_{3}\) = 1 (奇) + 1 (奇) = 2 (偶), \(F_{4}\) = 1 (奇) + 2 (偶) = 3 (奇), \(F_{5}\) = 2 (偶) + 3 (奇) = 5 (奇), \(F_{6}\) = 3 (奇) + 5 (奇) = 8 (偶) になります。つまり、n が 3 の倍数のとき項の値は偶数になるわけです。

この性質を利用すると、偶数となる項の総和は次のように求めることができます。

>>> sum([fibo(x) for x in range(43) if x % 3 == 0])
350704366

偶数の項の総和を求める公式は、次のように導出することができます。

\(S = F_{3} + F_{6} + \cdots + F_{3(n-1)} + F_{3n}\) とし、
各項を \(F_{n} = F_{n-2} + F_{n-1}\) の関係を使って書き直すと

\( S = (F_{1} + F_{2}) + (F_{4} + F_{5}) + \cdots + (F_{3n-2} + F_{3n-1}) \)

足し算すると

\(\begin{eqnarray} 2S &=& F_{1} + F_{2} + F_{3} + \cdots + F_{3n-2} + F_{3n-1} + F_{3n} \\ &=& F_{3n+2} - 1 \\ S &=& \dfrac{F_{3n+2} - 1}{2} \end{eqnarray}\)

このように、\(F_{3n}\) までの偶数項の総和は \(F_{3n}\) までの総和の半分になります。

(floor(phi ** 44 / sqrt(5) + 0.5) - 1) / 2
350704366.0

●解答４

参考 URL 『ゼッケンドルフの定理 - Wikipedia』によると、『ゼッケンドルフの定理は、任意の正の整数が、連続するフィボナッチ数を含まないような形で、相異なる 1 つ以上のフィボナッチ数の和として一意に表現できるというものである。』とのことです。これを「ゼッケンドルフの表現」と呼ぶそうです。正整数 N のゼッケンドルフの表現は、『各段階で可能な最大のフィボナッチ数を選ぶ貪欲法によって得ることができる。』そうです。

これをそのまま単純にプログラムすると次のようになります。

リスト : ゼッケンドルフの表現

def solver4(n):
    def max_fibo(n):
        i = 1
        while fibo(i) <= n: i += 1
        return fibo(i - 1)

    print(n, ":", end=' ')
    while n > 0:
        x = max_fibo(n)
        print(x, end=' ')
        n -= x
    print()

>>> solver4(300000000)
300000000 : 267914296 24157817 5702887 2178309 46368 233 89 1

局所関数 max_fibo() で n 以下の最大のフィボナッチ数を求めます。あとは、max_fibo() でフィボナッチ数を求め、それを n から引き算していくだけです。

●参考 URL

１－１４．ねずみ算とフィボナッチ数列, パズル遊びへの招待・オンライン版, (高木茂男氏)
フィボナッチ数を極める, 私の備忘録
フィボナッチ数 - Wikipedia
ゼッケンドルフの定理 - Wikipedia

Puzzle DE Programming

数字のパズル : フィボナッチ数