You can do the following considerations, at first for the Grundy values (A025480) which are given by

$a\left(2n\right) = n \quad \mathrm{and} \quad a\left(2n+1\right) = a\left(n\right)$

At first, we will define $m^{e} := 2n$ (m is even) respectively $m^{o} := 2n + 1$ (m is odd) and hence, we can rewrite this to

$a\left(m^{e}\right) = \frac{m^{e}}{2} \quad \mathrm{and} \quad a\left(m^{o}\right) = a\left(\frac{m^{o}-1}{2}\right)$

If we look at our examples and the definition of Grundy values, we see that starting by any $m^{o}$ the calculation of the final element stops if we reach a $m^{e}$ after an certain number of odd $m^{o}$'s. So, the $m^{e}$ are our termination cases of element computation.

We will determine an equation which connects the starting element $m_{1}^{o}$ with the final termination element $m_{i+1}^{e}$.

For this we get in general for only odd steps:
$m_{i}^{o} = \frac{m_{1}^{o} - \sum_{k=0}^{i-2}2^{k}}{2^{i-1}}\\
= \frac{m_{1}^{o} - 2^{0} - \sum_{k=1}^{i-2}2^{k}}{2^{i-1}}\\
= \frac{m_{1}^{o} - 1 - 2\frac{2^{i-2} - 1}{2 - 1}}{2^{i-1}}\\
= \frac{m_{1}^{o} - 2^{i-1} + 1}{2^{i-1}}$

for all $i \geq 2$, $n \in \mathbb{N}$. To determine the final sequence element, we have to do one even step:
$n_{i+1}^{e} = \frac{m_{1}^{o} - 2^{i-1} + 1}{2^{i-1}} \cdot \frac{1}{2}\\
= \frac{\left(2n_{1}^{o} + 1\right) - 2^{i-1} + 1}{2^{i}}\\
= \frac{2n_{1}^{o} - 2^{i-1} + 2}{2^{i}}\\
= \frac{n_{1}^{o} - 2^{i-2} + 1}{2^{i-1}}$

with $m_{1}^{o} = 2n_{1}^{o} + 1$ and $m_{i}^{e} = 2n_{i+1}^{e}$. We will solve the equation for $n_{1}^{o}$:

$2^{i-1}n_{i+1}^{e} = n_{1}^{o} - 2^{i-2} + 1$

$n_{1}^{o} = 2^{i-1}n_{i+1}^{e} + 2^{i-2} - 1$

Now, we want to use the result from above for some distance examinations.

We want to determine the first appearances of a particular number within the Grundy sequence.

At first at all, we have the first appearance of a number simple given by an even step. So, $n_{i+1}^{e}$ appears for $m_{i+1}^{e} = 2n_{i+1}^{e}$, because of $a\left(m_{i+1}^{e}\right) = a\left(2n_{i+1}^{e}\right) = n_{i+1}^{e}$.

So, to determine when this number $n_{i+1}^{e}$ appears the next, second time, within the Grundy sequence, we simple have take the equation for $i=2$:

$n_{1,1}^{o} = 2^{2-1}n_{i+1}^{e} + 2^{2-2} - 1\\
= 2n_{i+1}^{e}$

Next, we are interested in the positions of sequence elements.

The position $pos$ of a number $n_{i+1}^{e}$ within a simple integer sequence $0,1, \dots, k-2, k-1$ is given by

$n_{i+1,pos}^{e} = n_{i+1}^{e}$

and the position $pos$ of numbers $n_{i}^{u}$ respectively $n_{i}^{e}$ are given by

$n_{i,pos}^{o} = 2n_{i}^{o} + 2 \quad \mathrm{and} \quad n_{i,pos}^{e} = 2n_{i}^{e} + 1$

Now, we want to calculate the position distance for our given problem statement sequence.

$|n_{1,1,pos}^{o} - n_{i+1,pos}^{e}| = 2n_{1}^{o} + 2 - n_{i+1}^{e}\\
= 2\left(2n_{i+1}^{e}\right) + 2 - n_{i+1}^{e}\\
= 4n_{i+1}^{e} + 2 - n_{i+1}^{e}\\
= 3n_{i+1}^{e} + 2$

We start counting the sequence by $1$. Since we want to have a look at the original problem statement with a given pre-sequence $\{0,1,\dots, k-2,k-1\}$, we have to resubstitute the solution by $n_{i+1}^{e} - 1$ to

$|n_{1,1,pos}^{o} - n_{i+1,pos}^{e}| = 3\left(n_{i+1}^{e} - 1\right) + 2\\
= 3n_{i+1}^{e} - 3 + 2\\
= 3n_{i+1}^{e} - 1$

I also wrote it all together in a pdf version with some additional calculations. You can find it here: more detailed pdf Version