algorithm - Searching for an input for which a 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 given a number n < 10^25 and I have to show that exists a value a such as F(a)=n. Because of how the function is defined, there might exist a n such as F(a)=F(b)=n where a < b and in this situation I must return b and not a

What I have so far is:

• 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 specified value in logarithmic time, so the finding is more or less done.
• I've also found that F(2*n) >= F(2*n+1) for any n, so I first search for it in F(2*n) and if I don't find it there, I search in F(2*n+1)
• The problem is calculating the function value. Even with some crazy memoization up to 10^7 and then falling back to recursion, it still couldn't calculate values above 10^12 in a reasonable time.

I think I have the algorithm for actually finding what I need all figured out, but I can't calculate F(n) fast enough.

Answer 1

Simply use memoisation all the way up to the target value, e.g. 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 computes the answer for 10**25 instantly.

The reason this works is because the nature of the recursion means that for a binary number abcdef it will only need to at most use the 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 1, but you also divide the number by 2 so the most you can move away from the original number is limited.

Therefore the memoised code will only use at most 5*log_2(n) evaluations.