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):
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
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}$?
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.
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.
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):
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.
Comments
Post a Comment