Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I believe this question is due to Erdős and Graham, and I think it is still open: does the base 3 expansion of $2^n$ avoid the digit 2 for infinitely many $n$?

If we concatenate the digits of $2^i$, $i \geq 0$, we produce the number $0.110100100010000...$. This number is not simply normal in base 2, so it is not normal. Is it simply normal in base 3? I think even that result would not imply that for sufficiently large $n$, 2 doesn't appear in the base 3 expansion of $2^n$.

The number 20 here is not special:

$2^{20} = 1222021101011_3, \;\;\;\; 2^{21} = 10221112202022_3, \;\;\; 2^{22} = 21220002111121_3$

Statistically, we seem to be flipping a fair 3-sided coin, and statistical analysis for larger $n$ bears this out (in the past, I did a p-test on the digits, but don't have the data available here). If we actually produced these digits by flipping this 3-sided coin, for fixed $n$ we would have probability about $$(2/3)^{n\ln2/\ln3}$$ of having no 2s in the base-3 digit expansion.

What is the state of the art for this problem? Is there a good number-theoretic reason why this problem should be very difficult (e.g. an analogy with other supposed-hard problems)? Are there related problems that have been solved?

share|improve this question
    
So I guess you mean cases like $2^8 = 100111_3$? If I computed correctly. –  Helge Jul 30 '10 at 22:00
    
Yes, but as the number of digits increases, these become increasingly unlikely. Under the assumption, of course, that the base 3 digits of 2^n are random, which they are not. –  Eric Tressler Jul 30 '10 at 22:56

3 Answers 3

up vote 3 down vote accepted

As of a few months ago, the status of the problem was: still unsolved. See the slides Jeff Lagarias put up from a talk he gave in September 2009: http://www.math.lsa.umich.edu/~lagarias/talks-files/fields-horz5.pdf

An older reference is http://www.americanscientist.org/issues/id.3268,y.0,no.,content.true,page.2,css.print/issue.aspx (Brian Hayes, Third Base, American Scientist) which says the problem was still open in late 2001; also that Ilan Vardi searched up to $2^{6973568802}$ without finding any 2-less powers of 2 (other than $2^2$ and $2^8$).

share|improve this answer
    
This sounds comprehensive. Lagarias's slides in particular are very interesting. Thanks for the references. –  Eric Tressler Jul 31 '10 at 16:24

... and $\sum (2/3)^{n\log 2/\log 3} < \infty$ so (if things were random) we would expect only finitely many such occurrences by Borel-Cantelli easy direction.

But of course proving this is anything like random is far too hard for today's tools, I think.

share|improve this answer

Something way easier that one can prove is that your sequence is disjunctive, which is much weaker than normality. This is true since for every string of digits $k$ you can find a power of two with a base 3 expansion that starts with k.

I don't know much about normality except that there are many conjectures (for example that every irrational algebraic number is normal) and no techniques to answer such questions except in trivial cases. I believe the current state is similar for simply normal numbers.

Another question that is similar in spirit and that was answered recently is Stolarsky's conjecture that says $$\liminf_{n\to \infty}\frac{s_q(n^k)}{s_q(n)}=0$$ where $s_q(\cdot)$ is the sum of digits in base $q$. Intuitively it is hard to come up with examples that $s _3(2^{nk)} < s_3(2^k)$ for most $k$, let alone that the $\liminf$ is zero. However this question is much weaker than the one you ask since the sum of digits puts very few restraints on the digits themselves.

share|improve this answer
    
Thank you for the reference. I will read the proof of Stolarsky's conjecture (assuming it was answered in the positive). –  Eric Tressler Jul 31 '10 at 16:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.