階乗進法

階乗数は、フィボナッチ数と同様に、それをもとにして数を表現することができる。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【８】整数のフィボナッチ数分割

　フィボナッチ数は漸化式

　　Ｆn＝Ｆn-1＋Ｆn-2

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

　　１，１，２，３，５，８，１３，２１，３４，５５，８９，・・・

となる．

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

　　８３＝５５＋２８

　　２８＝２１＋７

　　　７＝５＋２

より，８３＝５５＋２７＋５＋２となる．

　２進法では，８３＝６４＋１６＋２＋１のように隣り合った２のベキ乗がしばしば必要になるが，数のフィボナッチ数分割では，どの２つのフィボナッチ数も隣り合っていないことに注意されたい．「あらゆる正の整数は連続でないフィボナッチ数の和として一意に表記することができる」

　フィボナッチ数系では，

　　　　　３＝３

　　　　　４＝３＋１

　　　　　５＝５

　　　　　６＝５＋１

　　　　　７＝５＋２

　　　　　８＝８

　　　　　９＝８＋１

　　　　１０＝８＋２

　　　　１１＝８＋３

　　　１２＝８＝３＋１

・・・・・・・・・・・

　　１０００＝８９７＋１３

　　・・・・・・・・・・・

１００００００＝８３２０４０＋１２１３９３＋４６３６８＋１４４＋２５＝Ｆ30＋Ｆ26＋Ｆ24＋Ｆ12＋Ｆ10

のように，一般に

　　ｎ＝Ｆk1＋Ｆk2＋・・・＋Ｆkn

で表されるのである（ツェッケンドルフの定理）．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

すべての数は２進法で一意に表すことができる．たとえば，

　　４５＝３２＋８＋４＋１＝２^5＋２^4＋２^2＋２^0

　フィボナッチ数も自然数を一意な和の形に表すことのできる数体系のひとつになっている．たとえば，

　　４５＝３４＋８＋３＝Ｆ9＋Ｆ6＋Ｆ4

　ツェッケンドルフの定理（１９３９年）

　「任意の正の整数は１個もしくは連続しない２個以上のフィボナッチ数の和として一意に表現できる．

　　ｎ＝Ｆk1＋Ｆk2＋・・・＋Ｆkr」

　この定理から２進数に似たフィボナッチ数体系を作ることができる．連続しないフィボナッチ数に限定する理由は，たとえば，

　　Ｆ4＝Ｆ3＋Ｆ2

　　４５＝３４＋８＋２＋１＝Ｆ9＋Ｆ6＋Ｆ3＋Ｆ2

Ｆ4をＦ3＋Ｆ2で置き換えると別の式ができてしまうからである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝