A new stunt at the flea circus

Question

The ringmaster of a flea circus puts a flea onto the integer $0$. Whenever the ringmaster shouts "Hop!", the flea jumps from its current integer $n$ to one of the numbers $n+2$, $n-2$, $2n$ and $n/2$. The flea only visits positive integers, and it must not visit any number twice.

Question: Is it possible that the flea visits every positive integer exactly once?

Answer 1

Yes.

Start with
0,2,1,3,6,4,8,10,5,7,9,11,22,20,18,16,14,12,24,26,13,15,17,19,21,23,25,27...

The pattern is

• Start with 0,2,1,3
• Double
• Decrement until you cannot
• Double
• Increment
• Divide
• Increment until the current value is the highest yet
• Repeat all but line 1

This works by filling in the evens and odds in parallel, doing evens (mostly) in reverse and odds forward, using doubling and dividing to switch between them.

Proof:

• We start on an odd number, n, with all lower numbers filled.
• We then move to 2n, then decrement until n+1. All odd numbers up to n and all even numbers up to 2n are done.
• We double, to 2n+2, increment to 2n+4, then divide to n+2. Now all even numbers up to 2n+4 and all odd numbers up to n+2 are done.
• We increment until we are at 2n+5.
• Now all odd numbers up to 2n+5 are done, and all even numbers up to 2n+4 i.e. all numbers up to 2n+5, and we are on an odd number. This meets the initial conditions, so we can repeat with this as our new value of n.

Answer 2

I'm actually not entirely sure if this strategy is proof one way or another :P

We can reach all positive integers up to any arbitrary odd integer $N$.

We do this by simply

Hopping to 2, then to 1 (n/2) and then going up to our point $N$, we then jump to $2N$ and hop down with -2 until we reach 4. We've no covered all integers from $1$ to $N$, since we can pick $N$ to be any odd integer, we can visit every positive integer. However, it's quite clear that there's some we don't visit because we visit odd integers higher then our arbitrary number, but if we wanted to include those numbers we just need to pick our $N$ higher

(from here on, the post is a lie thanks to frodo)

We can also note that there's no strategy that does better

because we're not allowed to visit numbers more then once, and because there's no combination of operators that allows us to visit all integers we 'pass' without backtracking entirely we have to conclude that either we visit all even numbers first, or we visit all odd numbers first. If we visit all odd first then using $2n$ is the only way to get to an even number (as we did). If we visit all even numbers first then using $n/2$ is the only way to get to an odd number, our arbitrary even number has to furfil $E/2$=odd, so $E=2N$, this. In both cases you get the exact same distribution, where all numbers from $1$ to $N$ are visited exactly once.

*note that this doesnt take into acount flea working hours, mortality, drug problems or wavering dedication