Piecewise function outputs the sum of the digits in base 3 representation

Question

Recently, I encontered a rather interesting function in the solution booklet to a math contest. It is a piecewise function that outputs the sum of the digits of the input in base $3$. Could anyone explain the intuition and why this function produces that result.

The function: $$ g(n) = \begin{cases} g\bigl(\frac{n}{3}\bigr) & \text{if } 3 \mid n, \\[2pt] g(n-1)+1 & \text{otherwise}. \end{cases} $$

Answer 1

Note: You need a base to your recursion: $g(0) = 0$.

In ternary (base $3$), the digits are $\{0, 1, 2\}$ and the place values are powers of $3$. That is, if we write $n = (d_k \dots d_2 d_1 d_0)_3$ in ternary, then $$ n = d_k 3^k + \cdots + d_2 3^2 + d_1 3 + d_0 $$

Claim 1. If a number is divisible by $3$, then its ternary representation will end in $0$, so the sum of digits is unchanged after dividing by $3$. Why? (Try to work it out yourself before revealing the spoiler.)

It's clear that $d_0$ is the remainder when $n$ is divided by $3$, so if $n$ is a multiple of $3$, then $d_0 = 0$. In this case, $$\frac{n}{3} = d_k 3^{k-1} + \cdots + d_2 3 + d_1,$$ which looks like $(d_k \dots d_2 d_1)_3$ in ternary (same string with final digit $d_0$ truncated). Now, \begin{align} g\bigl(\tfrac{n}{3}\bigr) &= d_k + \cdots + d_2 + d_1 \\ &= d_k + \cdots + d_2 + d_1 + 0 = g(n).\end{align}

Claim 2. If a number is not divisible by $3$, then its ternary representation will not end in $0$, so only the final digit will change (by decreasing by $1$) after subtracting $1$, hence the same is true of the sum of digits. Why?

In this case, $d_0 \in \{1, 2\}$, so $$n-1 = d_k 3^{k} + \cdots + d_2 3^2 + d_1 3 + (d_0-1),$$ where $d_0 - 1 \in \{0, 1\}$. Now, \begin{align} g(n-1) &= d_k + \cdots + d_2 + d_1 + (d_0 - 1) \\ &= (d_k + \cdots + d_2 + d_1 + d_0) - 1 = g(n) - 1,\end{align} which gives the formula in the other case.

Claim 3. By a sequence of moves of either subtracting $1$ if a number is not divisible by $3$ or by dividing by $3$ if a number is divisible by $3$, any natural number will terminate in $0$, whose sum of digits is clearly $0$. So this recursive definition will eventually terminate.

This is pretty clear and probably best illustrated by an example. Let's consider $n=35$, and indicate subtracting $1$ in blue and dividing by $3$ in red: $$ 35 \color{blue}{\to} 34 \color{blue}{\to} 33 \color{red}{\to} 11 \color{blue}{\to} 10 \color{blue}{\to} 9 \color{red}{\to} 3 \color{red}{\to} 1 \color{blue}{\to} 0. $$ In ternary, this sequence looks like: $$ 1022 \color{blue}{\to} 1021 \color{blue}{\to} 1020 \color{red}{\to} 102 \color{blue}{\to} 101 \color{blue}{\to} 100 \color{red}{\to} 10 \color{red}{\to} 1 \color{blue}{\to} 0. $$ If we count up the blue arrows, we get $5$, which is the ternary sum of digits.