The Puzzle
You begin with
At each step, you may replace aₙ with either:
2aₙ + 1
⌊aₙ / 2⌋ (the floor of half of aₙ)
The question:
Can you reach 2025?
This looks innocent. Double-and-add-one moves tend to grow numbers quickly; dividing by two seems to give you a way to “adjust.” So at first glance, maybe you can hop around and eventually land on 2025.
But reachability problems are rarely about brute force. They’re about structure.
Understanding the Moves
Let’s inspect both operations:
Move 1: 2a + 1
This is the operation that takes a number, shifts its binary digits left, and appends a 1 at the end.
Example:
13 → 27
(1101 → 11011)
This move always creates an odd number.
Move 2: floor(a / 2)
Binary right-shift by one (drop last bit).
Example:
13 → 6
(1101 → 110)
So the two moves let you append 1’s to the right, or chop off rightmost bits.
Now what is the binary of 2025?
Now try to think in binary and answer the question…