Day 29: CM, Page 15

Day 29: I've skipped a couple of days. This is the last page of chapter one - one more page of the Josephus problem. The authors do one final generalization of the Josephus problem. Suppose we take our previous recurrence:

f(1) = alpha
f(2n+j) = 2f(n) + BetaSubJ

And generalize it to:

f(j) = alphaSubJ where 1 <= j <= d
f(dn+j) = cf(n) + betaSubJ where 1 < = j <= d and n >= 1

Given any recurrence that fits this pattern, we can solve it by converting from a number in base d to a number in base c (as we did yesterday for the base 2 to base 2 conversion). For example, suppose we have the recurrence:

f(1) = 1
f(2) = 2
f(3n) = 10f(n) + 1
f(3n+1) = 10f(n) - 2
f(3n+2) = 10f(n) + 3

To calculate f(10):
10 = 101 base 3
f(10) = f((101)b3) = (1 1 -2)b10 = 100 + 10 - 2 = 108

Pretty neat. That's it for chapter 1.