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)