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 \gt 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 \to 2/19 \to 3/18 = 1/6 \to 2/5 \to 3/4 \to 4/3 \to 5/2 \to 6/1 = 6$

So $f(20) = 6$.

Also $f(1) = 1$, $f(2) = 2$, $f(3) = 1$ and $\sum f(k^3) = 118937$ for $1 \le k \le 100$.

Find $\sum f(k^3)$ for $1 \le k \le 2 \times 10^6$.

The problem involves understanding how specific attributes of the number “k” affects the outcome “n”. More specifically, as is outlined in the problem statement, the chain always ends at “n” when “y_i = 1” or in other words, when the denominator is exactly 1.

If we examine at the chain one step at a time, we can see that adding 1 to the numerator and subtracting 1 from the denominator has the effect of changing the value from some p/q into (p+q)/q. For example, 1/3 becomes 4/2 or 2, and 1/5 becomes 6/4 or 3/2, and so on.

The attributes of k that are going to affect this process are its prime factors. In particular, since the numerator and denominator change at each step, this acts almost like moving through the factors of k.

For example, consider k = 8 = 2^3, the chain will first increment from 1/8 to 9/7 where it hits its first prime factor, then on to hit 16/6 which reduces to 8/3, and then hits 11/2, and finally reaching 13/1 which stops the sequence, giving n = 13.

Observing these steps, we see that the sequence stops when the numerator is exactly 1 unit larger than the denominator.

From one example, we can hypothesize a procedure: for a given k with prime factorization p1^a1 * p2^a2 * … * pr^ar, we will compute n by computing (p1 + a1) * (p2 + a2) * … * (pr + ar), given that k corresponds to computed prime factorization.

With the above hypothesis, we need to compute the sum f(k^3) for 1 <= k <= 2*10^6, i.e., we need to compute the sum for each k from 1 to 2*10^6 of (p1 + a1) * (p2 + a2) * ... * (pr + ar) where p1^a1 * p2^a2 * ... * pr^ar is the prime factorization of k^3. This is a computation that can be optimized with computational arithmetic techniques, through using memoization to store partial computations and factorizations, or using prime factoring tricks to reduce the computations. Nonetheless, you need a computer program to solve this problem, as doing it by hand would be extremely time-consuming.

More Answers: