# Concrete Mathematics: Where is the cyclic shift for rewritten generalised Josephus function (1.15 and 1.16)?

### Summary

In equation labelled 1.16 how is the cyclic left shift happening? I.e. should the $$\alpha$$ not be at the end as in $$(\beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0} \alpha)_2$$ instead of $$(\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0})_2$$?

It seems to me that the derivation they go through (summarised below) is just giving $$f((n)_2) = (n)_2$$ or $$f((n)_2) = (n)_{10}$$ (as in the unfolding process)

### Details

The original J-recurrence has, as the book describes, a magical solution via a single cyclic left shift

$$J((b_m b_{m-1} ... b_1 b_0)_2) = (b_{m-1} ... b_1 b_0 b_m)_2\ \ \ \ \text{where}\ \ b_m = 1$$

A reminder of our original generalised recurrence (1.11 in book)

\begin{align} f(1) &= \alpha \\ f(2n) &= 2f(n) + \beta \\ f(2n + 1) &= 2f(n) + \gamma \\\ \end{align}

And then this rewritten as shown in 1.15

\begin{align} f(1) &= \alpha \\ f(2n+j) &= 2f(n) + b_j \text{,}\ \ \ \ \ \text{for}j=0,1\ \ \ \text{and}\ \ n\geq1 \end{align}

Then, the recurrence is unfolded as follows

\begin{align} f((b_m b_{m-1} ... b_1 b_0)_2) &= 2f((b_m b_{m-1} ... b_1)_2) + \beta_{b_0} \\ &= 4f((b_m b_{m-1} ... b_2)_2) + 2\beta_{b_1} + \beta_{b_0} \\ .\\ .\\ .\\ &=2^mf((b_m)_2) + 2^{m-1}\beta_{b_{m-1}}+ ... +2\beta_{b_1} + \beta_{b_0} \\ &=2^m\alpha + 2^{m-1}\beta_{b_{m-1}} ... +2\beta_{b_1} + \beta_{b_0} \end{align}

Finally the book concludes

The derivation above tells us

$$f((b_m b_{m-1} ... b_1 b_0)_2) = \alpha \beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0})_2$$

I don't quite see how this results in the function being applied with the shifted result?

I think I've figured it out. The key phrase comes after equation 1.15

if we let $$\beta_0 = \beta$$ and $$\beta_1 = \gamma$$.

To expand on that

\begin{align} \beta_0 &= 0_2 = \beta = -1 \\ \beta_1 &= 1_2 = \gamma = 1 \\ \end{align}

To put it in a couple of sentences: whenever we encounter a binary 0 it means we have $$\beta_0$$ which, in our original recurrence (and I think it still applies here), is $$\beta$$ and has a value of $$-1$$. Likewise for $$\beta_1$$ the value from our original recurrence is $$1$$.

So unrolling the recurrence from my question with a concrete number will look like

\begin{align} f((101)_2) &= 2^2(1) + 2^1(-1) + 2^0(1) \\ &= 4 -2 + 1 \\ &= 3 \\ \end{align}

Which matches the closed form answer

\begin{align} J(2^m + \ell) &= 2\ell + 1; \\ J(2^2 + 1) &= 2(1) + 1 \\ &= 3 \\ \end{align}

The book then identifies a compact solution

The derivation above tells us that

$$f((b_m b_{m-1} ... b_1 b_0)_2) = \alpha \beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0})_2$$

So, again using the example of $$5$$ ($$101$$ in binary), we can simply apply the above rules (as $$f(n)$$) to each binary digit (symbolic placeholders inserted for reference)

$$\begin{array}{l} n &= (1~~~~~~0~~~~1)_2 &= 5 \\ &\phantom{=} ~~\gamma~~~~~~\beta~~~~~\gamma \\ \hline f(n) &= (1~~~{-}1~~~~~1)_2 \\ f(n) &= {+}4~~{-}2~~{+}1 &= 3) \\ \end{array}$$