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}\ldots$$

All the terms cancel apart from 2s(1)/9 which is two ninths (and the remaining terms tend to 0 being as the numerator is linear in k and the denominator is exponential).

Let $f_i(n)$ be 1 if the $i$th digit from the end of $n$. (the 0th digit being the units, the 1st digit being the tens and so on) is greater than or equal to 5, so $f(n)=\Sigma_if_i(n)$.

$f_i(2^k)=1$ if and only if the fractional part of $\frac{2^k}{10^{i+1}}$ is at least a half. As it happens, this is exactly the condition required for the $(k+1)$th digit after the decimal point in the binary expansion of $\frac1{10^{i+1}}$ to be a 1.

Thus $\Sigma_k\frac{f_i(2^k)}{2^k}$ is the sum of $\frac{1}{2^k}$ for all k where the $(k+1)$th digit after the decimal point in the binary expansion of $\frac1{10^{i+1}}$ is a 1. Given that that's how binary expansions work, this means that $\Sigma_k\frac{f_i(2^k)}{2^k}=\frac2{10^{i+1}}$, so
$$\Sigma_k\frac{f(2^k)}{2^k}=\Sigma_k\Sigma_i\frac{f_i(2^k)}{2^k}=\Sigma_i\frac2{10^{i+1}}=\frac29$$ .

However, I think the blind alley I went down is worthy of a bit more exploration.

I started by thinking (wrongly) that if there is a nice solution to this, it would also give the solution for any other condition on the digits, other than just being greater than or equal to 5, so I started by looking for the sum of $g(2^k)/2^k$ where $g$ is the number of digits in $n$. So I fired up python and typed

>>>> x = sum(Fraction(len(str(1<<k for k in xrange(1000))
>>>> int(x)
2
>>>> int(1/(x-2))
7
>>>> int(1/(1/(x-2)-7))
146
>>>> int(1/(1/(1/(x-2)-7)-146))
9680860522270813488947208L
>>>> y = 2+1/(7+Fraction(1,146))
>>>> y
Fraction(2192, 1023)
>>>> float(x)
2.142717497556207
>>>> float(y)
2.142717497556207
>>>> 

So I assumed the answer was $\frac{2192}{1023}$ and moved on. I then looked at what the answer was in other bases - base 9 seemed to have $\frac{1123471}{2^{19}-1}$, 8 is trivially $\frac{16}{7}$ and so on, but I couldn't find a pattern. Further once I had seen both solutions I couldn't see how either could give $\frac{2192}{1023}$.

This morning I realised that I should stop trying to figure out why the sum of $g(2^k)/2^k$ is $\frac{2192}{1023}$, because it isn't. It's just very close. In fact, it's irrational: $$\Sigma_k\frac{g(2^k)}{2^k}=\Sigma_{j,k:10^j\le2^k}\frac{1}{2^k}=\Sigma_j\Sigma_{k\ge\mathrm{log}_2(10)j}\frac{1}{2^k} =\Sigma_j\frac{1}{2^{\lceil\mathrm{log}_2(10)j\rceil-1}}.$$

Since $\mathrm{log}_2(10)$ is irrational (no number is simultaneously a power of 2 and a power of 10), the binary expansion of the sum is not recurring, so the sum itself is irrational. But why is it so darn close to $\frac{2192}{1023}$?

>>>> x = sum(Fraction(len(str(1<<k for k in xrange(1000))
>>>> int(1/(x-Fraction(2192,1023))
10131301281511552169774432648193
>>>> x = sum(Fraction(len(str(1<<k for k in xrange(10000))
>>>> int(1/(x-Fraction(2192,1023))
10131301281511552169774432648193

Well that's because $\mathrm{log}_{10}(2)=0.3010\ldots$ is very close to 0.3. We said above that the sum was $\Sigma_j\frac{1}{2^{\lceil\mathrm{log}_2(10)j\rceil-1}}$, which would make it very close to $\Sigma_j\frac{1}{2^{\lceil j/0.3\rceil-1}}$, which is $2+\Sigma_k\frac1{2^{3+10k}}+\frac1{2^{6+10k}}+\frac1{2^{9+10k}}=\frac{2192}{1023}$.

Another way to express $\Sigma_j\frac{1}{2^{\lceil\mathrm{log}_2(10)j\rceil-1}}$ is that it is 2 plus the sums of the reciprocals of the largest 1-digit power of 2, 2-digit power of 2 and so on:
$$2+\frac18+\frac1{64}+\frac1{512}+\frac1{8192}+\frac{1}{65536}+\frac{1}{524288}\ldots.$$

Because 1024 is so close to 1000, if you start with 8 and continue multiplying by 1024, for a long time you will get the largest $3k+1$-digit power of 2. But because it is more than 1000, eventually you will get a $3k+2$-digit power of 2, and this is where the binary expansions of the above sum and $\frac{2192}{1023}$ will first differ. As it happens, this is at the 103rd binary digit.

>>>> 8*(1024**9)
9903520314283042199192993792
>>>> 8*(1024**10)
10141204801825835211973625643008

This does lead to some other questions. For instance, one could ask whether >=5 is the only condition on the digits that leads to a rational solution. But this feels like enough for one post.