Hopping forever

We claim that Brilli can visit all the odd integers (and $0$ , if you count zero steps as visiting), and none other. We assume that we're making a positive number of steps.

We induct on the number of steps that Brilli will always be on an odd integer. If Brilli makes one step, then it is on either $-1$ or $+1$ , proving the claim. Suppose Brilli makes $n$ steps, with $n \ge 1$ , and is now on an odd integer (the inductive hypothesis). Brilli then makes one more step (to make it $n+1$ steps); note that the length is $2^{n+1-1} = 2^n$ units, an even number. Thus from an odd integer, an even-length step must again land on an odd integer. This proves the claim; no even integer can be visited in a positive number of steps. ( $0$ is "visited" in zero steps, and can never be visited again.)

Now, we claim that all odd integers can be visited. In fact, to visit an odd integer $n$ , Brilli only needs $\lfloor \log_2 |n| \rfloor + 1$ steps. (This is the number of digits of $n$ in binary.) Note that it's enough to prove this for positive odd integers; if we can visit $n$ with $n > 0$ , then we can also visit $-n$ by reversing the directions of all the steps taken. To prove we can visit all positive odd integers, we give a constructive algorithm.

The simplest way to visit $n$ , assuming we may skip steps, is simply to use the binary representation; for example, $83 = 2^6 + 2^4 + 2^1 + 2^0$ , so we move $1$ to the right, move $2$ to the right, skip the step with $4$ , skip the step with $8$ , move $16$ to the right, skip the step with $32$ , and move $64$ to the right. The problem, of course, is that we may not skip steps.

The trick is, if we need to move $2^p$ to the right and then skip the steps $2^{p+1}, 2^{p+2}, \ldots, 2^q$ , we can instead move $2^p, 2^{p+1}, \ldots, 2^{q-1}$ to the left and then $2^q$ to the right. The total displacement is still $-(2^p + 2^{p+1} + \ldots + 2^{q-1}) + 2^q = 2^p$ to the right. Thus instead of moving $2$ to the right and skipping $4$ and $8$ , we move $2$ and $4$ to the left and move $8$ to the right. Likewise, we move $16$ to the left and $32$ to the right. Thus, to make $83$ , we move $0 \to 1 \to -1 \to -5 \to 3 \to -13 \to 19 \to 83$ , as desired.

It's trivial to show that by applying this trick as appropriate, we can visit all positive odd integers. Moreover, the number of steps is equal to the exponent of the largest power of $2$ used, plus one; in the example above, we used $7$ steps, since it's the exponent of the largest power of $2$ (namely $2^6$ ) plus $1$ . However, this is also the definition of $\lfloor \log_2 n \rfloor + 1$ . This proves that $f(n) \le \lfloor \log_2 n \rfloor + 1$ , since we can reach $n$ in that many steps.

To show that $f(n) \ge \lfloor \log_2 n \rfloor + 1$ , simply note that if we use less steps, the only steps available are in the form $2^0, 2^1, 2^2, \ldots, 2^{k-1}$ , while $2^k \le n$ . Thus the largest number we can reach is $2^0 + 2^1 + 2^2 + \ldots + 2^{k-1} = 2^k - 1 < 2^k \le n$ , so we can't reach $n$ . This proves the claim.

Finally, we need to compute $\sum_{n=1}^{2015} f(n)$ . We can use computer to do this, but there's a simple manual way to do this:

Observe that for $n$ satisfying $2^k \le n < 2^{k+1}$ , we have $f(n) = k+1$ . Additionally, for positive integer $k$ , there are $2^{k-1}$ such odd integers satisfying $2^k \le n < 2^{k+1}$ . (For $k = 0$ , there is one, $n = 1$ .) Thus we can simplify the expression:

$\displaystyle\begin{aligned} \sum_{n=1}^{2015} f(n) &= f(1) + \sum_{n=2}^{1023} f(n) + \sum_{n=1024}^{2015} f(n) \\ &= 1 + \sum_{k=1}^9 \sum_{n=2^k}^{2^{k+1}-1} f(n) + \sum_{k=512}^{1007} (f(2k)+f(2k+1)) \\ &= 1 + \sum_{k=1}^9 2^{k-1} \cdot (k+1) + \sum_{k=512}^{1007} (0+11) \\ &= 1 + \sum_{k=1}^9 2^{k-1} \cdot (k+1) + 496 \cdot 11 \\ &= \boxed{10065} \end{aligned}$