Similarly... http://artofproblemsolving.com/community/c6h209596p1154283

(1) If $a_{i+1}$ is rational, then also $a_i=(a_{i+1}-1)/2$ and $a_i=2a_{i+1}/(1-a_{i+1})$ must be rational. Similarly, if $a_{i+1}$ is positive, then also $a_i$ must be positive. As the sequence contains the positive rational number $2014$, all its terms are positive rational numbers. (2) Let us write $a_i=x_i/y_i$ with positive integers $x_i$ and $y_i$ that are relatively prime. Then $a_{i+1}=2a_i+1=(2x_i+y_i)/y_i$ and $a_{i+1}={a_i}/({a_i + 2})=x_i/(x_i+2y_i)$. As $x_i$ and $y_i$ are relatively prime, the greatest common divisor of $2x_i+y_i$ and $y_i$ is either $1$ or $2$, and also the greatest common divisor of $x_i$ and $x_i+2y_i$ is either $1$ or $2$. (3) Hence we either have $x_{i+1}+y_{i+1}=x_i+y_i$ or $x_{i+1}+y_{i+1}=2(x_i+y_i)$. (4) Now assume that $a_k=2014$ for some $k\ge1$. Then $x_k+y_k=2014+1=2015$, which implies $x_i+y_i=2015$ for all $i=0,1,\ldots,k$. In particular either (i) $x_{i+1}=x_i+\frac12y_i$ and $y_{i+1}=\frac12y_i$ with $y_i$ even, or (ii) $x_{i+1}=\frac12x_i$ and $y_{i+1}=\frac12x_i+y_i$ with $x_i$ even. Case (i) yields $x_i=x_{i+1}-y_{i+1}$ and $y_i=2y_{i+1}$. Case (ii) yields $x_i=2x_{i+1}$ and $y_i=y_{i+1}-x_{i+1}$ (5) Working backwards from $(x_k,y_k)=(2014,1)$ and keeping the positivity of $x_i$ and $y_i$ in mind, we get $(2014,1) ~\to~ $ $~\to~ (2013,2) ~\to~ (2011,4) ~\to~ (2007,8) ~\to~ (1999,16) ~\to~ (1983,32) ~\to~ (1951,64)$ $~\to~ (1887,128) ~\to~ (1759,256) ~\to~ (1503,512) ~\to~ (991,1024) ~\to~ (1982,33) ~\to~ (1949,66)$ $~\to~ (1883,132) ~\to~ (1751,264) ~\to~ (1487,528) ~\to~ (959,1056) ~\to~ (1918,97) ~\to~ (1821,194)$ $~\to~ (1627,388) ~\to~ (1239,776) ~\to~ (463,1552) ~\to~ (926,1089) ~\to~ (1852,163) ~\to~ (1689,326)$ $ ~\to~ (1363,652) ~\to~ (711,1304) ~\to~ (1422,593) ~\to~ (829,1186) ~\to~ (1658,357) ~\to~ (1301,714)$ $~\to~ (587,1428) ~\to~ (1174,841) ~\to~ (333,1682) ~\to~ (666,1349) ~\to~ (1332,683) ~\to~ (649,1366)$ $~\to~ (1298,717) ~\to~ (581,1434) ~\to~ (1162,853) ~\to~ (309,1706) ~\to~ (618,1397) ~\to~ (1236,779)$ $~\to~ (457,1558) ~\to~ (914,1101) ~\to~ (1828,187) ~\to~ (1641,374) ~\to~ (1267,748) ~\to~ (519,1496) $ $~\to~ (1038,977) ~\to~ (61,1954) ~\to~ (122,1893) ~\to~ (244,1771) ~\to~ (488,1527) ~\to~ (976,1039)$ $ ~\to~ (1952,63) ~\to~ (1889,126) ~\to~ (1763,252) ~\to~ (1511,504) ~\to~ (1007,1008) ~\to~ (2014,1)$ (6) Hence, the smallest possible index $k$ is $k=60$ for the starting value $a_0=2014$.

Did anyone bash it all out (I tried, but I think I only went to some number less than 60 or I calculated wrong)?

I did by hand. However the proof can be shortened if one look at the sequence carefully. In particular each of the pairs shown has an interesting structure.

There's no need to bash. Note that the sum of denominator and numerator of every $ a_i $ must be $ 2015 $ (this also proves that $ a_0 = 2014 $) and now note that the numerator of $ a_{i + 1} $ is the numerator of $ a_i $ multiplied by $ \frac{1}{2} $ mod $ 2015. $ The order of $ 2 $ mod $ 2015 $ is $ 60 $ so this is the answer and we're done.

What would the difficulty of this problem be, compared to other APMO #3's?

I solve it in the same way...but is it an acceptal solution???

Notice that $\frac{1}{a_{i+1}+1}=\frac{1}{2(a_{i}+1)}$ or $\frac{1}{a_{i+1}+1}=\frac{1}{2(a_{i}+1)}+\frac{1}{2}$ And we use binary representation ... finally smallest is 60

Making the substitution $b_i=\frac{2^i}{a_i+1}$, we have that either $b_{i+1}=b_i$ or $b_{i+1}=b_i+2^i$ for all nonnegative $i$. As $b_0$ is a unit fraction and we are adding integers to it and hope to obtain something of the form $\frac{2^n}{2015}$, we must have that $a_0=2014$ so $b_0=\frac{1}{2015}$. Now, if $b_n=\frac{2^n}{2015}$, then $b_n-b_0=\frac{2^n-1}{2015}$ is an integer. Hence, $n$ is divisible by the order of 2 mod 2015, which can easily be computed to be 60. A construction for 60 follows from the binary representation of $\frac{2^{60}-1}{2015}$, as it is clear that we can achieve $b_n=b_0+k$ for any nonnegative integer $k<2^n$.

The answer is $\boxed{60}$. We will handle the lower and upper bound concurrently. Reverse the sequence by $b_i = a_{n-i}$. It's easy to see that we must have $$b_{i+1} = \begin{cases} \dfrac{b_i-1}{2} & b_i>1 \\ \dfrac{2b_i}{1-b_i} & b_i<1 \end{cases}$$Thus if we let $b_i = \tfrac{r}{s}$, we get $b_{i+1}\in\{\tfrac{r-s}{2s}, \tfrac{2r}{s-r}\}$. Thus we define recursive sequence by $r_0=2014$, $s_0=1$ and $$(r_{i+1}, s_{i+1}) = \begin{cases}(r_i-s_i, 2s_i) & r_i>s_i \\ (2r_i, s_i-r_i) & r_i < s_i\end{cases}$$Then we would have $b_i=\tfrac{r_i}{s_i}$. The key observation is $r_i+s_i$ is constant, hence it must equal to $2015$. Thus actually, $$s_{i+1} = 2s_i\pmod{2015}\implies s_i = 2^i\pmod{2015}$$Hence in order to make $a_0$ an integer, we must have $b_n\in\mathbb{Z}$ or equivalently $s_n\mid 2015$. This is possible if and only if $s_n=1$ and $2^n\equiv 1\pmod{2015}$. It's easy to check that $\mathrm{ord}_{2015}(2)=60$ thus we must have $60\mid n$. The construction has been implicitly done as the sequence can be reversed uniquely.

We claim the answer is 60. Let $b_i=a_i+1$ so that $$b_{n+1}=2b_n$$or $$b_{n+1}=\frac{2b_n}{b_n+1}.$$Essentially, each time we double it, and we choose whether or not to divide by $b_n+1.$ The next section of this solution will gradually build up to this claim: Claim: If it eventually gets to 2015, then we must have $b_0=2015.$ To show this, we will prove two sub-claims: SC1: Suppose $p$ is an odd prime. If $v_p(b_n)\leq 0$, then $v_p(b_{n+1})\leq 0$ as well. Clearly, this is true if the doubling route is taken. Otherwise, $$v_p(b_{n+1})=v_p(b_n)-v_p(b_n+1).$$If $v_p(b_n)=0$, then $v_p(b_n+1)$ is nonnegative, which shows the difference is nonpositive. Otherwise, if $v_p(b_n)<0$, then $v_p(b_n+1)=\min(v_p(b_n),0)=v_p(b_n),$ so we would have $v_p(b_{n+1})=0.$ This shows this sub-claim. This essentially says that if $b_0$ does not have a prime factor $p$, then it will never gain that factor. Thus, $b_0$ must have $5,13,31$ as prime factors. SC2: Suppose $p$ is any prime (possibly 2). If $v_p(b_n)\geq 1$, then $v_p(b_{n+1})\geq v_p(b_n)$ as well. This is just because if the numerator of $b_n$ is divisible by $p$, then $b_n+1$ is not, so the division by $b_n+1$ can not negatively affect the $v_p$, hence proved. This shows that given any prime factor that $b_0$ has, it will always stay, and its exponent cannot decrease Thus, combined with SC1, this shows that $b_0=2015$, since if $b$ contains a prime factor that is not $5,13,31$, that bad prime factor will stay so it cannot be 2015, and if any of $5,13,31$ has an exponent at least 2, the exponent will also stay at least 2, so it also can't become 2015. Thus, we must have $b_0=2015.$ Write it has $$b_0=\frac{2015}{1}.$$Of course, from SC2, we can never let it be even, so the first step must be to take the other route, giving $$b_1=\frac{4030}{2016}=\frac{2015}{1008}.$$When the denominator is even, say $\frac{2015}{2k}$, then if we take the second route, what will happen is $$\frac{\frac{4030}{2k}}{\frac{2015}{2k}+1}=\frac{4030}{2015+2k},$$but the denominator here is odd, so now the $v_2$ is positive, which by SC2 makes it impossible to reach 2015. Thus, when the denominator is even, we must double it, which makes the denominator go from $d$ to $d/2$. If the denominator is odd, doubling it will make the $v_2$ positive, which can't happen, so we must take the second route, which makes the denominator go from $d$ to $(2015+d)/2$. Therefore, what happens to the denominator is: If it is even, it divides by 2. If it is odd, then it adds 2015 and divides by 2. This is just dividing by 2 when working mod 2015, so the answer is simply the order of 2 mod 2015, which is $\boxed{60}.$

This is truly the best AIME problem of all time. I'm really curious as to how this specific recurrence was contrived as to make this problem so interesting.... The answer is $60$. Let $\{ b \}$ be a sequence such that $b_0 = 2014$ and either \[b_i = \frac{b_{i-1} - 1}{2}\]or \[b_i = \frac{2b_{i-1}}{1-b_{i-1}}.\]So, $\{ b \}$ is just $\{ a\}$ in reverse. Note that we actually don't have a choice at each step of our recursion, because $\{ a\}$ is always positive, hence $\{ b \}$ is also always positive. If we let $b_i = \frac{m_i}{n_i}$, we have that \[(m_i, n_i) = (m_{i-1} - n_{i-1}, 2n_{i-1})\]if $m_{i-1} > n_{i-1}$ or \[(m_i, n_i) = (2m_{i-1}, n_{i-1} - m_{i-1}) \]if $m_{i-1} < n_{i-1}$. So, $m_i + n_i$ is invariant at $2015$. In fact, $\gcd (m_i, n_i)$ always equals $1$, due to the Euclidean algorithm; in particular, $\gcd (m-n, 2n) = \gcd (m-n, n)$ since $m-n$ is odd since $m+n = 2015$. This means that $a_0 = 2014$. Letting $n_i = 2015-m_i$, we can rewrite our recursion as \[m_i = 2m_{i-1}\]if $2m_{i-1} < 2015$ and \[m_i = 2m_{i-1} - 2015\]if $2m_{i-1} > 2015$. In other words, $m_i = 2m_{i-1} \pmod{2015}$. The smallest $k$ such that $2^k \equiv 1 \pmod{2015}$ is $k = 60$, hence $m_{60} = m_0 = 2014$, so our final answer is $\boxed{60}$.

\begin{lemma} all $a_i$ are positive \end{lemma} \begin{proof} Since $a_0$ is positive, we can see that both recursive relations map positives to positives. \end{proof} We can see that looking at the sequence backwards (that is $a_n$ is the first term), every operation is forced. More specifically $2a_i + 1$ maps to $(1, \infty)$ and $\frac{a_i}{a_i+2}$ maps to $(0, 1)$. Finding the inverse of these operations we find that they are $a_i = \frac{a_{i+1}-1}{2}$ and $a_i = \frac{2a_{i+1}}{1 - a_{i+1}}$ respectively \begin{lemma} all $a_i$ can be expressed as $\frac{x}{y}$ (not necesarrily relatively prime) where $m+n= 2015$ \end{lemma} \begin{proof} We prove the result by induction. Our base case is obvious. Now for the inductive step. Considering the first recursive relation we see that we would have $\frac{\frac{x}{y} - 1}{2} = \frac{x-y}{2y}$ summing gives the result. For the other recursive relation we can see that $\frac{\frac{2x}{y}}{\frac{y - x}{y}} = \frac{2x}{y-x}$ summing gives the result \end{proof} \begin{lemma} When $a_i$ is expressed as $\frac{x}{y}$ where $x + y = 2015$, we claim that $2^{n - i} \equiv y \pmod{2015}$. \end{lemma} \begin{proof} We prove the result by indcution. Our base case is obvious. Now for the inductive step. We can see that the first recursive relation happens when $x > y$ we can see that our $y$ becomes $2y$ which is what we would expect. We can see that the second recursive relation happens when $y > x$ (not it is impossible to have $x = y$). We can see that $y$ becomes $y - x$ in this case. Thus we need to prove that for $y > x$ and $x+y = 2015$, $2y \equiv y - x \pmod{2015}$. Subtracting $x + y$ from the LHS, we get $y - x \equiv y - x \pmod{2015}$ \end{proof} We want $y = 1$ specifically our answer is $\boxed{ord_{2015}(2)}$. $\blacksquare$

The answer is $60$. Notably it is easy to verify that if $a_{i+1} = \frac{2015-b_{i+1}}{b_{i+1}}$ then $a_i = \frac{2015 - b_i}{b_i}$ and $b_i \equiv 2 b_{i+1} \pmod {2015}$ and $b_i \in (0, 2015)$. Now $ord_{2015}(2) = lcm\left(ord_{5}(2), ord_{13}(2), ord_{31}(2)\right) = 60$, so the answer is $60$ starting from $a_0 = 2014$ since this is the only integer of such form.

Create the transformed "backwards" sequence $\{c_i\}$ with $c_i = \frac{2015}{a_i+1}$, which gives \[c_0 = 1, c_{i+1} = 2c_i \text{ or } 2c_i-2015.\] We require $c_n \mid 2015$ and $c_n \in [0,2015]$. Notice that once $c_i$ can't return to this interval once it leaves, so we simply have that $c_i$ is the remainder when $2^i$ is divided by 2015. Thus the only way for $c_n \mid 2015$ is if \[2^n \equiv 1 \pmod{2015} \implies n = \operatorname{ord}_{2015} 2 = \operatorname{ord}_{5 \cdot 13 \cdot 31} 2 = \boxed{60}. \quad \blacksquare\]