4

I am stuck with the following recurrence relations (actually asked in a programming question).Given the following relationships, is it possible to find the index of the occurrence of any given number which is in the series?

$f(0) = 1$
$f(1) = 1$
$f(2) = 2$
$f(2n) = f(n) + f(n + 1) + n$ (for $n > 1$)
$f(2n + 1) = f(n - 1) + f(n) + 1$ (for $n >= 1$)

So the series is like:(Index: 0,1,2,3...n)
$1,1,2,3,7,4,13,6,15,11,22,12,25,18,28,20,34...$

Example:
Given: $f(n) = 8074$
Result: $n = 2441$

Also, some other condition given are: A number may occur more than once - the resultant index should be the last time it occurs.
An example:
$f(14812) = 65389$ Also,
$f(16623) = 65389$
So, the result is $n = 16623$

By programming in python, I was able to observe that any number that repeats occurs utmost twice.
Also, since the input can be pretty large - simple recursion (with hashing) takes too long and mostly causes memory errors.
So, I tried to reduce the first recurrence formula by substituting the second in it, but still I was not able to find any proper relation between $f(n)$ and $f(2n)$ or $f(n-1)$ since only $f(n)$ is given as input.
Is it possible to solve this using any other relations?
(Edit: I've also posted on StackOverflow here)

Community
  • 1
user3581882
  • 41
  • Your examples make it seem that constant coefficient recurrence relations might be a narrowed case of interest here. For these the solutions are related to explicit solutions fairly easily, but the analysis for variable coefficient relations seems difficult. – hardmath Dec 17 '14 at 16:57
  • Reading over the Question again I get the feeling you may be interested only in this specific recurrence relation (by cases), so perhaps my first Comment is moot. – hardmath Dec 17 '14 at 17:01
  • Some recurrences such as the fibonacci series, do not have simple formulas. It looks like that kind of relation. – ghosts_in_the_code Dec 17 '14 at 19:42
  • @user45195 Yes, it is similar to fibonacci sequence, but is there any procedure or method to derive a formula for such recurrences? – user3581882 Dec 18 '14 at 11:27
  • @hardmath Yes, I am interested in this specific recurrence relations - not recurrence relations like the one given if that is what you meant. – user3581882 Dec 18 '14 at 11:29
  • What I am basically saying is, as far as I know, it can't be condensed into a single non-recurring equation. – ghosts_in_the_code Dec 18 '14 at 15:39
  • http://www.wikihow.com/Solve-Recurrence-Relations gives the most common methods used. – ghosts_in_the_code Dec 18 '14 at 15:42
  • I used python to solve this, see the answer I provided in the question on stackoverflow. But it seems like I never get numbers that appear twice. My logic was that the even and odd functionas are ever-increasing. Is that correct? Did I mess something else up? Thanks, math people. Question on SO: http://stackoverflow.com/questions/27546822/2-recurrence-equations-finding-index/27550269#27550269 – Reut Sharabani Dec 18 '14 at 16:15

0 Answers0