前回の記事で書いた「硬貨3種類の Change-Making Problem（お釣り生成問題）を解く計算量 log オーダーのアルゴリズム」の解説です。

注意

この証明は有識者のレビューを受けたものではありません。
タイポや論理の間違いがないか疑いつつ読んでください。

編集履歴

• 2024年11月24日: 証明を書き始めた
• 2026年2月8日: 書きかけだった証明を簡略化できそうなので大幅に書き換えて証明の道筋を書いた
• 2026年2月11日: 一通り証明を書いた

準備

変数

$u_1, u_2, n, a_i, p_i, q_i, r_i$ などの表記は前回の記事と同様に使います。

$y$ は $u_1$ の枚数、$z$ は $u_2$ の枚数、$x$ は $u_3(=1)$ の枚数を表すのに使います。
並びが $x,y,z$ でも $z,y,x$ の順でもないのはアルゴリズムを模索する際に $n$ を $u_1$ で割った余り $x$ と商の $y$ の $XY$座標上で考えたことの名残りです。

特に断り書き等がない限り変数は非負の整数を表します。

定義

合計枚数、合計金額、和

$V = (v_1,v_2,v_3)$ と $W = (w_1,w_2,w_3)$ に対して　
$\lvert V \rvert = v_1 + v_2 + v_3$
$||V|| = u_1 v_1 + u_2 v_2 + u_3 v_3$
$V + W = (v_1+w_1,v_2+w_2,v_3+w_3)$
と定義する.

$|V + W| = |V| + |W|$
$||V + W|| = ||V|| + ||W||$
が成り立つ.

$v_1,v_2,v_3$ はそれぞれ $u_1,u_2,u_3$ の使用枚数を、
$|V|$ は合計枚数を、$||V||$ は合計金額を意味する.

※ $||V||$ という記法は本記事独自の記法であり一般的なものではありません。

部分、差

$V = (v_1,v_2,v_3)$ と $W = (w_1,w_2,w_3)$ に対して　
$v_1 \ge w_1$ かつ $v_2 \ge w_2$ かつ $v_3 \ge w_3$ のとき
$V \supset W$ と書く.

$V \supset W$ のとき
$V - W = (v_1-w_1,v_2-w_2,v_3-w_3)$

と定義する.

辞書順

$V$ が辞書順で $W$ より大きいとき $V \gt W$ と書く.
例えば $(1,0,1) \gt (0,2,0)$ である.

等しいときも含めるときは $V \ge W$ と書く.

適している

$|V| \lt |W|$ または $|V| = |W|$ かつ $V \gt W$ であるとき
$V \sqsupset W$ と書き、$V$ は $W$ より適しているという.
例えば $(1,0,1) \sqsupset (0,2,0) \sqsupset (1,1,1)$ である.

これは合計枚数が少ないほどよく、同じ枚数のときは辞書順で大きいほどよいということを意味する.

等しいときも含めるときは $V \sqsupseteq W$ と書く.

表現、最適表現

$n = ||V||$ であるとき $V$ は $n$ の表現、
$n$ の表現の中で関係 $\sqsupset$ の順で最も適しているものを $n$ の最適表現
と呼ぶことにする.

例えば硬貨が $11, 6, 1$ の 3種類のとき
$(0,0,12), (0,1,6), (0,2,0), (1,0,1)$ が $12$ の表現のすべて、
$(1,0,1)$ が $12$ の最適表現である.

$(0,2,0) と (1,0,1)$ はどちらも最小の合計枚数だが $(0,2,0) \sqsubset (1,0,1)$ なので $(1,0,1)$ の方が最適表現である.

$V$ が $||V||$ の最適表現であるとき、単に $V$ は最適表現であるという.

関数 Q, R

$n$ を $u_1$ で割った商と余りを $Q(n)$ と $R(n)$ と書くことにする.
（$n$ は負でも定義する.例えば $u_1$ が $3$ のとき $Q(-5）= -2,\ R(-5) = 1$）

$Q(n)\ u_1 + R(n) = n$ が成り立つので
$||(Q(n),\ 0,\ R(n))|| = n$

$||(Q(p u_2),\ 0,\ R(p u_2))|| = p u_2 = ||(0,p,0)||$

$m \le n$ ならば $Q(m) \le Q(n)$

アルゴリズムの正当性の証明

いよいよ証明に入ります。

補題1

$V \subset W$ のとき $W$ が最適表現ならば $V$ も最適表現である.

また $W - V$ は $||W|| - ||V||$ の最適表現である.

以下の証明は David Pearson の A polynomial-time algorithm for the change-making problem の Lemma 1 の証明を参考にしています。

証明

$|V + D| = |V| + |D|,\ |W + D| = |W| + |D|$ なので
$|V| \lt |W|$ と $|V + D| \lt |W + D|$ が同値なことがわかる.

$v_i \lt w_i$ と $v_i + d_i \lt w_i + d_i$ が同値なので
辞書順の $V \lt W$ と $V + D \lt W + D$ が同値なことがわかる.

よって
$V \sqsubseteq W$ と $V + D \sqsubseteq W + D$ が同値なことがわかる.

$V$ が最適表現であることを示すには $||V||$ の任意の表現 $V'$ に対して $V' \sqsubseteq V$ であることを示せばよい.

$D = W - V$ とする.
$V \subset W$ なので $D$ の各成分は非負であることに注意する.

$V'$ を $||V||$ の任意の表現とすると $||V'|| = ||V||$.
$||D + V'|| = ||W|| - ||V|| + ||V'|| = ||W||$ なので
$D + V'$ は $||W||$ の表現である.
$W$ は最適表現だったので $D + V' \sqsubseteq W$
$W = W - V + V = D + V$ なので $D + V' \sqsubseteq D + V$
よって $V' \sqsubseteq V$

$W - V \subset W$ なので $W -V$ も最適表現である.
また $||W -V|| = ||W|| - ||V||$ なので$W -V$ は $||W|| - ||V||$ の最適表現である.

【証明終わり】

この補題から、金額 $n$ の最適表現の部分となる表現 $V$ を見つけることができれば、 $n$ の最適表現を求める問題をより金額の小さい $n - ||V||$ の最適表現を求める問題に帰着できることがわかります。

補題2

$(y,z,x)$ が $n$ の最適表現のとき $R(z u_2) \le R(n)$ である.

証明

$z = 0$ のときは $R(z u_2) = 0 \le R(n)$ と成り立つので
以降は $z \gt 0$ の場合で考える.

背理法を用いる. $R(z u_2) \gt R(n)$ と仮定する.
このとき $x \ge u_1 - R(z u_2)$ であることが導かれる.
なぜなら $x \lt u_1 - R(z u_2)$ と仮定すると

\begin{aligned}
R(n) = R(z u_2 + x) = R(z u_2) + x \ge R(z u_2)
\end{aligned}

となり $R(z u_2) \gt R(n)$ に矛盾する.
$x \ge u_1 - R(z u_2)$ なので $(0,z,u_1 - R(z u_2)) \subset (y,z,x)$ が成り立ち
$(y,z,x)$ は最適表現なので、補題1より $(0,z,u_1 - R(z u_2))$ は最適表現である.

$z u_2 + (u_1 - R(z u_2))$ は $u_1$ の倍数なので、これを $y' u_1$ と表すと
$||(y',0,0)|| = ||(0,z,u_1 - R(z u_2))||$

次に、両表現の枚数を比較する.

\begin{aligned}
|(y',0,0)|\ u_1
&= y' u_1 \\
&= z u_2 + (u_1 - R(z u_2)) \\
&\lt z u_1 + (u_1 - R(z u_2))\ u_1 （なぜなら z \gt 0, 1 \lt u_2 \lt u_1）\\
&= (z + (u_1 - R(z u_2)))\ u_1 \\
&= |(0,z,u_1 - R(z u_2))|\ u_1
\end{aligned}

したがって $|(y',0,0)| \lt |(0,z,u_1 - R(z u_2))|$
これは $(y',0,0)$ の方が $(0,z,u_1 - R(z u_2))$ より適していることになり
$(0,z,u_1 - R(z u_2))$ が最適表現であることに矛盾する.
ゆえに背理法の仮定は誤りであり $R(z u_2) \le R(n)$ が成り立つ.

【証明終わり】

補題3

$(y,z,x)$ は最適表現で $z \gt 0$ とする.

このとき $0 \lt p \le z$ であるすべての $p$ に対して $Q(p u_2) + R(p u_2) \gt p$ が成り立つ.

証明

$p \le z$ なので $(0,p,0) \subset (y,z,x)$
$(y,z,x)$ は最適表現なので補題1より $(0,p,0)$ も最適表現である.

ここで、$(0,p,0)$ と金額が等しい別の表現 $(Q(p u_2), 0, R(p u_2))$ を考える.
$(0,p,0)$ は最適表現なので以下のどちらかが成立する.
条件1. $|(Q(p u_2), 0, R(p u_2))| \gt |(0,p,0)|$
条件2. $|(Q(p u_2), 0, R(p u_2))| = |(0,p,0)|$ かつ $(Q(p u_2), 0, R(p u_2)) \le (0,p,0)$

条件2はありえないことを示す. 条件2だったとすると
$(Q(p u_2), 0, R(p u_2)) \le (0,p,0)$ より $Q(p u_2) = 0$
これと $|(Q(p u_2), 0, R(p u_2))| = |(0,p,0)|$ より $R(p u_2) = p$
よって $p u_2 = Q(p u_2)\ u_1 + R(p u_2) = 0\ u_1 + p = p$
これは $u_2 \gt 1$ に矛盾.

したがって条件1の $|(Q(p u_2), 0, R(p u_2))| \gt |(0,p,0)|$ の方が成り立つ.
すなわち $Q(p u_2) + R(p u_2) \gt p$ が成り立つ.

【証明終わり】

次の補題は当たり前に思えますが念のため証明もつけて。

補題4

$(y,0,x)$ が $n$ の最適表現のとき $y = Q(n), x = R(n)$ である.
すなわち、$(Q(n), 0, R(n))$ が $n$ の最適表現である.

$u_2$ の使用枚数が $0$ ということは $u_1$ と $u_3(=1)$ しか使わないので $u_1$ を貪欲に使うのが最適ということを意味している.

証明

まず $x \lt u_1$ を示す.
もし $x \ge u_1$ とすると $(0,0,u_1) \subset (y,0,x)$ なので補題1より $(0,0,u_1)$ も最適表現である.
しかし $||(0,0,u_1)|| = u_1$ の別の表現 $(1,0,0)$ と比べると
$|(0,0,u_1)| = u_1 \gt 1 = |(1,0,0)|$ なので
$(0,0,u_1)$ が最適表現ということに矛盾する.

したがって $n = ||(y,0,x)|| = y u_1 + x\ (0 \le x \lt u_1)$
一方 $n = Q(n) u_1 + R(n)\ (0 \le R(n) \lt u_1)$
なので商と余りの一意性から $y = Q(n), x = R(n)$.

【証明終わり】

補題5 p_i, q_i, r_i の性質

改めて $p_i, q_i, r_i$ の定義を書いておくと

\begin{aligned}
初期値 \\
&r_0 = u_1,\ p_0 = 0,\ q_0 = 1 （a_0 は定義しない）\\
&r_1 = u_2,\ p_1 = 1,\ q_1 = 0 \\
\\
漸化式 \\
&a_i = r_{i-1} を r_i で割った商 \\
&r_{i+1} = r_{i-1} を r_i で割った余り \\
&（つまり r_{i-1} = a_i r_i + r_{i+1} という関係） \\
&p_{i+1} = a_i p_i + p_{i-1} \\
&q_{i+1} = a_i q_i + q_{i-1} \\
\\
終了条件 \\
&r_{i-1} が r_i で割り切れたところで終わりとし、そのときの i を l で表す 
\end{aligned}

さらにこの記事では $r_i, p_i, q_i$ の添数を $l+1$ まで拡張して

\begin{aligned}
&r_{l+1} = 0 \\
&p_{l+1} = p_{l-1} + a_l p_l \\
&q_{l+1} = q_{l-1} + a_l q_l \\
&a_{l+1} は定義しない
\end{aligned}

とする。

以下の性質を持つ.

(i) $1 \le i \le l+1$ のとき

\begin{aligned}
&r_i は狭義単調減少、p_i と q_i は狭義単調増加 \\
&p_i \gt q_i
\end{aligned}

(ii) $0 \le i \le l+1$ のとき

\begin{aligned}
p_i u_2 - q_i u_1 = (-1)^{i+1} r_i
\end{aligned}

(iii) $1 \le i \le l$ のとき

\begin{aligned}
p_{i-1} q_i - p_i q_{i-1} = (-1)^i \\
\end{aligned}

(iv) $0 \le i \le l, 0 \le j \le a_{i+1}$ で $i = 0\ かつ\ j = 0$ 以外のとき

\begin{aligned}
&Q((p_i + j p_{i+1}) u_2) = q_i + j q_{i+1} \\
&R((-1)^{i+1} (p_i + j p_{i+1}) u_2) = r_i -j r_{i+1}
\end{aligned}

(v)

\begin{aligned}
& r_l は u_1 と u_2 の最大公約数 \\
&p_{l+1} = u_1 / r_l \\
&q_{l+1} = u_2 / r_l \\
&Q(p_{l+1} u_2) = u_2 / r_l \\
&R(p_{l+1} u_2) = 0
\end{aligned}

これらの性質は拡張ユークリッドの互除法や連分数で検索すると見つかると思いますので証明は省略します。
帰納法を使って自力でも証明できると思います。

命題6

$A$ は $p_{l+1}$ より小さい与えられた整数で $0 \lt s \le A$ とするとき
$R(s u_2)$ の最小値を与える $s$ の整数値は

\begin{aligned}
& k \ge 1 \\
&s = p_{2k-1} + i p_{2k} \le A \lt p_{2k-1} + (i+1) p_{2k}, 0 \le i \lt a_{2k}
\end{aligned}

となる $s$ のときのみである.

この命題は初等整数論講義（高木貞治）の 定理2.8の第二

$ω$は与えられた無理数、$A$は与えられた整数で $0 \lt x \le A$ とするとき
もしも、$ωx-y$ の正（または負）の値のみを考察するならば、
$ωx-y$ の最小絶対値を与える $x,y$ の整数値は $ω$の奇数（または偶数）番号の主なる近似分数およびその中間近似分数 $r/s$ の中で $A$ を超えない最大分母を有するものの分母、分子である。
すなわち $x = s, y = r$ で
$s = q_{n-1} + λ q_n \le A \lt q_{n-1} + (λ+1) q_n, 0 \le λ \lt k_n$
$ω$の奇数（または偶数）番号の主なる近似分数およびその中間近似分数 $r/s$ の中で $A$ を超えない最大分母を有するものの分母、分子である。

を $ω$ が有理数 $u_2/u_1$のとき用に焼き直したものになります。（$A$ の使い方も初等整数論講義では $q$用に使っていますがこちらの命題では $p$用に変更しています）

数論的な命題なので証明は記事の最後に行うこととし、ここではこの事実を認めて先へ進みます。

補題7

$0 \lt z \lt p_{2k-1} + j p_{2k},\ 2 \le 2k \le l,\ 0 \lt j \le a_{2k}$ のとき

\begin{aligned}
R(z u_2) \ge r_{2k-1} - (j-1)\ r_{2k}
\end{aligned}

が成り立つ.

証明

$0 \lt z \lt p_{2k-1} + j p_{2k}$ は
$0 \lt z \le p_{2k-1} + j p_{2k} - 1$ と同値.
命題6 を $A = p_{2k-1} + j p_{2k} - 1$ で考えると $R(s u_2)$ を最小にする $s$ は
$s = p_{2k-1} + i p_{2k} \le p_{2k-1} + j p_{2k} - 1 \lt p_{2k-1} + (i+1)\ p_{2k}$ をみたす.
したがって $i = j - 1$
すなわち $s = p_{2k-1} + (j-1)\ p_{2k}$ のとき $R(s u_2)$ は最小値をとる.
このときの $R(s u_2)$ の値は補題5(iv) より
$R(s u_2) = R((p_{2k-1} + (j-1)\ p_{2k})\ u_2) = r_{2k-1} - (j-1)\ r_{2k}$

したがって $R(z u_2) \ge min\ \lbrace R(s u_2)\ |\ 0 \lt s \le A \rbrace = r_{2k-1} - (j-1)\ r_{2k}$

【証明終わり】

補注8

$p_{2k-1} + a_{2k} p_{2k} = p_{2k+1}$
$r_{2k-1} - (a_{2k}-1)\ r_{2k} = r_{2k-1} - a_{2k}\ r_{2k} + r_{2k} = r_{2k+1} + r_{2k}$
なので
$j = a_{2k}$ のときの上記補題は

$0 \lt z \lt p_{2k+1},\ 2 \le 2k \le l$ のとき

\begin{aligned}
R(z u_2) \ge r_{2k+1} + r_{2k}
\end{aligned}

となる.

命題9

$r_{2k+1} \le R(n) \lt r_{2k}\ (1 \le 2 k + 1 \le l)$
$n$ の最適表現を $(y,z,x)$
$p = p_{2k+1},\ q = q_{2k+1},\ r = r_{2k+1}$
とすると

このとき $z \gt 0$ であるための必要十分条件は

\begin{aligned}
Q(n) \ge q\ かつ\ Q(p u_2) + R(p u_2) \gt p 
\end{aligned}

をみたすことである.

また $z \gt 0$ のとき

\begin{aligned}
&z \ge p \\
&Q(n - p u_2) = Q(n) - q \\
&R(n - p u_2) = R(n) - r
\end{aligned}

が成り立つ.

証明

まず $z \gt 0$ のとき $z \ge p$ を示す.

$k = 0$ のときは $p = p_{2k+1} = p_1 = 1$ なので
$z \gt 0$ ならば $z \ge 1 = p_1$ なので $z \ge p$ が成り立っている.

$k \gt 0$ のときは背理法で $z \lt p = p_{2k+1}$ と仮定する.
補注8より $R(z u_2) \ge r_{2k+1} + r_{2k}$
補題2とあわせると $R(n) \ge R(z u_2) \ge r_{2k} + r_{2k+1} \ge r_{2k}$
これは本命題の仮定 $R(n) \lt r_{2k}$ に矛盾するので $z \ge p$ が示せた.

以降、補題5(iv)より
$q = q_{2k+1} = Q(p_{2k+1} u_2) = Q(p u_2)$
$r_{2k+1} = R(p_{2k+1} u_2) = R(p u_2)$
であることに注意する.

$z \ge p$ なので $n = ||(y,z,x)|| \ge z u_2 \ge p u_2$
よって
$Q(n) \ge Q(p u_2) = q$

また $0 \lt p \le z$ なので補題3より $Q(p u_2) + R(p u_2) \gt p$ である.

逆に $Q(n) \ge q$ かつ $Q(p u_2) + R(p u_2) \gt p$ のとき $z \gt 0$ であることを示す.

背理法の仮定として $z = 0$ とする.
補題4より $(Q(n), 0, R(n))$ が最適表現ということになる.

本命題の仮定より $R(n) \ge r_{2k+1} = R(p u_2)$
これと $Q(n) \ge q = Q(p u_2)$ より
$(Q(p u_2),0,R(p u_2)) \subset (Q(n), 0, R(n))$
$(Q(n), 0, R(n))$ は最適表現だったので補題1から $(Q(p u_2),0,R(p u_2))$ も最適表現でなければならない.

ここで、$(Q(p u_2), 0, R(p u_2))$ と金額が等しい別の表現 $(0,p,0)$ を考える.
$Q(p u_2) + R(p u_2) \gt p$ より
$|(Q(p u_2),0,R(p u_2))| \gt |(0, p, 0)|$
つまり $(0, p, 0)$ の方が $(Q(p u_2),0,R(p u_2))$ より適している.
これは $(Q(p u_2),0,R(p u_2))$ が最適表現であることに矛盾する.
ゆえに背理法の仮定は誤りであり $z \gt 0$ が成り立つ.

補題5(ii) より $p u_2 = q u_1 + r$ なので
$n - p u_2 = Q(n) u_1 + R(n) - q u_1 - r = (Q(n) - q) u_1 + (R(n) - r)$
本命題の仮定から $R(n) \ge r$ なので $0 \le R(n) - r \lt u_1$
一方 $n - p u_2 = Q(n - p u_2) u_1 + R(n - p u_2)$
$n - p u_2$ に対する商と余りの一意性から
$Q(n - p u_2) = Q(n) - q,\ R(n - p u_2) = R(n) - r$

【証明終わり】

この命題がアルゴリズムのステップ2 に対応しています。

命題10

$r_{2k-1} - j r_{2k} \le R(n) \lt r_{2k-1} - (j-1)\ r_{2k} \ (2 \le 2 k \le l,\ 1 \le j \lt a_{2k})$
$n$ の最適表現を $(y,z,x)$
$p = p_{2k-1} + j p_{2k},\ q = q_{2k-1} + j q_{2k},\ r = r_{2k-1} - j r_{2k},$
とする.

このとき $z \gt 0$ であるための必要十分条件は

\begin{aligned}
Q(n) \ge q\ かつ\ Q(p u_2) + R(p u_2) \gt p 
\end{aligned}

をみたすことである.

また $z \gt 0$ のとき

\begin{aligned}
&z \ge p \\
&Q(n - p u_2) = Q(n) - q \\
&R(n - p u_2) = R(n) - r
\end{aligned}

が成り立つ.

証明

証明の流れは命題9と同様である.

まず $z \gt 0$ のとき $z \ge p$ を示す.

背理法で $z \lt p = p_{2k-1} + j p_{2k}$ と仮定する.
補題7より $R(z u_2) \ge r_{2k-1} - (j-1)\ r_{2k}$
補題2とあわせると $R(n) \ge R(z u_2) \ge r_{2k-1} - (j-1)\ r_{2k}$
これは本命題の仮定に矛盾するので $z \ge p$ が示せた.

補題5(iv)より
$q = q_{2k-1} + j q_{2k} = Q((p_{2k-1} + j p_{2k}) u_2) = Q(p u_2)$
$r_{2k-1} - j r_{2k} = R((p_{2k-1} + j p_{2k}) u_2) = R(p u_2)$
本命題の仮定より
$R(n) \ge r_{2k-1} - j r_{2k} = R(p u_2)$
であることに注意すれば、あとは命題9の証明と同じである.

【証明終わり】

この命題がアルゴリズムのステップ3 に対応しています。

補題11

$p = p_{2k-1} + j p_{2k},\ 2 \le2k \le l,\ 0 \lt j \le a_{2k}$ とすると次の (i),(ii) は同値である.

(i) $Q(p u_2) + R(p u_2) \gt p$
(ii) $j(p_{2k} - q_{2k} + r_{2k}) \lt q_{2k-1} - p_{2k-1} + r_{2k-1}$

$j = a_{2k}$ のときは $p = p_{2k-1} + a_{2k} p_{2k} = p_{2k+1}$ である.

証明

(i) $\Rightarrow$ (ii)

補題5(iv)より $Q(p u_2) = q_{2k-1} + j q_{2k},\ R(p u_2) = r_{2k-1} - j r_{2k}$
よって (i) は $q_{2k-1} + j q_{2k} + r_{2k-1} - j r_{2k} \gt p_{2k-1} + j p_{2k}$
$\therefore\ q_{2k-1} - p_{2k-1} + r_{2k-1} \gt j p_{2k} - j q_{2k} + j r_{2k} = j (p_{2k} - q_{2k} + r_{2k})$

(ii) $\Rightarrow$ (i)

上記の式の変形を逆にたどればよい.

【証明終わり】

この補題がアルゴリズムのステップ3 の $a$ の決定に対応しています。

定理12

前回の記事で書いたアルゴリズムは最適表現を計算する.

このアルゴリズムの計算量は $O(log\ u_2)$ である.

証明

アルゴリズムの方針は $n$ の最適表現の部分となる表現 $(0,p,0)$ を見つけだし、 $n - p u_2$ の最適表現を求める問題に帰着させていくことである.

(ステップ 1)

$u_1$ と $u_2$ から 4つの整数列 ${a_i}, {r_i}, {p_i}, {q_i}$ を求める.

(ステップ 2)

$y = Q(n),\ z = 0,\ x = R(n),\ k = 1$ に初期化する.

これ以降も、$n$ に求めたい最適表現の金額が、$y$ には $Q(n)$ が、$x$ には $R(n)$ が、$z$ にはそれまでに必要と判明した $u_2$ の枚数が設定されるようにしていく.

(ステップ 3)

このステップに入ったときは $x = R(n) \lt r_{2k-2}$ が成り立っている.
なぜなら、ステップ 2 から入ったときは $k = 1$ なので
$x = R(n) \lt u_1 = r_0 = r_{2k-2}$ と成り立つ.
後述するステップ 4 から入るときについてはステップ 4 で説明する.

また、このステップに入ったときは
$Q(p u_2) + R(p u_2) \gt p （ただし p = p_{2k-1})$ が成り立っている.
なぜなら、ステップ 2 から入ったときは $k = 1$ で $p = p_{2k-1} = p_1 = 1$ なので
$Q(p u_2) + R(p u_2) = 0 + u_2 \gt 1 = p$ と成り立つ.
ステップ 4 から入るときについてはステップ 4 で説明する.

これらの条件の上にさらに $R(n) = x \ge r_{2k-1}$ かつ $Q(n) = y \ge q_{2k-1}$ が成り立つときは
命題9より $n$ の最適表現は部分として $(0,p,0)$ を含むことがわかる.
このときは $n$ の最適表現を求める問題を $n - p u_2$ の最適表現を求める問題に帰着できる.
$R(n - p u_2) = R(n) - r_{2k-1} \lt r_{2k-2} - r_{2k-1} \le r_{2k-2}$ なので
もし $R(n - p u_2) \ge r_{2k-1}$ ならばまた同様の処理を試すことができる.
これを繰り返せる回数が $\lfloor x / r_{2k-1} \rfloor$ と $\lfloor y / q_{2k-1} \rfloor$ の小さい方の値である.
$\lfloor x / r_{2k-1} \rfloor \gt \lfloor y / q_{2k-1} \rfloor$ のときは繰り返した結果 $Q(n) \ge q_{2k-1}$ が成り立たなくなっているので命題9よりこれ以上 $u_2$ を使わないことが確定する.
このときは帰着された金額に対して $u_1$ を貪欲に使い処理を終了する.

$\lfloor x / r_{2k-1} \rfloor \le \lfloor y / q_{2k-1} \rfloor$ のときは $x$ から $r_{2k-1}$ を引く処理を $\lfloor x / r_{2k-1} \rfloor$回繰り返しているので $x \lt r_{2k-1}$ が成り立った状態でステップ 4 に進む.

(ステップ 4)

ステップ 3 の最後に書いたとおり、このステップに入ったときは $x \lt r_{2k-1}$ が成り立っている.

まず $r_{2k-1} - j r_{2k} \le x \lt r_{2k-1} - (j-1)\ r_{2k}$ を満たす $j$ を求める.
$p = p_{2k-1} + j p_{2k}$ とする.

$Q(n) \lt j q_{2k} + q_{2k-1}$ ならば命題10よりこれ以上 $u_2$ を使わないことが確定する.
このときは $n$ に対して $u_1$ を貪欲に使い処理を終了する.

以下、補題5(i)より $p_{2k} \gt q_{2k}$ なので
$r_{2k} + p_{2k} - q_{2k} \gt 0$ であることに注意する.

$r_{2k-1} - p_{2k-1} + q_{2k-1} \gt a\ (r_{2k} + p_{2k} - q_{2k})$ をみたす最大の $a$ を求める.

$j \gt a$ ならば $r_{2k-1} - p_{2k-1} + q_{2k-1} \le j\ (r_{2k} + p_{2k} - q_{2k})$ なので
補題11より $Q(p u_2) + R(p u_2) \le p$
よって、命題10よりこれ以上 $u_2$ を使わないことが確定する.
このときも $n$ に対して $u_1$ を貪欲に使い処理を終了する.

それ以外のときは命題10より $n$ の最適表現は部分として $(0,p,0)$ を含むことがわかる.
このときは $n$ の最適表現を求める問題を $n - p u_2$ の最適表現を求める問題に帰着できる.
$R(n - p u_2) = R(n) - (r_{2k-1} - j r_{2k}) \lt (r_{2k-1} - (j-1) r_{2k}) - (r_{2k-1} - j r_{2k}) = r_{2k-2}$
なので、この後ステップ 3 に入るときは $x \lt r_{2k-2}$ が成り立っている.

$a \lt a_{2k}$ のときは
$r_{2k-1} - p_{2k-1} + q_{2k-1} \le a_{2k}\ (r_{2k} + p_{2k} - q_{2k})$ なので
補題11の $j = a_{2k}$ のケースに該当し $Q(p_{2k+1} u_2) + R(p_{2k+1} u_2) \le p_{2k+1}$
よって命題10よりこれ以上 $u_2$ を使わないことが確定する.
このときも $n$ に対して $u_1$ を貪欲に使い処理を終了する.

そうでなければ、この後ステップ3 に入るときには
$Q(p_{2k+1} u_2) + R(p_{2k+1} u_2) \gt p_{2k+1}$
が成り立っている.

ステップ 3 とステップ 4 の繰り返しの停止性について.

補題5(v) より
$Q(p_{l+1} u_2) + R(p_{l+1} u_2) = u_2 / r_l \lt u_1 / r_l = p_{l+1}$
よって命題10または命題11によりステップ 3 またはステップ 4 でこれ以上 $u_2$ を使わないことが確定するので必ず処理が終わる.

計算量について

繰り返しの回数は $u_1$ と $u_2$ のユークリッドの互除法のステップ数のオーダーなので $O(log\ u_2)$ である.
各ステップの計算量は $O(1)$ なので全体の計算量は $O(log\ u_2)$ である.

【証明終わり】

最後にまわしていた命題6の証明

この証明は初等整数論講義（高木貞治）の 定理2.8の第二の証明を有理数用に焼き直したものになります。

【証明】

$R(s u_2)$ の正の最小値は $s u_2 - t u_1$ の正の最小値と等しいので $s u_2 - t u_1$ を正の中で最小にする $s,t$ を求める.

まず

\begin{aligned}
&c = s q_{2k} - t p_{2k} \\
&d = -s q_{2k-1} + t p_{2k-1} \\
&\Delta = p_{2k-1} q_{2k} - p_{2k} q_{2k-1}
\end{aligned}

とおくとよく知られているように $\Delta \neq 0$ のとき

\begin{aligned}
&s = (c p_{2k-1} + d p_{2k}) / \Delta\\
&t = (c q_{2k-1} + d q_{2k}) / \Delta
\end{aligned}

補題5(iii)より $\Delta = 1$ であることに注意すると

\begin{aligned}
&s = c p_{2k-1} + d p_{2k} \\
&t = c q_{2k-1} + d q_{2k}
\end{aligned}

なので整数の組 $s,t$ と整数の組 $c,d$ は一対一対応する

$s u_2 - t u_1$ を $c,d$ で表すと 補題5(ii)より

\begin{aligned}
s u_2 - t u_1 &= (c p_{2k-1} + d p_{2k}) u_2 - (c q_{2k-1} + d q_{2k}) u_1 \\
&= c (p_{2k-1} u_2 - q_{2k-1} u_1) + d (p_{2k} u_2 - q_{2k} u_1) \\
&= c r_{2k-1} - d r_{2k}
\end{aligned}

なので $s u_2 - t u_1$ を正の中で最小にする $s,t$ を考える代わりに $c r_{2k-1} - d r_{2k}$ を正の中で最小にする $c,d$ を考える.

もし $c \le 0$ と仮定すると $p_{2k-1} \gt 0, p_{2k} \gt 0$ ($k \ge 1$) なので

\begin{aligned}
&0 \lt s = c p_{2k-1} + d p_{2k} \le d p_{2k} \\
\therefore \ &d \gt 0
\end{aligned}

$d$ は整数なので $d \ge 1$.
したがって $c r_{2k-1} - d r_{2k} \le -r_{2k}$ と負になるので $c r_{2k-1} - d r_{2k}$ の正の値を考えるなら $c \gt 0$ でなければならない.
つまり $ c\ge 1$.

$s \le A \lt p_{2k-1} + (j+1) p_{2k}$ だったので
$c p_{2k-1} + d p_{2k} = s \lt p_{2k-1} + (j+1) p_{2k}$
これと $c \ge 1$ を使うと
$d p_{2k} \lt (1 - c) p_{2k-1} + (j+1) p_{2k} \le (j + 1) p_{2k}$
$p_{2k} \gt 0$ なので $d \lt j + 1$ したがって $d \le j$.

よって $c r_{2k-1} - d r_{2k} \ge r_{2k-1} - j r_{2k}$
しかも等号は $c = 1, d = j$ のときに限る.
すなわち $s, t$ の表現に戻すと

\begin{aligned}
&s = p_{2k-1} + j p_{2k} \\
&t = q_{2k-1} + j q_{2k}
\end{aligned}

のときに $s u_2 - t u_1$ は正の最小値をとる.

$s u_2 - t u_1$ の正の最小値は $R(s u_2)$ の値と等しいので $R(s u_2)$ を使った表現で言い換えると
$R(s u_2)$ の最小値を与える $s$ の整数値は

\begin{aligned}
s = p_{2k-1} + j p_{2k} \\
\end{aligned}

そのときのみである。

【証明終わり】

May Monad be with you