ここでは最大公約数を数列の総和にて表示する。ただしこの表示によって、計算量の減少や、なにかふかーい事実が得られるというわけではない。ただ、この和表示によってなにかしらの一つの新しい解釈が得られることは保証されよう(もしも既に知っていることだったら・・・う~ん残念!)。
ここでは級数表示のために使うあるアイディアを紹介する。おそらく多くの人が最大公約数と結びつけたことのない話題であろう。
格子点同士を結ぶ直線を考える(面倒くさいからExcelで撮影)。
Line
このときに、直線がいくつの正方形を通っているか、一度は考えたことがあるだろう。
LineBlock
これを具体的な式で表すことが今回の肝である。
直線が通る正方形の数を考えるときに、直線がいくつの格子点を通るかが重要となる。
ただし直線は垂直や水平でないものとする。
ここで直線と、格子の線の交点に注目する
LinePoints
小さい丸は格子の線と一回交わっている場所、大きな丸は格子点で交わっている場所を表している。
左上から右下まで直線をゆっくりたどっていこう。
このように見てみると、あることが分かってくる。赤い丸である交点は、直線が通る隣り合う正方形と正方形の間に位置しているのだ。したがって、植木算より
「交点の個数
と分かる。じゃあ交点の個数は?これは直線の始点と終点の間にある、縦線と横線の個数に関係がある。小さい赤い丸の点では線と一回交わっている。一方で大きな赤い丸の点は格子点なので、縦線と横線両方に交わっている。だから
「交点の個数
となる。ここで
となる。すると正方形の数は
と表される。
図の例では
より、
ちなみにこの式を
正方形の個数は求まった。でも考えてみてほしい。直線の通る正方形(図の黄色い部分)の個数を、一列ごとに足していけばいいのではないだろうか。
LineBlockSum
ここでやっと直線の式の出番だ。
LineBlockUnder
茶色のブロックは、
そして直線の上側のブロック数も、下側のブロック数と同じである。よって、直線の通るブロック数は、
である。ただし、
もしくは、黄色のブロックを直接求めることも可能だ。すなわち
道具の解説も終わったので、ついに和表示の導出である。とはいっても、直線の通る正方形の個数の表示式
を使うとばすぐ導出できる:
これは
と一致している。また、この式に
を適用することで
と証明ができる。
先ほどの和表示は次の関係式を用いることで、一応拡張することができる
でもこれだと式がめっちゃ汚くなる。そこで先ほどのアイディアが使えないかと考えてみる。
しかし問題は、どうしても立方体の個数を和表示できないのだ。おそらくはこの方針では解決不能であり、新しいアイディアが必要である。もしくは、和表示は