9
$\begingroup$

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.

$\endgroup$

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ 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. $\endgroup$
    – Boklucius
    Nov 30, 2014 at 21:24
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 30, 2014 at 21:47
  • $\begingroup$ the maximal S is $10^{25}$, doesn't that leave a pretty wide range? $\endgroup$
    – Boklucius
    Nov 30, 2014 at 22:24
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 1, 2014 at 10:21
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 3, 2014 at 14:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .