Problem 433 「ユークリッドの互除法のステップ数」

x0y0 の最大公約数をユークリッドの互除法 (Euclid's algorithm) を用いて割り出す時に必要となるステップ数を E(x0, y0) としよう. より形式的に表すと:
x1 = y0, y1 = x0 mod y0
xn = yn-1, yn = xn-1 mod yn-1
E(x0, y0) は yn = 0 となるような最小の n である.

E(1,1) = 1, E(10,6) = 3, そして E(6,10) = 4 であることがわかっている.

1 ≤ x,y ≤ N における E(x, y) の和を S(N) と定義しよう.
S(1) = 1, S(10) = 221, そして S(100) = 39826 であることがわかっている.

S(5·106) を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-06-23 (日) 00:33:49 (1519d)