■数のフィボナッチ数分割(その24)

与えられた数を、隣り合わないフィボナッチ数だけの和で表すことを考えます。

このような表現に関して、

どんな自然数に対してもただひとつに定まる(ツェッケンドルフの定理)

ことが知られています。

===================================

ツェッケンドルフ表現は、与えられた数以下の最も大きいフィボナッチ数を探していくだけです(破綻しないアルゴリズム)。

22=21+1

31=21+8+2

43=34+8+1

53=34+13+5+1

77=55+21+1x1

一般にFn<N<Fn+1のとき

N-Fn<Fn+1-Fn<Fn-1

つまり、N-Fn以下の最も大きなフィボナッチ数はFnと隣り合わないフィボナッチ数となります。

===================================