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.

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.

Day 27: CM, Page 14

Day 27: The authors introduce the repertoire method by an example with the Josephus problem. Recall from yesterday that we believe:

A(n) = 2^m
B(n) = 2^m - 1 - l
C(n) = l

How can we prove this? One way is to find a series of equalities based on specific data points, then to solve those equalities. No hints yet on how to find the specific data points to form the equalities. The authors make a few clever observations to find their data points. We'll assume that f(n) = A(n)(alpha) + B(n)(beta) + C(n)(gamma).

What happens in the case where alpha=1, beta=0, gamma=0? We have f(n) = A(n) or:

A(1) = 1
A(2n) = 2A(n)
A(2n+1) = 2A(n)

We want to show that A(n) = 2^m. This follows from the equations above by induction. A(1) = 1 since A(1) = alpha. Assume A(n/2) = 2^(m-1). Then:

A(n) = A(2^m + l) = 2A((2^m + l)/2) = 2(2^(m-1)) = 2^m.

Next we want some other interesting data points. What are some other values for alpha, beta, and gamma that make it easy to solve our recurrences? How about f(n) = 1:

1 = alpha
1 = 2*1 + beta
1 = 2*1 + gamma

For this to be true, alpha=1, beta=-1, and gamma=-1. Plugging that back in, we get:

A(n) - B(n) - C(n) = f(n) = 1

What happens if f(n) = n? In that case:

1 = alpha
2n = 2n + beta
2n+1 = 2n + gamma

So in this case, alpha=1, beta=0, and gamma=1. Plugging that back in, we get:

A(n) + C(n) = n

Now that we have three inequalities, we can solve them. From our first observation, we directly have A(n) = 2^m

That gives us:
A(n) + C(n) = n
C(n) = n - A(n) = 2^m - l - 2^m = l

Which matches what we expect. And finally:

A(n) - B(n) - C(n) = 1
B(n) = A(n) - C(n) - 1
B(n) = 2^m - l - 1

And that matches all our observations for A(n), B(n), and C(n) of:

A(n) = 2^m
B(n) = 2^m - l - 1
C(n) = l

This is an illustration of the repertoire method. There are still some questions to work out - how do we choose the right specific data points to use for our equalities? I suspect we'll return to this in the exercises. More on the Josephus problem tomorrow.

Day 26: CM, Page 13

Day 26: The Josephus problem continued. The authors generalize the Josephus problem even further. They ask the question: how would we find a closed form for the recurrence if the pattern had been more complex? What if the coefficients on the recurrence were something besides -1 and +1? To generalize the recurrence:


By expanding the recurrence, we can build a table of values for f(n):


If we write f(n) as:
Then, it appears that:
More on these equations tomorrow.

Day 25: CM, Page 12

Day 25: I've missed a couple of days. I'm now on pace for Nov 5, 2016.

The authors continue to examine the binary representation of the Josephus function. They observe that since the solution to the Josephus problem is a cyclic left bit shift, you might expect that m iterations of the function would return to the original number. However, this is not true because zeros are removed from the number during the shifting process. For example:

J(1101) = 1011
J(1011) = 0111 = 111
J(111) = 111

For a given number, you can find the convergent number by counting the number of 1's in the original number's binary representation. The point of convergence can be defined as 2^v(n) - 1 where v(n) is the numbers of 1's in n.

More on the Josephus problem tomorrow. The authors continue to generalize it even further.

Day 24: CM, Page 11

Day 24: The authors prove the closed form of the Josephus problem by induction. They prove the odd and even cases separately.

Base case: J(1) = J(2^0 + 0) = 2(0) + 1 = 1
Assume: J(2n) = 2(J(n)) - 1 and J(2n + 1) = 2(J(n)) + 1
Inductive Hypothesis Even: J(n/2) = J(2^(m-1) + l/2) = 2l/2 + 1
Inductive Hypothesis Odd: J((n-1)/2) = J(2^(m-1) + (l-1)/2) = 2(l-1)/2 + 1

This a different twist on the normal induction process. Rather than assuming n-1 is true, we are assuming n/2 is true for all even numbers. Then:

And a similar proof for odd numbers:


Together, the two proofs cover all even and odd numbers. Next the authors suggest trying to generalize the problem. There seems to be a relationship in the problem between powers of 2, so let's represent the problem in binary.


That last step follows because J(n) = 2l + 1 and b sub m = 1. This is a pretty interesting result. J(n) can be calculated by doing a one bit cyclic left shift on n. More details from the CM authors tomorrow about this new observation tomorrow.

Day 23: CM, Page 10

Day 23: The Josephus problem continued. Yesterday we found a recursive solution for the Josephus problem with an even number of people. With an odd number of people, the recursive solution is similar.

Consider J(2n + 1). If you start with 1 2 3 4 5 6 7 8 9, after the first round of elimination you have 1 3 5 7 9. But wait! This isn't right. To continue the elimination process, we would need to eliminate 1 next, so new sequence isn't quite correct - it's off by one if we want to skip the first member of the sequence on the second iteration. To keep the iteration consistent (always skipping the first element in a sequence), we need to eliminate one more element. So 1 2 3 4 5 6 7 8 9 is actually the same as 3 5 7 9 where 1 is included in the first round of elimination. Now on the second round of iteration we start with 5 as expected. 3 5 7 9 is the same problem as 1 2 3 4 except that each number is doubled and incremented by 1. So J(2n + 1) = 2(J(n)) + 1.

So we have:
J(1) = 1
J(2n) = 2(J(n)) - 1
J(2n + 1) = 2(J(n)) + 1

And with that we have a recursive formula to describe a solution to the problem. The authors use the recursive formula to describe the pattern we saw a couple of days ago, but they find a better notation to represent the closed form.

J(n) = J(2^m + l) = 2l + 1

Where 2^m <= n < 2^(m+1) and l is the remainder (or leftover) of n/2^m. Also note: l < 2^m

With this we have a closed form representation of the Josephus problem. Tomorrow we'll need to prove it, and authors have some additional interesting observations about the problem.