A good sequence

Number Theory Level 5

A sequence of real numbers $a_0, a_1, a_2 \ldots$ is said to be good if the following three conditions hold.

The value of $a_0$ is a positive integer.
For each non-negative integer $i$ we have $a_{i+1}=2a_i+1$ or $a_{i+1}=\dfrac{a_i}{a_i+2}$ .
There exists a positive integer $k$ such that $a_k=2014$ .

Find the smallest positive integer $n$ such that there exists a good sequence $a_0, a_1, a_2 \ldots$ of real numbers with the property that $a_n=2014$ .

The answer is 60.

1 solution

Patrick Corn
Jan 5, 2018

Let's run it backwards. Suppose $a_n = 2014.$ Let $b_k = a_{n-k},$ so $b_0 = 2014$ and $b_k = \begin{cases} \frac{b_{k-1}-1}2 &\text{ if } b_{k-1} > 1 \\ \frac{2b_{k-1}}{1-b_{k-1}} &\text{ if } b_{k-1} < 1. \end{cases}$

So we can generate values of $b_k$ recursively until we get to our first positive integer. In fact, $b_{60} = 2014$ is the first positive integer, so $n=\fbox{60}$ and the minimal good sequence ending in $2014$ also starts with $2014.$

I think there is a nice formula for $n$ in general based on the binary expansion of the starting number plus one (2015 in this case), but I haven't quite put all the pieces together. I'll update with a full solution later. Here is a hint: it's not hard to prove that if you add up the numerator and denominator of $b_k,$ the result is always $2015.$

A good sequence

The answer is 60.

1 solution

0 pending reports