問題
，を自然数とする．次の算法を考える．
(a) ，，．
(b) ならばとして終了する．
(c) の値が奇数ならとする．
(d) ．
(e) ．
(f) (b)に戻る．
（ここで，はを越えない最大の整数を表す．）
(1) のとき，3周目と4周目の(b)における，，の値を求めよ．たとえば1周目では，，である．
(2) 一般のに対して，(b)における，，の値については1周目から最後まで一定であることを示せ．
(3) 一般のに対して，を求めよ．
(4) を自然数とする．のとき，終了するまでに何回(d)を実行するか．
方針
が各周回の(b)で不変であることを示す。 が偶数なら半分にした と2倍した の積は変わらず、 が奇数なら先に に を足すことで失われる1個分を補っている。(4)は を何回半分にすると1になるかを、 まで下がる段階と、その後 になる段階に分けて数える。
解答
(1)
1周目の(b)では である。 は偶数なので、次の周回では となる。さらに も偶数なので、3周目の(b)では である。ここで は奇数なので、(c)で となり、その後 、 となる。したがって4周目の(b)では である。
(2)
ある周回の(b)での値を とする。 が偶数のときは、次の周回で となるから である。 が奇数のときは とおける。(c)で は となり、その後 となる。したがって である。
よって、どちらの場合も は次の周回で変わらない。1周目では だから、最後まで一定値は である。
(3)
終了時は(b)で となっており、 と定められる。このとき である。(2)より だから である。
(4)
から始める。 が偶数である間は、(d)を1回行うごとに は半分になる。したがって(d)を 回行うと となる。次に は奇数なので、(c)を行った後、(d)で となる。この次に(b)へ戻ると終了する。
したがって(d)を実行する回数は である。
別解。(4)は床関数を順に書いてもよい。 は 回の半減で になり、さらに で終了条件に達する。 になった後は(b)で終了するので、追加の(d)は行われない。