Rabbits and Recurrence Relations

This problem asks:

Given: Positive integers n≤40 and k≤5.

Return: The total number of rabbit pairs that will be present after n months, if we begin with 1 pair and in each generation, every pair of reproduction-age rabbits produces a litter of k rabbit pairs (instead of only 1 pair)

Restate the problem

I’m going to get two numbers that define a system of reproducing rabbits. The first number is how many generations of rabbits I need to keep track of. The second number is the size of each litter of rabbits.

The problem text includes the hint that if I track a population of rabbits for 5 generations with a litter size of 3, I should expect a final population of 19 pairs of rabbits.

First, getting values from a file

My first challenge was to read the two numbers from the downloaded file and assign them to variables.

That didn’t seem like it should be too hard, but I couldn’t get it to work, so I looked online and found help here.

The article didn’t solve my exact case, but it was close enough that I was able to figure out this method:

file = open(file_path, "r").readline().split(' ')
n = int(file[0])
k = int(file[1])

Writing a Fibonacci function with variable offspring

First, I wrote a function to calculate the number of rabbits in a system when there are two offspring rabbits per generation. That was the Nth generation of the Fibonacci sequence for N generations. The Fibonacci sequence is a fascinating recurrence relation that appears throughout nature.

I struggled to modify the Fibonacci function so that it took n of 5 and k of 3 and returned 19, so I went looking for help.

I found this fancy article on ways to calculate the Fibonacci sequence in Python, but all the examples there assumed a litter size of 2. I tried to work the litter size into my function, but couldn’t get 5 and 3 to return 19.

Then I found this amazing pythontutor visualization tool which shows you exactly what all the frames and objects are at every step of execution of your code. With that, I was able to figure out that the key to calculating populations of rabbits after n generations with litter sizes of k is this:

def fib(n, k):
    prev1, prev2 = 1, 1
    for i in range(2, n):
        current = prev1 + k * prev2
        prev2 = prev1
        prev1 = current
    return current

You can see my full code set for this challenge here.

Conclusion

The problem parameters that I downloaded from Project Rosalind were: 33 4. So my code needed to figure out how many pairs of rabbits there would be after 33 generations of rabbits producing 4 rabbits per litter.

Not surprising to me, the result was a very large number of rabbits.

7,334,743,797,805 pairs of rabbits. That’s over 14 trillion rabbits. Trillion with a “T”. Of course, that’s assuming that none of these rabbits never die, and they never get too old to have more rabbits.