■フィボナッチ・ゲーム(その8)

 フィボナッチ数は漸化式

  Fn=Fn-1+Fn-2

に従って,その前の2つの数の合計として順次計算することができて,

  1,1,2,3,5,8,13,21,34,55,89,・・・

となる.

 任意の正の整数nは,それを超えない最大のフィボナッチ数と余りに分割されるが,このとき余りもそれを超えない最大のフィボナッチ数と余りに分割され,任意の正の整数nは一意的に表すことができる.たとえば,

  83=55+28

  28=21+7

   7=5+2

より,83=55+27+5+2となる.

 2進法では,83=64+16+2+1のように隣り合った2のネキ乗がしばしば必要になるが,数のフィボナッチ数分割では,どの2つのフィボナッチ数も隣り合っていないことに注意されたい.

 フィボナッチ数系では,

     3=3

     4=3+1

     5=5

     6=5+1

     7=5+2

     8=8

     9=8+1

    10=8+2

    11=8+3

   12=8=3+1

・・・・・・・・・・・

  1000=897+13

  ・・・・・・・・・・・

1000000=832040+121393+46368+144+25=F30+F26+F24+F12+F10

のように,一般に

  n=Fk1+Fk2+・・・+Fkn

で表されるのである(ツェッケンドルフの定理).

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