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.

• this is a programming problem. Given some number S find n so that f(n) = S. I'm looking for an exact expression, if possible or something else that can help me devise an algorithm. Nov 30, 2014 at 21:24
• For $n$ sufficiently large it should be the case that $.39 n \log n \leq f(n) \leq .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. Nov 30, 2014 at 21:47
• the maximal S is $10^{25}$, doesn't that leave a pretty wide range? Nov 30, 2014 at 22:24
• OK, now I see how to do it in log n steps under the unit cost model. The idea is that the two subsequences $(f(2n))_{n \geq 0}$ and $(f(2n+1))_{n \geq 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. Dec 1, 2014 at 10:21
• I don't. By "steps" I meant queries to f. You can compute values of f in O(log n) time using dynamic programming (or "memoization"). If one is really being careful, one should count the sizes of the numbers being operated on, too, so I guess the total cost is going to be something like O((log n)^3) bit operations. Dec 3, 2014 at 14:52