Posts

Digits in powers of 2

An ex-colleague of mine who is also fond of brainteasers shared the following excellent problem with me the other day: Let $f(n)$ denote the number of digits of $n$ (in base 10) that are greater than or equal to 5 (so $f(128)=1, f(1024)=0$ and $f(1048576)=4$). What is the sum of $f(2^k)/2^k$ (from $k=0$ to $\infty$)? It seemed very unlikely to me that this would have a nice solution, but after some initial exploration and a few blind alleys I was able to find one. Turned out to be different to the nice solution my ex-colleague had in mind. I present both solutions here (behind spoiler tags): Let $s(n)$ denote the sum of the digits of $n$. Then if you consider manually adding n to itself, the digits greater than or equal to 5 are the ones that force you to carry a 1. Therefore, $f(n)=\frac{2s(n)-s(2n)}9$. As such, the sum of $f(2^k)/2^k$ is \[\frac{f(1)}1+\frac{f(2)}2+\frac{f(4)}4\ldots=\frac{2s(1)-s(2)}{9\times1}+\frac{2s(2)-s(4)}{9\times2}+\frac{4s(4)-s(8)}{9\times4}\ldot