Solving recursive sequence

Question

Lately I've been solving some challenges from Google Foobar for fun, and now I've been stuck in one of them for more than 4 days. It is about a recursive function defined as follows:

R(0) = 1
R(1) = 1
R(2) = 2
R(2n) = R(n) + R(n + 1) + n (for n > 1)
R(2n + 1) = R(n - 1) + R(n) + 1 (for n >= 1)

The challenge is writing a function answer(str_S) where str_S is a base-10 string representation of an integer S, which returns the largest n such that R(n) = S. If there is no such n, return "None". Also, S will be a positive integer no greater than 10^25.

I have investigated a lot about recursive functions and about solving recurrence relations, but with no luck. I outputted the first 500 numbers and I found no relation with each one whatsoever. I used the following code, which uses recursion, so it gets really slow when numbers start getting big.

def getNumberOfZombits(time):
    if time == 0 or time == 1:
        return 1

    elif time == 2:
        return 2

    else:
        if time % 2 == 0:
            newTime = time/2
            return getNumberOfZombits(newTime) + getNumberOfZombits(newTime+1) + newTime

        else:
            newTime = time/2 # integer, so rounds down
            return getNumberOfZombits(newTime-1) + getNumberOfZombits(newTime) + 1

The challenge also included some test cases so, here they are:

Test cases
==========

Inputs:
    (string) str_S = "7"
Output:
    (string) "4"

Inputs:
    (string) str_S = "100"
Output:
    (string) "None"

I don't know if I need to solve the recurrence relation to anything simpler, but as there is one for even and one for odd numbers, I find it really hard to do (I haven't learned about it in school yet, so everything I know about this subject is from internet articles).

So, any help at all guiding me to finish this challenge will be welcome :)

Answer 1

The key to solving this puzzle was using a binary search.

As you can see from the sequence generators, they rely on a roughly n/2 recursion, so calculating R(N) takes about 2*log2(N) recursive calls; and of course you need to do it for both the odd and the even.

Thats not too bad, but you need to figure out where to search for the N which will give you the input. To do this, I first implemented a search for upper and lower bounds for N. I walked up N by powers of 2, until I had N and 2N that formed the lower and upper bounds respectively for each sequence (odd and even).

With these bounds, I could then do a binary search between them to quickly find the value of N, or its non-existence.

Answer 2

Instead of trying to simplify this function mathematically, I simplified the algorithm in Python. As suggested by @LambdaFairy, I implemented memoization in the getNumberOfZombits(time) function. This optimization sped up the function a lot.

Then, I passed to the next step, of trying to see what was the input to that number of rabbits. I had analyzed the function before, by watching its plot, and I knew the even numbers got higher outputs first and only after some time the odd numbers got to the same level. As we want the highest input for that output, I first needed to search in the even numbers and then in the odd numbers.

As you can see, the odd numbers take always more time than the even to reach the same output.

The problem is that we could not search for the numbers increasing 1 each time (it was too slow). What I did to solve that was to implement a binary search-like algorithm. First, I would search the even numbers (with the binary search like algorithm) until I found one answer or I had no more numbers to search. Then, I did the same to the odd numbers (again, with the binary search like algorithm) and if an answer was found, I replaced whatever I had before with it (as it was necessarily bigger than the previous answer).

I have the source code I used to solve this, so if anyone needs it I don't mind sharing it :)