convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

For the recurrence relation:

$f(0)=1$

$f(1)=1$

$f(2)=2$

$f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$

$f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$

(the first numbers of the sequence are: 1, 1, 2, 3, 7, 4, 13, 6, 15, 11, 22, 12, 25, 18, 28)

Given some number $S$, I would like to find $n$ such that $f(n) = S$, using an approach that runs in $O(\log n)$ time. Any ideas or tips how to solve it? I tried substitution so far but didn't get far.

Your recurrence is one of large class of similar ones called "2-regular". These recurrences can be expressed in a number of different ways. For example, it follows from the papers below that there exist square matrices $M_0, M_1$ and vectors $u, v$ such that if the base-2 expansion of $n$ is given by $e_1 e_2 \cdots e_j$, then $$f(n) = u M_{e_1} \cdots M_{e_j} v.$$ The size of the matrices is called the rank; your series seems to have rank 10, from what I can see.

From this expression one can often find, e.g., the asymptotic behavior of the recurrence. But, in general, even basic properties of such sequences (such as "does 0 ever occur?") is undecidable—although often decidable for any particular given sequence.

In your particular case I think one can probably prove with a bit of work that $\liminf f(n)/(n \log n)$ and $\limsup f(n)/(n \log n)$ both exist and are bounded. For $n$ sufficiently large it should be the case that $.39 n \log n ≤ f(n) ≤ .5 n \log n$. This means if you are trying to solve $f(n) = S$ then, for each $S$, there is only a finite range (depending on $S$) that needs to be searched.

This gives an algorithm (once you prove the inequalities) for all $n$ sufficiently large; smaller $n$ can be searched through brute force. This approach using the asymptotic expression will not allow you to solve for $n$ in $O(\log n)$ time, so it does not satisfy your requirements.

However, you can exploit the fact that the two subsequences $(f(2n))_{n≥0}$ and $(f(2n+1))_{n≥0}$ are, individually, monotonically increasing. This means that you can solve $f(n) = S$ through binary search, one for the even indices and one for the odd.

References:

Allouche and Shallit, The ring of $k$-regular sequences, Theor. Comput. Sci. 98 (1992), 163-197. Allouche and Shallit, The ring of $k$-regular sequences, II. Theor. Comput. Sci. 307 (2003), 3-29.