Up: Recursion. Prev: How long it takes. Next: Exponentiation.

Let's figure out values of `M` for the first few numbers.

M(1) | =1 |

M(2)=2M(1) + 1 | =3 |

M(3)=2M(2) + 1 | =7 |

M(4)=2M(3) + 1 | =15 |

M(5)=2M(4) + 1 | =31 |

So the monks will move 2^{64}+1 (about
18.45x10^{18}) disks. If they are really good and can move one
disk a millisecond, then they'll have to work for 584.6 million
years. It looks like we're safe.

Now we'll look at a very different, very practical problem: Exponentiation.

Next: Exponentiation.