The pattern is
- Start with 0,2,1,3
- Decrement until you cannot
- 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.
- 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.