負数番のフィボナッチ数を用いた表現
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/05/21 05:07 UTC 版)
「ゼッケンドルフの定理」の記事における「負数番のフィボナッチ数を用いた表現」の解説
フィボナッチ数列は、漸化式を書き換えて F n − 2 = F n − F n − 1 , {\displaystyle F_{n-2}=F_{n}-F_{n-1},\,} F − n = ( − 1 ) n + 1 F n . {\displaystyle F_{-n}=(-1)^{n+1}F_{n}.\,} 任意の整数は、連続したフィボナッチ数を使わない形で負数番のフィボナッチ数の和として一意に表すことができる。例えば −11 = F−4 + F−6 = (−3) + (−8) 12 = F−2 + F−7 = (−1) + 13 24 = F−1 + F−4 + F−6 + F−9 = 1 + (−3) + (−8) + 34 −43 = F−2 + F−7 + F−10 = (−1) + 13 + (−55) 0 は空集合に対する和として表される。 たとえば 0 = F−1 + F−2 であるから、この表現の一意性は連続するフィボナッチ数を用いないという条件に依存している。 この表現によって、ゼッケンドルフの表現と同様に整数を符号化することが可能である(en:NegaFibonacci_coding)。整数 x を表す文字列においては、n 番目の桁は Fn が x を表す和に現れるなら 1, そうでないなら 0 となる。例えば 24 = F−1 + F−4 + F−6 + F−9 であるから 24 は 9, 6, 4, 1 桁目に 1 を置いて 100101001 によって表現できる。整数 x が奇数桁でこのように表されることと、x > 0 であることは同値である。
※この「負数番のフィボナッチ数を用いた表現」の解説は、「ゼッケンドルフの定理」の解説の一部です。
「負数番のフィボナッチ数を用いた表現」を含む「ゼッケンドルフの定理」の記事については、「ゼッケンドルフの定理」の概要を参照ください。
- 負数番のフィボナッチ数を用いた表現のページへのリンク
