*[[Problem 343:http://projecteuler.net/problem=343]] 「分数数列」 [#k0698816]

ある正の整数 &tex{k}; において, 分数 x&tex{_{i}};/y&tex{_{i}}; による有限数列 a&tex{_{i}}; は次のように定義される :

a&tex{_{1}}; = 1 / &tex{k};~
a&tex{_{i}}; = (x&tex{_{i-1}};+1)/(y&tex{_{i-1}};-1) [ ただし, &tex{i};>1 のとき, 約分可能な場合は約分する ]

a&tex{_{i}}; がある整数 &tex{n}; になったとき, 数列はそこで終了とする. (つまり, y&tex{_{i}};=1になった時)~
ここで関数 f(&tex{k};) = &tex{n}; と定義する. ~
例えば, &tex{k}; = 20 のとき, 

1/20 → 2/19 → 3/18 = 1/6 → 2/5 → 3/4 → 4/3 → 5/2 → 6/1 = 6

したがって f(20) = 6 となる.

同様に, f(1) = 1, f(2) = 2, f(3) = 1, そして 1 ≤ &tex{k}; ≤ 100 のとき, Σf(&tex{k^{3}};) = 118937 となる.

1 ≤ &tex{k}; ≤ 2×10&tex{^{6}}; のときの Σf(&tex{k^{3}};) を求めよ.

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS