# Always oddly-many ones in the binary expression for $10^{10^{n}}$?

Update: Pending independent verification, the answer to the title question is "no", according to a computation of $q(10) = 11609679812$ (which is even).

Let $q(n)$ be the number of ones in the binary expression for $10^{10^{n}}$ (which is the same as for $5^{10^{n}}$ of course), for positive integer $n$. The first nine $q(n)$ values — the most I can compute — are all odd: $11, 105, 1163, 11683, 115979, 1161413, 11606847, 116093517, 1160951533$. Is this just a quirk (with even values showing up eventually), or is $q(n)$ odd for all positive integer $n$? Equivalently, letting $t(0),t(1),t(2)...$ be the Thue-Morse sequence, is $t(10^{10^{n}}) = 1$ for all positive integer $n$?

It may not be surprising that about half of the binary digits of $5^{10^{n}}$ are ones, i.e., $q(n) \sim \displaystyle\frac{1}{2} \log_2(5^{10^{n}}) \approx \ 1.16096404744 \cdot 10^{n}$ (thus explaining the leading digits of sufficiently large terms), but why should all the terms be odd (if indeed they are)?

Note: My motivation for posting is the expectation that a proposition like "$q(10^{10})$ is even" provides a problem of the kind that Solomon Feferman ("Are there absolutely unsolvable problems?", p. 16), calls "absolutely unsolvable from the standpoint of practice". Obviously, this expectation is wrong if it can be proved that $q(n)$ is odd for all positive integer $n$. I strongly suspect, however, that there are infinitely many $q(n)$ values of each parity.

• whoops, you're right. – Qiaochu Yuan Oct 5 '11 at 17:10
• I'd mention oeis.org/A118738, but it doesn't seem to have any information. – Charles Oct 5 '11 at 19:47
• Could you describe how you got up to $n=9$? When I take the direct approach and calculate the powers using Java's BigInteger class, already $n=7$ takes a long time; I'd presume that they use efficient methods to calculate the powers; are you doing something more sophisticated? – joriki Oct 7 '11 at 7:08
• @joriki: I imagine r.e.s. is using Fast Fourier Transforms. I would be surprised if FFT was built into the BigInteger class. – TonyK Oct 7 '11 at 8:35
• Writing an answer to your own question is fine. See meta.math.stackexchange.com/questions/1401/… – Gerry Myerson Oct 12 '11 at 3:51

The answer to the title question is "no" according to the following computation in a Sage notebook:

%time
for n in [1..10]: print n, (5^10^n).popcount()

1 11
2 105
3 1163
4 11683
5 115979
6 1161413
7 11606847
8 116093517
9 1160951533
10 11609679812

CPU time: 487.60 s,  Wall time: 1935.41 s


EDIT: In Sage, the popcount() method -- which returns the number of ones in the binary representation -- is built-in for objects of type 'Integer' (but not for type 'long', which I had been forcing), making it unnecessary to import gmpy, etc., as done previously.

• Just one (hopefully-obvious) comment: you may want to use the 'hybrid' approach through gmpy (and the bin counting) on the previous problem instances to confirm that the results you get match the already-known results... – Steven Stadnicki Oct 12 '11 at 16:36
• Yes, I already did that, and they agree. – r.e.s. Oct 12 '11 at 16:43