Get number of Nth place of modified Fibonacci sequence

Question

In an interview today, I was given this sequence, which is sort of a modified Fibonacci:

1, 1, 2, 4, 6, 13, 19, 42, 61, 135, ...,

I was asked to write a function to return the number at place n.

So, if n = 4, the function should return 4, n = 6 return 13, etc.

As I'm sure you already noticed, the difference is that even items equal the previous 4 items, while odd items equal the previous 2.

It isn't a problem if you use recursion. That's what I did, but it's not the approach I would have liked.

The Fibonacci calculation goes something like this (in PHP):

$n = 17;
$phi = (1 + sqrt(5)) / 2;
$u = (pow($phi, $n) - pow(1 - $phi, $n)) / sqrt(5);

$u being, in this case, 1597.

However, I have no idea how to solve it with a modified version of a Fibonacci sequence like this one.

Answer 1

If I understand you correctly, you want to compute efficiently [i.e. in O( log(n) )] sequence defined as:

a[2n + 5] = a[2n + 4] + a[2n + 3] + a[2n + 2] + a[2n + 1]
a[2n + 2] = a[2n + 1] + a[2n]

Let's define two new sequences. First one will correspond to the values of a on even positions, the second one to the values on even positions:

b[n] = a[2n]
c[n] = a[2n + 1]

Now we have:

c[n] = b[n] + c[n - 1] + b[n - 1] + c[n - 2]
b[n] = c[n - 1] + b[n - 1]

Subtracting the second equation from the first we get (after some transformation):

b[n] = ( c[n] - c[n-1] ) /2

Next substitute this formula into first equation to get formula for c:

c[n] = 2 c[n-1] + c[n-2] 

Notice that this equation involves only elements from c. Therefore now it is possible to compute elements of c, using techniques described here. By transforming equations a little bit further you will be able to compute b efficiently as well.