Day 28: CM, Page 15

Day 28: The authors continue to generalize the Josephus problem. We noticed a few days ago that the Josephus problem can be represented as cyclic left bit shift. Can we generalize that observation to our more general equations with alpha, beta, and gamma? Yes, we can...

First, rewrite our recurrences as:
f(1) = alpha
f(2n + j) = 2f(n) + betaSubJ for j=0,1 and n>=1

For j=0, betaSubJ = beta and for j=1, betaSubJ = gamma. Then by the equations above:

Sure enough, if we consider the original problem with alpha=1, beta=-1, gamma=1, we have something like:

100 = (1100100)
f(1100100) = alpha gamma beta beta gamma beta beta
f(1100100) = (1 1 -1 -1 1 -1 -1) = 64 + 32 - 16 - 8 + 4 - 2 - 1 = 73

We've had to "relax" the binary representation to allow betas and gammas that are not equal to 0 or 1. But this is still and interesting result.

One more page of the Josephus problem tomorrow and then it's on to the exercises.