問題
，を自然数とする．次の算法を考える．
(a) ，，．
(b) ならばとして終了する．
(c) の値が奇数ならとする．
(d) ．
(e) ．
(f) (b)に戻る．
（ここで，はを越えない最大の整数を表す．）
(1) のとき，3周目と4周目の(b)における，，の値を求めよ．たとえば1周目では，，である．
(2) 一般のに対して，(b)における，，の値については1周目から最後まで一定であることを示せ．
(3) 一般のに対して，を求めよ．
方針
この算法は、 を半分にしながら、奇数部分に対応する を に足していく掛け算の手順である。各周回の(b)に入った時点で を見ると、 が偶数でも奇数でも次の周回で値が変わらない。(1)は実際に周回を追い、(2)は偶奇で場合分けして不変量を証明し、(3)は終了時 で となることから答える。
解答
(1)
1周目の(b)では、問題文の通り である。 は偶数なので は変わらず、 は 、 は になる。したがって2周目の(b)では である。
同様に も偶数なので、3周目の(b)では である。ここで は奇数なので、(c)で となる。その後 、 となるから、4周目の(b)では である。
(2)
ある周回の(b)における値を とする。まず が偶数のとき、(c)では は変わらず、次の周回では である。したがって である。
次に が奇数のとき、 とおく。(c)で は となり、次の周回では である。したがって である。
よって、どちらの場合にも次の周回で は変わらない。したがって は1周目から最後まで一定である。1周目では なので、一定値は である。
(3)
算法が終了するのは(b)で となったときであり、そのとき と定められる。ところが なので である。(2)より は常に に等しいから である。
別解。この算法は、 を2進法で見たときの各桁に応じて を足す操作である。奇数なら現在の を に足し、毎回 を半分、 を2倍にするので、最終的に 個分の が足される。したがって答えは になる。不変量 はこの考えを式で表したものである。