Problem 343

Fractional Sequences

For any positive integer `k`, a finite sequence a_{i} of fractions x_{i}/y_{i} is defined by:

a_{1} = 1/`k` and

a_{i} = (x_{i-1}+1)/(y_{i-1}-1) reduced to lowest terms for `i`>1.

When a_{i} reaches some integer `n`, the sequence stops. (That is, when y_{i}=1.)

Define f(`k`) = `n`.

For example, for `k` = 20:

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

So f(20) = 6.

Also f(1) = 1, f(2) = 2, f(3) = 1 and Σf(`k`^{3}) = 118937 for 1 `k` 100.

Find Σf(`k`^{3}) for 1 `k` 210^{6}.

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**