Dying Rabbits

Mon Jun 17, 2013

I checked back in to Project Rosalind a few days ago, and I noticed that they had added several new problems. One was the familiar Fibonacci sequence, beloved of introdutory computer science instruction everywhere. There was also a modified version of the Fibonacci problem, however, which requires you to compute the sequence with mortal rabbits. (The normal Fibonacci sequence is often introduced as an unrealistic problem in modeling the population growth of immortal rabbits.)

I wanted to find a solution to this that didn’t involve manually keeping track of how many rabbits were breeding and dying, and it turned out to be more complicated than I originally thought. Brother U. Alfred tackled it in an early issue of The Fibonacci Quarterly “Dying Rabbit Problem Revived”, only to be rebuked somewhat harshly by John H. E. Cohn in a subsequent issue. V. E. Hoggatt, Jr. and D. A. Lind devised a simple-seeming solution a few years later that I found quite difficult to compute. Luckily enough, this paper by Antonio M. Oller included some Maple code that I was able to translate into perl:

Maple Translation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$h=2;
$n=193; #(Subtract one from offered values, indexing)
$k=17; # As above
use bignum;
for $i (0..($h-1)) {
  $c[$i]=1;

}

for $i ($h..($k+$h+2)) {
  $c[$i]=$c[$i-1]+$c[$i-$h];
}

for $i ((($k+$h)-1)..$n) {
  $counter=0;
  for $j (($i-$k-$h+1)..($i-$h)) {
    $counter=$counter+$c[$j];
  }
  $c[$i]=$counter;
}

print $c[$n];

There is a very short python solution and Common Lisp solution posted on the solutions page (which you can only see after you have solved the problem) that I don’t understand at all, so there are clearly many other ways.