# Odd digits of $2^n$

Let $u_{b}(n)$ be equal to to number of odd digits of $n$ in base $b$.

For example:
In base $10$, $u_{10}(15074) = 3$
In base $13$, $u_{13}(15610) = u_{13}([7, 1, 4, 10]_{13}) = 2$

What is the value of $$\sum_{n=1}^\infty \frac{u_b(2^n)}{2^n}$$ I don't think there's a nice closed form solution in the general case.
But when the base is even, it seems that the sum evaluates to $\frac{1}{b-1}$.

I have no idea how to approach it. I tried thinking about the generating function. But I can't find a recurrence relation or any nice properties.

• This is an incredible phenomenon – Stella Biderman Jan 30 '16 at 20:15

Here is my solution:

If $a=\sum_{j\geq 0} a_j b^j$, then $u_b(a) = \frac{1}{2}\sum_j (1-(-1)^{a_j})$ because $1-(-1)^m=\begin{cases} 0 & 2\mid m\\ 2 & 2\nmid m\end{cases}$. Note that $a_j$ is the digit directly left of the decimal point in the $b$-adic expansion of $ab^{-j}$, i.e. $a_j = \lfloor ab^{-j} \rfloor \mod b$. Now if $b$ is even we can therefore replace $(-1)^{a_j}$ by $(-1)^{\lfloor ab^{-j} \rfloor}$.

Thus: $$\sum_{n\geq 1} 2^{-n} u_b(2^n) = \sum_{n\geq 1,j\geq 0} 2^{-n} \frac{1}{2} (1-(-1)^{\lfloor 2^n b^{-j}\rfloor})$$ Observe that for $j=0$ we always have $2^n b^{-j} \in 2\mathbb{N}$ so that all summands for $j=0$ vanish. Thus we assume $j\geq 1$ from now on.

Now we have to think about $2^n b^{-j}$. This suggests looking at the $2$-adic expansion of $b^{-j}$: $$b^{-j} =\sum_{n\geq 1} d_n 2^{-n}$$ for some $d_n\in\{0,1\}$ so that $\lfloor 2^n b^{-j} \rfloor \mod 2 = d_n$.

The nice thing about the digits $d$ of any $2$-adic expansion is that $\frac{1}{2}(1-(-1)^d)$ not just indicates whether or not $d$ is odd, it is actually equal to $d$, because $d\in\{0,1\}$. Therefore $\frac{1}{2}(1-(-1)^{\lfloor 2^{n} b^{-j} \rfloor})=\frac{1}{2}(1-(-1)^{d_n})=d_n$.

Thus: $$\sum_{j\geq 1} \sum_{n\geq 1} 2^{-n} \frac{1}{2}(1-(-1)^{\lfloor 2^n b^{-j} \rfloor}) = \sum_{j\geq 1} \sum_{n\geq 1} 2^{-n} d_n = \sum_{j\geq 1} b^{-j} = \frac{1}{b-1}$$ and that's what we wanted to prove.

• That was an amazing proof. Much more simple than I imagined. – Kitegi Jan 31 '16 at 15:57