I'm on an infinite number line. I start at 0 and at each step can move to the left or to the right. At the $n$'th step my step length is n.
So my motion can be $1$ move to the right, $2$ moves to the left and then $3$ moves to the right.
What is the minimum number of steps required to reach $n$-th position?
I'm looking for closed form solutions - I've realised that it is always possible to reach the $n$-th position in atmost $2n-1$ moves where $n>0$ and $-2n$ moves where $n<0$. How do I get a closed form?
I tried to formulate the problem as a recurrence relation, where $f(n):\mathbb{Z}\to\mathbb{N}$ is the minimum number of steps needed to reach the $n$-th position and ended up with this $$f(n\pm f(n))=f(n)-1$$ where the $\pm$ means that it's sometimes plus and sometimes minus. This may seem to be rubbish to you, but this is all I could do.
Please help, thanks.
The answer is tabulated out to $n=100$ at OEIS. There's a conjecture there:
Choose $k$ so that $t(k)\le n<t(k+1)$ where $t(n)$ is the $n$-th triangular number $t(n)=n(n+1)/2$. If $n=t(k)$, $a(n)=k$, otherwise if $k$ is odd then $a(n)=k+2$ if $n-t(k)$ is odd, $a(n)=k+1$ if $n-t(k)$ is even, else if $k$ is even than $a(n)=k+1$ if $n-t(k)$ is odd, $a(n)=k+3$ if $n-t(k)$ is even. (This has been verified for $n$ up to 100.)
At this page, it is tabulated out to $n=10,000$.