ユークリッドの互除法の解析を続ける．除算ステップの最大回数がわかったから，次は平均回数を求めたい．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［１］近似モデル

　分母がｎのときの平均回数を

　　Ｔn＝１／ｎ・ΣＴ（ｋ，ｎ）

とすると，漸化式

　　Ｔ0＝０，

　　Ｔn＝１＋（Ｔ0＋Ｔ1＋・・・＋Ｔn-1）／ｎ

　　Ｔn+1＝１＋（Ｔ0＋Ｔ1＋・・・＋Ｔn）／（ｎ＋１）

＝１＋（ｎ（Ｔn−１）＋Ｔn）／（ｎ＋１）＝Ｔn＋１／（ｎ＋１）

が成り立つ．

　したがって，Ｔn＝Ｈnすなわち調和数となるから

　　Ｔn＝ｌｎ（ｎ）＋Ｏ（１）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［２］連続モデル（ガウスの定理）

　１８２８年，ガウスは整数部を除いた［０：ａ1，ａ2，ａ3，・・・，ａn］がｘより小さい小数となる確率は

　Ｐ（［０：ａ1，ａ2，ａ3，・・・，ａn］＜ｘ）＝ｌｏｇ2（１＋ｘ）＋εn

で与えられることを証明しました．

　誤差項に関して，１９２８年にクズミンはほとんどすべての連分数に対して，

　　εn＝Ｏ（ｑ^√n）　　０＜ｑ＜１

１９２９年にレヴィは

　　εn＝Ｏ（ｑ^n）　　ｑ＝０．７

であることを示しました．どちらも誤差項εnは漸近的に０になることを示しています．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　ガウスはまた，連分数の部分商の確率密度関数は

　　Ｐ（ａn＝ｋ）＝Ｐ（ｋ＜εn＜ｋ＋１）＝Ｐ（εn＜ｋ＋１）−Ｐ（εn＜ｋ）

→ｌｏｇ2（１＋１／ｋ）−ｌｏｇ2（１＋１／（ｋ＋１））＝ｌｏｇ2（１＋１／ｋ（ｋ＋２））

であることを示しました．

　ａn＝１，２，３，・・・に対する確率は大部分の小数部で等しいのと対照的に，連分数では減少していきます．そして，十分大きなｎに対する部分商の起こる確率Ｐは

ｋ　　　　　　　　１　　２　　３　　４　　５　　６　　７　　８　９＋

Ｐ（ａn ＝ｋ）　 .41 .17　 .09　 .06　 .04 .03 .02 .02 .16

となることがわかります．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　部分商がａになる確率は

　　ｌｏｇ2（１＋１／ａ）−ｌｏｇ2（１＋１／（ａ＋１））

＝ｌｏｇ2（（ａ＋１）^2／（（ａ＋１）^2−１））

　商が１になる確率はｌｏｇ2（４／３）＝４１．５０４％

　商が２になる確率はｌｏｇ2（９／８）＝１６．９９３％

　商が３になる確率はｌｏｇ2（１６／１５）＝９．３１１％

　商が４になる確率はｌｏｇ2（２５／２４）＝５．８８９％

　商が１となる確率は４１％で，これはベンフォードの法則，最大桁が１になる頻度ｌｏｇ10２＝０．３０１０よりも高いことになる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝