closed form expression for sum of sequence of tuples that resemble a binary counter

Question

Consider a simple rule that gives a sequence of tuples. The first tuple is empty r_0 = [], and subsequent tuples are obtained by finding the right-most element that is not three(insert a zero on the left if there are no elements that are not 3), incrementing that element by 1, then changing all the following elements from 3 to 2.

This is somewhat, but not quite, like a binary counter. For example, the first 50 are

r_0 = []
r_1 = [1]
r_2 = [2]
r_3 = [3]
r_4 = [1, 2]
r_5 = [1, 3]
r_6 = [2, 2]
r_7 = [2, 3]
r_8 = [3, 2]
r_9 = [3, 3]
r_10 = [1, 2, 2]
r_11 = [1, 2, 3]
r_12 = [1, 3, 2]
r_13 = [1, 3, 3]
r_14 = [2, 2, 2]
r_15 = [2, 2, 3]
r_16 = [2, 3, 2]
r_17 = [2, 3, 3]
r_18 = [3, 2, 2]
r_19 = [3, 2, 3]
r_20 = [3, 3, 2]
r_21 = [3, 3, 3]
r_22 = [1, 2, 2, 2]
r_23 = [1, 2, 2, 3]
r_24 = [1, 2, 3, 2]
r_25 = [1, 2, 3, 3]
r_26 = [1, 3, 2, 2]
r_27 = [1, 3, 2, 3]
r_28 = [1, 3, 3, 2]
r_29 = [1, 3, 3, 3]
r_30 = [2, 2, 2, 2]
r_31 = [2, 2, 2, 3]
r_32 = [2, 2, 3, 2]
r_33 = [2, 2, 3, 3]
r_34 = [2, 3, 2, 2]
r_35 = [2, 3, 2, 3]
r_36 = [2, 3, 3, 2]
r_37 = [2, 3, 3, 3]
r_38 = [3, 2, 2, 2]
r_39 = [3, 2, 2, 3]
r_40 = [3, 2, 3, 2]
r_41 = [3, 2, 3, 3]
r_42 = [3, 3, 2, 2]
r_43 = [3, 3, 2, 3]
r_44 = [3, 3, 3, 2]
r_45 = [3, 3, 3, 3]
r_46 = [1, 2, 2, 2, 2]
r_47 = [1, 2, 2, 2, 3]
r_48 = [1, 2, 2, 3, 2]
r_49 = [1, 2, 2, 3, 3]
r_50 = [1, 2, 3, 2, 2]

Is it possible to find a closed-form expression for the $S_k$: the sum of the tuple r_k? For example, $S_6 = 2+2=4$ and $S_{10} = 1 + 2 + 2 = 5$.

This problem has arisen in some original research I am doing.

Answer 1

The left-most digit can be 1,2 or 3, while the remaining digits act exactly as a binary counter except with 2 and 3 instead of 0 and 1.

The length of the r_k tuple is given by

$$ h(k)=\left\lceil \lg\left(1+\frac{k}{3}\right)\right\rceil $$

It can be confirmed that the left-most digit is given by

$$ \left\lceil \frac{k-3(2^{h(k)}-1)}{2^{h(k)-1}}\right\rceil $$

and the remaining $h(k)-1$ digits represent the integer $k - 3[2^{h(k)}-1]$ in binary, except each digit is the bit shifted up by 2. Hence, the sum of elements of tuple $r_k$ is given by

$$ \left\lceil \frac{k-3(2^{h(k)}-1)}{2^{h(k)-1}}\right\rceil+2\left[h(k)-1\right]+\beta\left(k-3\left[2^{h(k)}-1\right]\right) $$

where $\beta(n)$ is the sum of bits of integer $n$, and requires an $\mathcal{O}(\lg n)$ algorithm to compute using divide and conquer algorithms for Hamming-weight.