問題12 （tomhさん）
問題編
問：1億以下の2つの自然数a,b(a>b)が与えられたとき、Euclidの互除法で
公約数を見つけることにします。この方法で最悪の場合、何回割り算を
行わなければならないでしょうか？
また、そのような最悪の組み合わせになる(a,b)は何組ありますか？
なかさん出題の発展問題
６０けたのときに後半の設問の答はいくつになりますか。
なかさんの発展問題解答へ
解答編 tomhさんの気合の入った解答です(*^_^*)
自然数a,b(a>b)に対して、Euclidの互除法を実行して、n回の割り算が
行われたものとします：
a = q_1 b + r_1, 0 <r_1 < b
b = q_2 r_1 + r_2, 0 <r_2 < r_1
r_1 = q_3 r_2 + r_3, 0 <r_3 < r_2
…
r_{n-2} = q_n r_{n-1} + r_n. r_n = 0
これらの式から、nを固定したときの最小のaを求めてみます。
それには、これらの式を逆にたどっていったときに、順番に
r_{n-1}, q_n, q_{n-1}, …, q_1をなるべく小さくすればよいので、
0<r_{n-1}<r_{n-2}に注意して、
r_{n-1}=1, q_n=2,
q_{n-1} = q_{n-2} = … = q_1 = 1
とすれば、aは最小になります。
（q_n=1とすると、r_{n-1}=r_{n-2}となってしまいます。）
つまり、
r_{n-1} = 1,
r_{n-2} = 2,
r_k = r_{k-1} +r_{k-2} k≧3
です(b=r_1+r_2, a=b+r_1)。これは、お馴染みのFibonacci数列{F_k}です。
Fibonacci数列を (F_0=1,) F_1=1, F_2=2, …, F_37=39088169,
F_38=63245986, F_39=102334155とすると、対応は、r_{n-1}=F_1,
r_{n-2}=F_2, …, r_1=F_{n-1}, b=F_n, a=F_{n+1}となります。
よって、n≧38ならば、a≧102334155(=F_39)となります。
対偶をとれば、a<102334155ならば、n<38です。つまり、最悪37回割り算を
しなければならない可能性があるわけですが、実際、それは、
a=63245986(=F_38), b=39088169(=F_37)という隣り合ったFibonacci数を
採ると実現します。
このa=63245986, b=39088169という組み合わせは、確かに37回の
割り算を必要としますが、q_37を2から3にした場合のa=87403803,
b=54018521や、q_36からq_2のどれかを1から2にした場合の値は、
すべて37回の割り算を必要とします。37回必要なのは、
これらだけでしょうか?
今、q_kのどれか一つの値を上記の値よりpだけ増加させてみます。
このとき、新しいaとbは、それぞれ
a → a +pF_{k-1}F_{38-k}, (k=1,…,37)
b → b +pF_{k-2}F_{38-k} (k=2,…,37)
→ b (k=1)
と増加します。
実際にaの増加分を計算すると
k= 1 : F_0 F_37 = 1 x 39088169 = 39088169 0.94028487
k= 2,37: F_1 F_36 = 1 x 24157817 = 24157817 1.52141288
k= 3,36: F_2 F_35 = 2 x 14930352 = 29860704 1.23084888
k= 4,35: F_3 F_34 = 3 x 9227465 = 27682395 1.32770355
k= 5,34: F_4 F_33 = 5 x 5702887 = 28514435 1.28896168
k= 6,33: F_5 F_32 = 8 x 3524578 = 28196624 1.30348988
k= 7,32: F_6 F_31 = 13 x 2178309 = 28318017 1.29790211
k= 8,31: F_7 F_30 = 21 x 1346269 = 28271649 1.30003078
k= 9,30: F_8 F_29 = 34 x 832040 = 28289360 1.29921688
k=10,29: F_9 F_28 = 55 x 514229 = 28282595 1.29952764
k=11,28: F_10 F_27 = 89 x 317811 = 28285179 1.29940892
k=12,27: F_11 F_26 = 144 x 196418 = 28284192 1.29945427
k=13,26: F_12 F_25 = 233 x 121393 = 28284569 1.29943695
k=14,25: F_13 F_24 = 377 x 75025 = 28284425 1.29944356
k=15,24: F_14 F_23 = 610 x 46368 = 28284480 1.29944104
k=16,23: F_15 F_22 = 987 x 28657 = 28284459 1.29944200
k=17,22: F_16 F_21 = 1597 x 17711 = 28284467 1.29944163
k=18,21: F_17 F_20 = 2584 x 10946 = 28284464 1.29944177
k=19,20: F_18 F_19 = 4181 x 6765 = 28284465 1.29944173
となります。表の最後の値は、100000000-a=36754014を
各F_{k-1}F_{38-k}で割った値で、pの制限を与えます。
これによると、F_0 F_37 (k=1)による増加で、aが1億を
越えてしまうことがわかります。残りの18個の増加分は、p=1ならば、
aを1億以下にすることができます。
よって、36(=18x2)個の組み合わせと元のa=63245986,b=39088169の
組み合わせの合計37個が、割り算を37回必要とするすべての組に
なります。
（18を2倍にしたのは、同じaの増加分でも、bの増加分が違うからです。
例えば、aが、F_18 F_19=28284465だけ増加しても、bは、
F_17 F_19=17480760(k=19)増加する場合と、F_18 F_18=17480761(k=20)
増加する場合があります。）
因みにr_36をpだけ増加させたときは、aはpF_38だけ増加するので、
p=1でもaが1億を越えてしまい不適です。
=================================================================
q_kのどれか一つの値を上記の値よりpだけ増加するときはP=1で
なければならないことがわかりましたが、2箇所のq_kが増加するときはどうでしょうか
記法は前回通りとします。
q_iとq_j(37≧i>j≧1)の値をそれぞれp_iとp_jだけ増加させてみます。
このとき、新しいaは、
a → a +p_iF_{i-1}F_{38-i} +p_jF_{j-1}F_{38-j}
+p_ip_jF_{i-1}F_{i-j+1}F_{38-j}
と増加します。
F_{k-1}F_{38-k}を再掲すると
k= 1 : F_0 F_37 = 1 x 39088169 = 39088169 0.94028487
k= 2,37: F_1 F_36 = 1 x 24157817 = 24157817 1.52141288
k= 3,36: F_2 F_35 = 2 x 14930352 = 29860704 1.23084888
k= 4,35: F_3 F_34 = 3 x 9227465 = 27682395 1.32770355
k= 5,34: F_4 F_33 = 5 x 5702887 = 28514435 1.28896168
k= 6,33: F_5 F_32 = 8 x 3524578 = 28196624 1.30348988
k= 7,32: F_6 F_31 = 13 x 2178309 = 28318017 1.29790211
k= 8,31: F_7 F_30 = 21 x 1346269 = 28271649 1.30003078
k= 9,30: F_8 F_29 = 34 x 832040 = 28289360 1.29921688
k=10,29: F_9 F_28 = 55 x 514229 = 28282595 1.29952764
k=11,28: F_10 F_27 = 89 x 317811 = 28285179 1.29940892
k=12,27: F_11 F_26 = 144 x 196418 = 28284192 1.29945427
k=13,26: F_12 F_25 = 233 x 121393 = 28284569 1.29943695
k=14,25: F_13 F_24 = 377 x 75025 = 28284425 1.29944356
k=15,24: F_14 F_23 = 610 x 46368 = 28284480 1.29944104
k=16,23: F_15 F_22 = 987 x 28657 = 28284459 1.29944200
k=17,22: F_16 F_21 = 1597 x 17711 = 28284467 1.29944163
k=18,21: F_17 F_20 = 2584 x 10946 = 28284464 1.29944177
k=19,20: F_18 F_19 = 4181 x 6765 = 28284465 1.29944173
でした。表の最後の値は、100000000-a=36754014を各F_{k-1}F_{38-k}で
割った値で、1以上の値になっていないと駄目なので、使えるのは
k=2〜37となったのでした。
今回もこの値を計算しましょう。p_i=p_j=1として計算してみて、
駄目なことを示します。この値で駄目なら、p_iやp_jを1以上にしても
駄目ですね。
さて、
(100000000-a)/(F_{k-1}F_{38-k}) = 36754014/(F_{k-1}F_{38-k})
= d_k
とします。表を見ると、各d_kは、0<d_k<2を満たすことを
覚えておきましょう。以後、36754014をAと書きます。
では、計算です。求める量は、
A/(F_{i-1}F_{38-i}+F_{j-1}F_{38-j}+F_{i-1}F_{i-j+1}F_{38-j})です。
これをBとしましょう。すると、このBは
B < A/(F_{i-1}F_{38-i}+F_{j-1}F_{38-j})
= 1/[(1/d_i)+(1/d_j)]
= d_id_j/(d_i+d_j)
と評価されます。ここで、
d_id_j-(d_i+d_j) = (1-d_i)(1-d_j)-1
ですが、(1-d_i)(1-d_j)は、-1<1-d_i,1-d_j<1より、絶対値が1より
小さい量を掛け合わせているので、掛け合わせた量も絶対値が1よりも
小さい量になります。よって、
d_id_j-(d_i+d_j) < 0.
つまり、d_id_j/(d_i+d_j)<1となって、B<1がいえました。
これは2カ所でq_kを増やすと、新しいaは１億を越えてしまう
ことを意味しています。■
∴ 37回の割り算を要する組み合わせが37組ある。
=================================================================
回数と組数が同じなのは偶然だと思います。
＃ただ、1万のときは、"18回の割り算を要する組み合わせが18組ある"
＃ってのが答えになるんですよねぇ… 偶然じゃないのかも… (^^;
それから、前回出てきた"（正則）連分数"を求める計算も、実は
Euclidの互除法と同じ計算なので、連分数の段数も求められるわけです。
最後に37個の数字の組(a,b)をすべて挙げておきます。
orig: 63245986 39088169
k= 2: 87403803 63245986
k= 3: 93106690 54018521
k= 4: 90928381 57543099
k= 5: 91760421 56196830
k= 6: 91442610 56711059
k= 7: 91564003 56514641
k= 8: 91517635 56589666
k= 9: 91535346 56561009
k=10: 91528581 56571955
k=11: 91531165 56567774
k=12: 91530178 56569371
k=13: 91530555 56568761
k=14: 91530411 56568994
k=15: 91530466 56568905
k=16: 91530445 56568939
k=17: 91530453 56568926
k=18: 91530450 56568931
k=19: 91530451 56568929
k=20: 91530451 56568930
k=21: 91530450 56568929
k=22: 91530453 56568931
k=23: 91530445 56568926
k=24: 91530466 56568939
k=25: 91530411 56568905
k=26: 91530555 56568994
k=27: 91530178 56568761
k=28: 91531165 56569371
k=29: 91528581 56567774
k=30: 91535346 56571955
k=31: 91517635 56561009
k=32: 91564003 56589666
k=33: 91442610 56514641
k=34: 91760421 56711059
k=35: 90928381 56196830
k=36: 93106690 57543099
k=37: 87403803 54018521
=================================================================
Fibonacci数列の表現方法で、良く知られたものとして、
F_k = [((1+√5)/2)^{k+1} -((1-√5)/2)^{k+1}]/√5
ってのがあります。これを使って、回数の上限を
評価してみましょう。
F_{k+2}＞a≧F_{k+1} (k≧1)とします。このとき、
上限の回数nに対して、k≧nであることに注意しましょう。
（帰納法により証明できます。最後の付録を参照して下さい。）
上記の式を使って、
a ≧ [((1+√5)/2)^{k+2} -((1-√5)/2)^{k+2}]/√5
=((1+√5)/2)^{k+2} [1-(-(1-√5)^2/4)^{k+2}]/√5
となりますが、kが奇数のときは、"[ ]"の中は1よりも
大きい数になります。また、kが偶数のときは、
0<(1-√5)^2/4<1なので、"[ ]"の中は1よりも小さい数に
なりますが、その中でもk=2のときが一番小さくなります。
よって、
a ≧ ((1+√5)/2)^{k+2} [1-((1-√5)^2/4)^4]/√5
= (1+√5)/2)^k (9-3√5)/2
≧ (1+√5)/2)^n (9-3√5)/2
です。両辺の（常用）対数をとると、
4.785 log(a) -0.283 ≧ n
となります。実際にa=100000000を入れると、左辺は
37.997となるので、37≧nがわかります。
もちろん、この方法では、37回を実現する(a,b)が
何組あるかはわからないんですけどね。
この割り算の回数に関しては、ラメ(Lame:本当は、eの上には揚音符´が
つきます。)の定理というものがあって、
「Euclidの互除法で最大公約数を求めるのに必要なわり算の回数は、
最大でも"小さい"方の数の(10進)桁数の5倍以内である。」
となっています。
また、最近、
"フィボナッチ数の小宇宙（ミクロコスモス）／フィボナッチ数、リュカ数、
黄金分割"、中村滋（日本評論社、2002）
という本が出版されました。Fibonacci数のことが、色々書いてあって、
なかなかの意欲作になっています。ラメの定理の証明もありますので、
興味のある方はご一読を。
== 付録 ==
F_{k+2}>a ならば、k≧nであることの証明：
(i) k=1,2のときは、ほぼ自明である。
（実際に代入して確かめられる。）
(ii) k=mの成り立つと仮定する。
そして、F_{m+3}>a (k=m+1)のときを考える。
a=q_1 b+r_1 (0<r_1<b), b=q_2 r_1+r_2 (0<r_2<r_1)と
する。
(1) F_{m+2}>bならば、F_{m+2}>b>r_1なので、bとr_1
から出発すれば、仮定によりm回以下で割り算は
終わる。最初の1回を加えて、m+1回以下で終わる。
(2) b≧F_{m+2}のときは、
a-b < F_{m+3}-F_{m+2} = F_{m+1} < b
であるから、r_2<r_1=a-b<F_{m+1}となる。
r_1とr_2から出発すれば、仮定によりm-1回以下で
割り算は終了するから、最初の2回を加えて、
m+1回以下で終わる。
以上のことから、F_{k+2}>a ならば、k≧nであることが
証明できた。■
=================================================================
発展問題解答
１００けたまで計算してみました。
最大除算回数をｎそれを与える初期値の場合の数をｋ（ｎ）とすると、
たいがい、ｋ（ｎ）＝１、または、ｋ（ｎ）＝ｎ
となることが確認されました。例外は９桁などわずかです。
最小値が微妙な値になるときに限り、場合の数が微妙になる点、
気分はでてますね。
結局、いちいち確かめないと（２）は出せないのかなと思います。
Upper 10^ 1 , n= 4 , k(n)= 1
Upper 10^ 2 , n= 9 , k(n)= 1
Upper 10^ 3 , n= 14 , k(n)= 1
Upper 10^ 4 , n= 18 , k(n)= 18
Upper 10^ 5 , n= 23 , k(n)= 1
Upper 10^ 6 , n= 28 , k(n)= 1
Upper 10^ 7 , n= 33 , k(n)= 1
Upper 10^ 8 , n= 37 , k(n)= 37
Upper 10^ 9 , n= 42 , k(n)= 3
Upper 10^ 10 , n= 47 , k(n)= 1
Upper 10^ 11 , n= 52 , k(n)= 1
Upper 10^ 12 , n= 57 , k(n)= 1
Upper 10^ 13 , n= 61 , k(n)= 61
Upper 10^ 14 , n= 66 , k(n)= 1
Upper 10^ 15 , n= 71 , k(n)= 1
Upper 10^ 16 , n= 76 , k(n)= 1
Upper 10^ 17 , n= 81 , k(n)= 1
Upper 10^ 18 , n= 85 , k(n)= 83
Upper 10^ 19 , n= 90 , k(n)= 1
Upper 10^ 20 , n= 95 , k(n)= 1
Upper 10^ 21 , n= 100 , k(n)= 1
Upper 10^ 22 , n= 104 , k(n)= 104
Upper 10^ 23 , n= 109 , k(n)= 3
Upper 10^ 24 , n= 114 , k(n)= 1
Upper 10^ 25 , n= 119 , k(n)= 1
Upper 10^ 26 , n= 124 , k(n)= 1
Upper 10^ 27 , n= 128 , k(n)= 128
Upper 10^ 28 , n= 133 , k(n)= 1
Upper 10^ 29 , n= 138 , k(n)= 1
Upper 10^ 30 , n= 143 , k(n)= 1
Upper 10^ 31 , n= 148 , k(n)= 1
Upper 10^ 32 , n= 152 , k(n)= 150
Upper 10^ 33 , n= 157 , k(n)= 1
Upper 10^ 34 , n= 162 , k(n)= 1
Upper 10^ 35 , n= 167 , k(n)= 1
Upper 10^ 36 , n= 171 , k(n)= 171
Upper 10^ 37 , n= 176 , k(n)= 3
Upper 10^ 38 , n= 181 , k(n)= 1
Upper 10^ 39 , n= 186 , k(n)= 1
Upper 10^ 40 , n= 191 , k(n)= 1
Upper 10^ 41 , n= 195 , k(n)= 195
Upper 10^ 42 , n= 200 , k(n)= 1
Upper 10^ 43 , n= 205 , k(n)= 1
Upper 10^ 44 , n= 210 , k(n)= 1
Upper 10^ 45 , n= 214 , k(n)= 214
Upper 10^ 46 , n= 219 , k(n)= 217
Upper 10^ 47 , n= 224 , k(n)= 1
Upper 10^ 48 , n= 229 , k(n)= 1
Upper 10^ 49 , n= 234 , k(n)= 1
Upper 10^ 50 , n= 238 , k(n)= 238
Upper 10^ 51 , n= 243 , k(n)= 3
Upper 10^ 52 , n= 248 , k(n)= 1
Upper 10^ 53 , n= 253 , k(n)= 1
Upper 10^ 54 , n= 258 , k(n)= 1
Upper 10^ 55 , n= 262 , k(n)= 262
Upper 10^ 56 , n= 267 , k(n)= 1
Upper 10^ 57 , n= 272 , k(n)= 1
Upper 10^ 58 , n= 277 , k(n)= 1
Upper 10^ 59 , n= 281 , k(n)= 281
Upper 10^ 60 , n= 286 , k(n)= 282
Upper 10^ 61 , n= 291 , k(n)= 1
Upper 10^ 62 , n= 296 , k(n)= 1
Upper 10^ 63 , n= 301 , k(n)= 1
Upper 10^ 64 , n= 305 , k(n)= 305
Upper 10^ 65 , n= 310 , k(n)= 3
Upper 10^ 66 , n= 315 , k(n)= 1
Upper 10^ 67 , n= 320 , k(n)= 1
Upper 10^ 68 , n= 325 , k(n)= 1
Upper 10^ 69 , n= 329 , k(n)= 329
Upper 10^ 70 , n= 334 , k(n)= 1
Upper 10^ 71 , n= 339 , k(n)= 1
Upper 10^ 72 , n= 344 , k(n)= 1
Upper 10^ 73 , n= 348 , k(n)= 348
Upper 10^ 74 , n= 353 , k(n)= 5
Upper 10^ 75 , n= 358 , k(n)= 1
Upper 10^ 76 , n= 363 , k(n)= 1
Upper 10^ 77 , n= 368 , k(n)= 1
Upper 10^ 78 , n= 372 , k(n)= 372
Upper 10^ 79 , n= 377 , k(n)= 3
Upper 10^ 80 , n= 382 , k(n)= 1
Upper 10^ 81 , n= 387 , k(n)= 1
Upper 10^ 82 , n= 392 , k(n)= 1
Upper 10^ 83 , n= 396 , k(n)= 396
Upper 10^ 84 , n= 401 , k(n)= 1
Upper 10^ 85 , n= 406 , k(n)= 1
Upper 10^ 86 , n= 411 , k(n)= 1
Upper 10^ 87 , n= 415 , k(n)= 415
Upper 10^ 88 , n= 420 , k(n)= 3
Upper 10^ 89 , n= 425 , k(n)= 1
Upper 10^ 90 , n= 430 , k(n)= 1
Upper 10^ 91 , n= 435 , k(n)= 1
Upper 10^ 92 , n= 439 , k(n)= 439
Upper 10^ 93 , n= 444 , k(n)= 3
Upper 10^ 94 , n= 449 , k(n)= 1
Upper 10^ 95 , n= 454 , k(n)= 1
Upper 10^ 96 , n= 459 , k(n)= 1
Upper 10^ 97 , n= 463 , k(n)= 463
Upper 10^ 98 , n= 468 , k(n)= 1
Upper 10^ 99 , n= 473 , k(n)= 1
Upper 10^ 100 , n= 478 , k(n)= 1
参考（UBASIC）
1 print=print+"euc30.txt"
3 word 22
4 dim A(503),Amin(503),Q(503)
8 Upper=1
10 for Pw=1 to 100
12 Nmax=0:Count=0
20 Upper=Upper*10
30 ' print:print "----------- 1e";Pw;"(";Upper;") ----------"
50 for I=0 to 5*Pw+3:Amin(I)=Upper:Q(I)=0:next
55 Q(1)=1
60 A(0)=0:A(1)=1
70 N=1
75 if N<1 then goto 190
80 Q(N)=Q(N)+1
90 A(N+1)=A(N)*Q(N)+A(N-1)
91 if A(N+1)>Upper then Q(N)=0:N=N-1:goto 75
92 if Amin(N+1)=Upper then Amin(N+1)=A(N+1)
96 if A(N+1)>=Amin(N+2) and A(N+1)+A(N)>=Amin(N+3) then Q(N)=0:N=N-1:goto 75
100 if A(N)+A(N+1)<=upper then N=N+1:goto 75
110 if N>=Nmax then Count=Count+1:Nmax=N
111 ' if N>=Nmax then print "No.";Count;"n=";N;"(";A(N+1);",";A(N);")"
120 goto 75
190 print "Upper 10^";Pw;" , n=";Nmax;", k(n)=";Count
200 next Pw