Do the base 3 digits of $2^n$ avoid the digit 2 infinitely often -- what is the status of this problem?

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?

• So I guess you mean cases like $2^8 = 100111_3$? If I computed correctly. Jul 30, 2010 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. Jul 30, 2010 at 22:56
• Tao (end of blog post) cites some refs & draws some analogy to the collatz conjecture. apparently Erdos conjectured "2" always appears in the base-3 expansion for all $i>8$
– vzn
Aug 26, 2014 at 18:35

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/TALK-SLIDES/ternary-fields-2009sep.pdf

An older reference is http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.6976&rep=rep1&type=pdf (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$$).

• This sounds comprehensive. Lagarias's slides in particular are very interesting. Thanks for the references. Jul 31, 2010 at 16:24
• I think the first set of slides has moved here (judging from the date and a skim, not my field) - math.lsa.umich.edu/~lagarias/TALK-SLIDES/… and the second link is also dead Dec 17, 2019 at 8:34
• jstor has the Hayes essay at Hayes, Brian. “Computing Science: Third Base.” American Scientist, vol. 89, no. 6, 2001, pp. 490–94. JSTOR, jstor.org/stable/27857554. Accessed 25 May 2022. May 25 at 9:16

... 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.

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.

• Thank you for the reference. I will read the proof of Stolarsky's conjecture (assuming it was answered in the positive). Jul 31, 2010 at 16:17