Concrete Mathematics: Chapter 1: Generalised Josephus Recurrence: Understanding Radix 3 to 10 digit-by-digit replacement 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.
 A: 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*}$$
