A game involving repeated hopping by powers of 2 I have a number $n$. The $2$-adic valuation of $n$, which I denote as $v(n)$, is the greatest exponent of $2$ such that $2^{v(n)}$ divides $n$. For instance, $v(24)=3$ because $2^3=8$ is the greatest power of $2$ that divides $24$.
Now define a decreasing function $f:\mathbf N\to\mathbf N$ by
$$
f(n)=n-2^{v(n)}.
$$
Here is a game: given $n$, I can perform one of two moves:

*

*Decrement $n$ (that is, $n\mapsto n-1$)


*Or, apply $n\mapsto f(n)$.
Is there an explicit strategy or algorithm to find a positive number $m<n$ such that I maximize the minimum number of moves from $n$ down to $m$?
I am quite stuck on this game: my intuition is that, in order to maximize the minimum number of moves from $n$ to $m$, we want to make sure that we don't make too many large $n\mapsto f(n)$ hops; beyond that, I'm not sure how to approach the problem. Any help would be appreciated!
 A: It probably helps to write out the numbers in binary.  Then your moves are equivalent to:

*

*Take the lowest bit of $n$ that is currently $1$ and set it to $0$, then set all lower bits (which were $0$) to $1$.

*Take the lowest bit of $n$ that is currently $1$ and set it to $0$.

So, how do we get as quickly as possible from $n$ to $m$ (where $0 < m < n$)?
For this, it turns out to be useful to define $b(n)$ for $n ≥ 1$ as the "bit length" of $n$, i.e. the unique integer that satisfies $2^{b(n)} ≤ n < 2^{b(n)+1}$.  (Equivalently, we may define $b(n) = \lfloor \log_2 n \rfloor$.)  Clearly $b$ is a monotone function, so $n > m$ implies $b(n) ≥ b(m)$.
Now, let's consider a few different cases:

*

*If $m = 2^{b(n)}$, then the fastest way to get from $n$ to $m$ is to repeat move 2 to clear all lower bits of $n$.


*If $m > 2^{b(n)}$, and thus $b(m) = b(n)$, then the sequence of moves needed to get from $n$ to $m$ are exactly the same as the moves needes to get from $n - 2^{b(n)}$ to $m - 2^{b(n)}$.  These moves will only affect the lower $b(n)$ bits of $n$ and leave the highest bit (which is the same for $n$ and $m$) untouched.


*If $m < 2^{b(n)}$, and thus $b(m) < b(n)$, then the only way to get from $n$ to $m$ is to first get from $n$ to $2^{b(n)}$, then use move 1 to get from $2^{b(n)}$ to $2^{b(n)}-1$, and then get from there to $m$.  (This follows from the observation that applying move 1 to a power of 2 is the only way to decrease $b(n)$ without going all the way down to zero!)
Applying those three rules, we can in fact recursively find the fastest path between any two distinct numbers. Here's a quick Python program that does just that:
def count_trailing_zero_bits(n):
  v = 0
  while n & 2**v == 0:
    v += 1
  return v

def fastest_path(n, m):
  k = 2**(n.bit_length() - 1)
  if m == n:
    return (n,)
  elif m == k:
    v = count_trailing_zero_bits(n)
    return (n,) + fastest_path(n - 2**v, m)
  elif m > k:
    return tuple(x + k for x in fastest_path(n - k, m - k))
  else:
    return fastest_path(n, k) + fastest_path(k - 1, m)

for n in range(1, 32):
  for m in range(1, n):
    print(" -> ".join(str(i) for i in fastest_path(n, m)))

But what about finding the $m > 0$ that is the most steps away from a given $n$?  Well, looking at the output of the script above, it strongly suggests that $m = 1$ is the most distant number from any $n$.
So how many steps does it take to get from $n$ down to $1$?

*

*If $n = 2^b$, then going from $n$ to $2^{b-1}$ takes $b$ steps: first a single move 1 to get from $2^b$ to $2^b-1$, and then $b-1$ repetitions of move 2 to clear all but the highest bit of $2^b-1$.

*Thus, getting from $2^b$ all the way down to $1$ takes $1 + 2 + 3 + \dots + b = \frac{b^2 + b}{2}$ steps.

*Finally, if $n$ is not (necessarily) a power of 2, then getting down to $1$ takes $\frac{b(n)^2 + b(n)}{2} + c(n) - 1$ steps, where $b(n)$ is as defined above, and $c(n)$ is the number of $1$ bits in $n$ when written out in binary.

I haven't actually finished a rigorous proof that getting to $1$ indeed takes the most steps from any starting point $n$, but I'm pretty sure that all it takes is some grunt work.  In particular, it should be sufficient to show that if $1 < m < n$ and $m$ is odd, then reaching $m - 2^{b(m)}$ from $n$ must take more steps than reaching $m$.
(An even number $m$ cannot possibly be the most distant number from any $n > m$: since move 2 only yields even numbers, the only way to reach $m-1$ is by move 1 from $m$, and thus the shortest path to from $n$ to $m-1$ must be one step longer than the shortest path to $m$!)
