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
    whoops, you're right.2011-10-05
  • 0
    I'd mention http://oeis.org/A118738, but it doesn't seem to have any information.2011-10-05
  • 0
    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?2011-10-07
  • 0
    @joriki: I imagine r.e.s. is using Fast Fourier Transforms. I would be surprised if FFT was built into the BigInteger class.2011-10-07
  • 0
    @joriki: I used a [Sage](http://sagemath.org) notebook with `def q(n): return bin(5^(10^n)).count('1')`, which took less than a minute.2011-10-07
  • 0
    On the other hand, I would not be at all surprised if FFT was built into Sage.2011-10-07
  • 0
    I just updated the question with results of a computation of $q(10)$ (which is *even*, if the computation is correct). Being new to SE, I wasn't sure just how to present this in the body of the question. I'm happy to explain the computation details, of course, but I don't know whether this would be the right place for it. Or should I just write it into an answer to my own question?2011-10-12
  • 3
    Writing an answer to your own question is fine. See http://meta.math.stackexchange.com/questions/1401/what-to-do-if-you-figure-out-the-answer-to-your-own-question2011-10-12
  • 0
    @r.e.s.: By all means give us a few details on how you carried out the computation. Especially as joriki specifically asked you about it!2011-10-12
  • 0
    @Gerry Myerson: Thanks for the advice and link.2011-10-12
  • 0
    @TonyK: Well, I hope I haven't overdone the detail in my answer concerning $q(10)$.2011-10-12
  • 0
    See also this: http://blog.stackoverflow.com/2011/07/its-ok-to-ask-and-answer-your-own-questions/2011-10-12
  • 0
    @joriki: That linked post is very encouraging ... thank you.2011-10-13
  • 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.

  • 0
    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...2011-10-12
  • 1
    Yes, I already did that, and they agree.2011-10-12