9

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.

user26486
  • 11,331
Boklucius
  • 193

1 Answers1

10

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.

Community
  • 1
Jeffrey Shallit
  • 1,518
  • 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. – Boklucius Nov 30 '14 at 21:24
  • 2
    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. – Jeffrey Shallit Nov 30 '14 at 21:47
  • the maximal S is $10^{25}$, doesn't that leave a pretty wide range? – Boklucius Nov 30 '14 at 22:24
  • You asked for an algorithm; you didn't specify that it had to run in a certain time. – Jeffrey Shallit Nov 30 '14 at 23:10
  • My bad, should've said earlier that there were constraints. There should be a solution that runs in $log (n)$, that's why I thought solving it will help me with finding it. I suppose it's some base transformation or something like that. Thanks for the help. – Boklucius Dec 01 '14 at 08:29
  • 1
    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. – Jeffrey Shallit Dec 01 '14 at 10:21
  • Thanks a lot again, I feel so stupid now for not seeing it. – Boklucius Dec 01 '14 at 13:28
  • Since your comments provided an answer to the question, would you like to include them into the answer itself? Related discussion. –  Dec 02 '14 at 18:25
  • @JeffreyShallit How do you compute the values of $f()$ for your binary search in constant time? – Steven Stadnicki Dec 02 '14 at 20:16
  • 2
    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. – Jeffrey Shallit Dec 03 '14 at 14:52
  • @JeffreyShallit What do you mean by "solving through binary search"? Does that mean doubling $n$ until I find the finite range where $S$ can be found? – Sven Dec 06 '14 at 11:46
  • You can look up the term "binary search" in any introductory book on algorithms and data structures or on wikipedia. – Jeffrey Shallit Dec 06 '14 at 15:06
  • Any clue how to find $M_0, M_1,..., M_k$ matrices? – knok16 Sep 25 '15 at 00:41
  • By the way is there a simple way to estimate $n$ for a given $S$ and $0.5n\log(n)=S$, rather than a binary search? – xslittlegrass Dec 02 '16 at 04:32