Concrete Mathematics: Chapter 1: Generalised Josephus Recurrence: Understanding Radix 3 to 10 digit-by-digit replacement

Question

Summary

When converting $(201)_3$, specifically, converting the $2$, I am not entirely sure how they select $5$ (from $f(2) = 5$) and not $8$ (from $f(3n+2) = 10f(n)+8$) when doing the radix replacement operation for the recurrence following equation 1.18. My thinking is that it is due to the start of the replacement being done with $\alpha_j$ which, in this case, is $5$. See below for more context.

Details

The following radix independent, generalised recurrence is given as follows (1.17 in book)

$$ \begin{align} f(j) &= \alpha_j,\ \ \text{for}\ 1 \leq j < d; \\ f(dn + j) &= cf(n) + \beta_j,\ \ \text{for}\ 0 \leq j < d\ \text{and}\ \ n \geq 1, \end{align} $$

The above recurrence can then start with numbers in radix $d$ and produce values in radix $c$. So it has the radix changing solution (1.18 in book)

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

Then, as the book says, by some stroke of luck we're given the recurrence

$$ \begin{align} f(1) &= 34, \\ f(2) &= 5, \\ f(3n) &= 10f(n) + 76,\ \ \text{for}\ \ n \ge 1, \\ f(3n+1) &= 10f(n) - 2,\ \ \text{for}\ \ n \ge 1, \\ f(3n+2) &= 10f(n) + 8,\ \ \text{for}\ \ n \ge 1, \\ \end{align} $$

Then the book proposes computing $f(19)$ where $d = 3$ and $c = 10$ (from 1.17). So $19 = (201)_3$ and the radix-changing solution has us doing a digit-by-digit replacement of 201 so

• $2_3$ becomes $5_{10}$ - this is the bit I'm unsure about. Why is it not $8$? I think because it is the first digit to replace and thus applies to $\alpha_j$. If it where in the middle of the number (e.g. $120$) it may well have been $8$?
• $0_3$ becomes $76$
• $1_3$ becomes $-2$

So tying it all together as radix $10$ we get

$$ f(19) = ((201)_3) = (5 76 -2)_{10} = 500 + 760 -2 = 1258 $$

Being verbose: the final addition is because $500$ is in the radix $10$ "hundreds" column (multiply by $100$), $76$ in the "tens" column (multiply by $10$), and $-2$ in the "ones" column.

Answer 1

Your suspicion is correct: the function $f$ takes $$(b_mb_{m-1}\ldots b_1b_0)_d$$ to $$(\alpha_{b_m}\beta_{b_{m-1}}\beta_{b_{m-2}}\ldots\beta_{b_1}\beta_{b_0})_c\,.$$ (Note that you didn’t copy (1.18) quite correctly.) This is a digit-by-digit replacement: $b_m$ is replaced by $\alpha_{b_m}$, and $b_k$ is replaced by $\beta_{b_k}$ for $0\le k\le m-1$. In the example you have $c=10$, $d=3$, and the values

$$\left\{\begin{align*} \alpha_1&=34\\ \alpha_2&=5\\ \beta_0&=76\\ \beta_1&=-2\\ \beta_2&=8\,. \end{align*}\right.$$

If your input is $19=(201)_3$, then $m=2$, $b_2=2$, $b_1=0$, and $b_0=1$, so your output from $f$ is

$$\begin{align*} (\alpha_2\beta_0\beta_1)_{10}&=(5\;76\;-2)_{10}\\ &=5\cdot 10^2+76\cdot 10^1-2\cdot 10^0\\ &=500+760-2\\ &=1258\,. \end{align*}$$

Had the input been $46=(1201)_3$, the output would have been

$$\begin{align*} (\alpha_1\beta_2\beta_0\beta_1)_{10}&=(34\;8\;76\;-2)_{10}\\ &=34\cdot 10^3+8\cdot 10^2+76\cdot 10^1-2\cdot 10^0\\ &=34000+800+760-2\\ &=35558\,. \end{align*}$$