343 : 分数数列

任意の正の整数$k$に対して、分数$x_i/y_i$の有限数列$a_i$は次のように定義される：

$a_1 = 1 / k$ $a_i = (x_{i-1}+1)/(y_{i-1}-1)$($i>1$のとき。約分可能な場合は約分する）

$a_i$がある整数$n$になったとき（つまり$y_i=1$になったとき）数列はそこで終了とする。 ここで関数$f(k) = n$と定義する。 例えば$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 ≤ k ≤ 100$について$\sum f(k^3) = 118937$となる。

$1 ≤ k ≤ 2×10^6$について$\sum f(k^3)$を求めよ。