# 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.

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*}

• Thanks! I'll fix my copy error soon Commented Aug 3, 2020 at 7:47
• @FredClausen: You’re welcome! Commented Aug 3, 2020 at 7:47