Algorithm - Search for input for which the function returns a specific value

Question

I have the following function:

F(0) = 0 F(1) = 1 F(2) = 2 F(2*n) = F(n) + F(n+1) + n , n > 1 F(2*n+1) = F(n-1) + F(n) + 1, n >= 1 

I am assigned the number n < 10^25 , and I must show that there is a value a , such as F(a)=n . Due to how the function is defined, a n may exist, for example F(a)=F(b)=n where a < b , and in this situation I have to return b , not a

What I still have:

• We can split this function into two strict monotone series: one for F (2 * n) and one for F (2 * n + 1) and can find the indicated value in logarithmic time, therefore, the finding was more or less done.
• I also found that F(2*n) >= F(2*n+1) for any n , so I search for it in F (2 * n) first, and if I don't find it, I search in F ( 2 * n + 1)
• The problem is calculating the value of the function. Even with some crazy memoization to 10 ^ 7, and then back to recursion, he still could not calculate values ​​above 10 ^ 12 in a reasonable amount of time.

I think that I have an algorithm in order to actually find what I need, everything turned out, but I can not calculate F (n) fast enough.

Answer 1

Just use memoisation up to the target value, for example. in Python:

 class Memoize: def __init__(self, fn): self.fn = fn self.memo = {} def __call__(self, *args): if not self.memo.has_key(args): self.memo[args] = self.fn(*args) return self.memo[args] @Memoize def R(n): if n<=1: return 1 if n==2: return 2 n,rem = divmod(n,2) if rem: return R(n)+R(n-1)+1 return R(n)+R(n+1)+n 

This instantly calculates the response to 10 ** 25.

The reason for this is that the nature of the recursion means that for the binary number abcdef, it will have to use no more values:

 abcdef abcde-1,abcde,abcde+1 abcd-2,abcd-1,abcd,abcd+1,abcd+2 abc-2,abc-1,abc,abc+1,abc+2 ab-2,ab-1,ab,ab+1,ab+2 a-2,a-1,a,a+1,a+2 

At each step, you can move up or down by 1, but you also divide the number by 2, so most of them can move away from the original number.

Therefore, memoised code will use no more than 5 * log_2 (n) ratings.