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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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. – Helge 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. – Eric Tressler Jul 30 2010 at 22:56

## 3 Answers

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

-

This sounds comprehensive. Lagarias's slides in particular are very interesting. Thanks for the references. – Eric Tressler Jul 31 2010 at 16:24

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

... 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). – Eric Tressler Jul 31 2010 at 16:17
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9550204277038574, "perplexity_flag": "middle"}