Tetranacci!

Computer Science Level 2

Tetranacci numbers are defined by the following recurrence relation:

$T_0 = 0$
$T_1 = 1$
$T_2 = 1$
$T_3 = 2$
$T_n = T_{n-1} + T_{n-2} + T_{n-3} + T_{n-4}$ for $n > 3$

Lisa decides to write a quick python script to calculate the $n$ th Tetranacci number:

def tetra(n):
        if n < 0:
                raise ValueError("invalid index!")
        if n==0:
                return 0
        if n==1:
                return 1
        if n==2:
                return 1
        if n==3:
                return 2
        return tetra(n-1) + tetra(n-2) + tetra(n-3) + tetra(n-4)

If she calls tetra(5), then the tetra() procedure will be called $9$ times all together (if you include the initial invocation):

tetra(5)
    -> tetra(4)
        -> tetra(3)
        -> tetra(2)
        -> tetra(1)
        -> tetra(0)
    -> tetra(3)
    -> tetra(2)
    -> tetra(1)

How many times will it be called for tetra(10)?

The answer is 241.

1 solution

Geoff Pilling
Apr 1, 2017

For the first few numbers it is easy to see that the number of times the procedure is invoked is as follows;

n	Number of calls
0	1
1	1
2	1
3	1
4	5
5	9

And, in fact, we know that, in general tetra(n) will call tetra(n-1), tetra(n-2), tetra(n-3), and tetra(n-4). So, the total number of calls it will make will be the sum of the four previous numbers of calls plus $1$ (the call itself).

Or in general, the number of calls, N, will be given by:

$N_n = 1$ for $n \leq 3$
$N_n = N_{n-1} + N_{n-2} + N_{n-3} + N_{n-4} + 1$ for $n \geq 4$

Equations quite similar to the Tetranacci numbers themselves!

Using this recursion relation, we find that $N_{10} = \boxed{241}$ .

On my first attempt I went along and found the sequence $5,9,17,33,65$ and guessed that the general pattern was $N_{n} = 2^{n-2} + 1$ , so $N_{10} = 257$ , which is wrong. I then went back and did the actual calculations and found instead that $N_{9} = 125$ and $N_{10} = 241$ . Curious that it followed such a nice pattern from $n = 4$ to $n = 8$ and only then started to deviate.

Brian Charlesworth - 4 years, 2 months ago

Whoa... Interesting that it followed such a common pattern so closely. I suspect that it has to do with the fact that these are Tetranacci numbers. If they were Petranacci or Hexanacci numbers, I suspect they may follow the $2^{n} + 1$ pattern for a bit longer....

Geoff Pilling - 4 years, 2 months ago

Yes, I have the same suspicion....

Brian Charlesworth - 4 years, 2 months ago

Tetranacci!

The answer is 241.

1 solution

0 pending reports