25
$\begingroup$

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.

  • 0
    Feferman's article asserts that the question "Is the value of the digit in the $10^{10^{10^{10}}}$th place of the decimal expansion of $\pi - 3$ equal to $0$?" "cannot be settled by the human mind because it is beyond all remotely conceivable computational power on the one hand and *there is no conceptual foothold to settle it by a proof* on the other." My motivating question is whether exactly the same is true of the question "Are there evenly many ones in the binary expression for $10^{10^{10^{10}}}$?" -- or does $\pi$ have some special quality that sets it apart in this regard?2011-10-13

1 Answers 1

14

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.

  • 1
    Yes, I already did that, and they agree.2011-10-12