今回のコラムでは，破綻するアルゴリズムの例として数の平方数分割を，破綻しないアルゴリズムの例として数のフィボナッチ数分割を取り上げます．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】数の平方数分割
任意の整数ｎは，ｎ個の平方和
ｎ＝１^2＋１^2＋・・・＋１^2
に書けますから，これをなるべく少ない数の平方和でｎを表そうと思うのは自然な成り行きです．そこでまず，簡単な数値実験から始めることにしましょう．１から１０までの整数をいくつかの平方数の和の形式で表現するというものです．
整数の平方
０，１，４，９，１６，２５，・・・
は非常にまばらにしか存在しませんが，２つの平方数の和の形で表される整数はより頻繁に現れます．１，２，４，５，８，９，１０，・・・
１＝１^2＋０^2
２＝１^2＋１^2
４＝２^2＋０^2
５＝２^2＋１^2
８＝２^2＋２^2
９＝３^2＋０^2
１０＝３^2＋１^2
ここで，３，６，７といった整数は，２つの平方の和では書けないことがわかります．しかし，３つの平方和となると幾分間隙を埋めてくれます．
３＝１^2＋１^2＋１^2
６＝２^2＋１^2＋１^2
それでも，なおすべての正の整数を得ることはできません．最後まで残った７に対しては３つの平方数の和で書けず，４つの平方数が必要となります．
７＝２^2＋１^2＋１^2＋１^2
このような数値実験からいくつかのことが予想されます．たとえば「すべての正の整数は，ｇ個の平方数の和として表すことができるだろうか？ さらに，ｇの最小値はいくつであろうか？」というより高度な問題が派生しますが，「すべての正の整数は高々４個の整数の平方和で表される」というのが，ラグランジュの定理です．
驚くべきことに，７のみならず，任意の自然数がたった４つの平方数の和の形に表せるのです．
７＝２^2＋１^2＋１^2＋１^2
２＝１^2＋１^2＋０^2＋０^2
このことを，シンボリックに書くと
ｎ＝□＋□＋□＋□
となります．□は平方数の意味です．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】アルゴリズムの破綻
２次形式の問題は，ｎ次元空間における格子点の配置の問題として幾何学的に考えることができます．すなわち，ラグランジュの定理は４次元空間内の原点を中心とする半径√ｎの球面には必ず格子点があることを主張しているわけです．半径√ｎの２次元の円，３次元の球には格子点が存在するとは限らないのです．
上の数値実験では，実際に４個必要なのは７だけで，他はすべて３個以下の平方数の和で書けていました．どの場合に２つで済むのか，３つで済むのか？という問題は，ラグランジュの定理に先行するフェルマー・オイラーの定理，オイラー・ルジャンドルの定理で解決されています．
また，ｎを越えない最大の平方数は，ガウス記号を用いて［√ｎ］^2と表せるのですが，ｎを越えない最大の平方数をとり，その残りに対して同様に最大の平方数をとる，・・・，そして残りが平方数になるとおしまいというアルゴリズムによって，４個の平方数の和
ｎ＝ｎ1^2＋ｎ2^2＋ｎ3^2＋ｎ4^2
に分解できるように思われます．はたして，これは正しいのでしょうか？ 数値実験を続けてみることにします．
１１＝３^2＋１^2＋１^2
１２＝３^2＋１^2＋１^2＋１^2
１３＝３^2＋２^2
１４＝３^2＋２^2＋１^2
１５＝３^2＋２^2＋１^2＋１^2
１６＝４^2
１７＝４^2＋１^2
１８＝４^2＋１^2＋１^2
１９＝４^2＋１^2＋１^2＋１^2
２０＝４^2＋２^2
２１＝４^2＋２^2＋１^2
２２＝４^2＋２^2＋１^2＋１^2
２３＝４^2＋２^2＋１^2＋１^2＋１^2
素数２３では５個の平方和となり，このアルゴリズムは２３で破綻してしまいます．もちろん，２３は８ｎ＋７型の素数ですから，３個の平方和では表すことはできませんが，
２３＝３^2＋３^2＋２^2＋１^2
のように４個の平方和の形に表すことができます．
また，
１２＝３^2＋１^2＋１^2＋１^2＝２^2＋２^2＋２^2
１８＝４^2＋１^2＋１^2＝３^2＋３^2
１９＝４^2＋１^2＋１^2＋１^2＝３^2＋３^2＋１^2
２３＝４^2＋２^2＋１^2＋１^2＋１^2＝３^2＋３^2＋２^2＋１^2
のように，より少ない数の平方和として幾通りかに表すことのできる数もあります．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【３】数の三角数分割
数の三角数分割（ガウス，１７９６年）
ｎ＝△＋△＋△，△＝ｋ（ｋ＋１）／２
すなわち「すべての整数は３つの三角数の和によって表し得る」についての同様の問題は，読者の演習問題とします．
７＝３＋３＋１＝６＋１＋０
８＝６＋１＋１
９＝３＋３＋３＝６＋３＋０
１０＝６＋３＋１
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【４】数のフィボナッチ数分割
フィボナッチ数は漸化式
Ｆn＝Ｆn-1＋Ｆn-2
に従って，その前の２つの数の合計として順次計算することができて，
１，１，２，３，５，８，１３，２１，３４，５５，８９，・・・
となる．
任意の正の整数ｎは，それを超えない最大のフィボナッチ数と余りに分割されるが，このとき余りもそれを超えない最大のフィボナッチ数と余りに分割され，任意の正の整数ｎは一意的に表すことができる．たとえば，
８３＝５５＋２８
２８＝２１＋７
７＝５＋２
より，８３＝５５＋２７＋５＋２となる．
２進法では，８３＝６４＋１６＋２＋１のように隣り合った２のネキ乗がしばしば必要になるが，数のフィボナッチ数分割では，どの２つのフィボナッチ数も隣り合っていないことに注意されたい．
フィボナッチ数系では，
３＝３
４＝３＋１
５＝５
６＝５＋１
７＝５＋２
８＝８
９＝８＋１
１０＝８＋２
１１＝８＋３
１２＝８＝３＋１
・・・・・・・・・・・
１０００＝８９７＋１３
・・・・・・・・・・・
１００００００＝８３２０４０＋１２１３９３＋４６３６８＋１４４＋２５＝Ｆ30＋Ｆ26＋Ｆ24＋Ｆ12＋Ｆ10
のように，一般に
ｎ＝Ｆk1＋Ｆk2＋・・・＋Ｆkn
で表されるのである（ツェッケンドルフの定理）．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝