Number of steps the path-avoiding snail must take before a step size of $(2n - 1)/2^k$?

Solution 1:

I have no idea about proving maximality, which is probably very difficuly, but the following construction gives an answer that coincides with OP's calculation if $n \leqslant 34$ except for $n=11, 21, 22, 23$, and its slight modification is ok for $n=11, 23$, but not $n=21, 22$.

Game. Consider such a game: we have two natural numbers $(f, b)$ and two types of operations -- to $(f/2, b+f/2)$ (if $f/2$ is natural) and to $(b, f)$. Starting position is $(2^{d(n-1)+1}, 0)$, final position is $(2n-1, \ldots)$, the goal is to get there with minimal number of operations.

The minimal sequence of operations may be reconstructed backwards, doing inverse to the first operation when possible, and inverse of the second otherwise, and consists of $1+d(n-1)+g(n-1)$ operations, where $d(k)$ is the number of digits in binary representation on $k$ and $g(k)$ is the number of groups of repeating digits there.

Example. Consider $n=6$. Then $2^{d(n-1)+1}=16$ and $2n-1=11$, so $$(11=1011_2, 5=0101_2) \twoheadleftarrow (5=0101_2, 11=1011_2) \leftarrow (10=1010_2, 6=0110_2) \twoheadleftarrow (6=0110_2, 10=1010_2) \leftarrow (12=1100_2, 4=0100_2) \twoheadleftarrow (4=0100_2, 12=1100_2) \leftarrow (8=1000_2, 8=1000_2) \leftarrow (16=10000_2, 0)$$ is the sequence with minimal $1+d(101_2)+g(101_2)=7$ operations.

We consider $f$ as the distance forward, and $b$ -- backward, as if snail always looks vertically and alternates segments up and down. Now you can construct snail's walk as follows: make first three moves as right, up, left; then go along the sequence from the previous game, replacing first operations by moves up or down, and second - by moves right; in the end make one move up or down.

Modification. The game may be modified as follows: we have three natural numbers $(f, b_1, b_2)$ and three types of operations -- to $(f/2, b_1+f/2, b_2+f/2)$, to $(b_1, f, 0)$ and to $(b_2, f, 0)$. Starting position is $(2^{d(n-1)+1}, 0, 0)$, final position is $(2n-1, \ldots, \ldots)$, the goal is the same.

Here we consider $b_1$ and $b_2$ as distances backward along left and right sides of snail. Second and third operations should be interpreted as moves left or right according to the situation.

Unfortunately, I can not solve modified game, but computer simulation obtains the same solutions as OP's for $n=11, 23$, but $a(21)=14>13$ and $a(22)=15>14$.

Comment. Feel free to correct my language!