49
$\begingroup$

We call a number "holy" if it contains no $666$ in its decimal expansion, and "unholy" otherwise. For instance, $12366621$ and $666609$ are unholy, while $7777$ and $66166266366$ are holy.

Question: Is the set $$\{2^n \ | \ n \in \mathbb N, 2^n \text{ is holy}\}$$ infinite?

Of course, tons of similar questions can be asked by changing the number $666$, the base $2$, and the base for extension (we asked for decimal, so the default was $10$). I do not feel that I am the first one asking this, and I appreciate it if someone gives me references if applicable.

But my thought is the following:

Conjecture: No.

I will share my reasoning at the end of the post, but let us first see some facts:

Smallest unholy instances: $$ \begin{aligned} 2^{157} &= 182687704\color{magenta}{666}362864775460604089535377456991567872\\ 2^{192} &= 6277101735386680763835789423207\color{magenta}{666}416102355444464034512896 \end{aligned} $$

Then, we witnessed a cluster of unholy powers: $2^{218}, 2^{220}, 2^{222}, 2^{224}, 2^{226}$, and then kept holy for a while, until we hit the unholy $2^{243}$.

Largest holy instances: I did not throw in a lot of CPU time to pursue holy numbers, nor did I try hard enough to optimize my programs, but among the $3715$ holy powers of $2$, the largest of them are $$2^{25357}, 2^{25896}, 2^{26051}, 2^{26667}, 2^{29784}.$$

I tested up to around $2^{110000}$, but that is all I got. It probably will be reasonable for an average computer to test up to say $2^{10^6}$ or $2^{10^7}$, but I will be surprised to see a new holy number.

Statistics: For an integer $n$, let $H(n)$ be the number of holy powers of $2$ up to $2^n$.

n      | H(n)     || n      | H(n)     || n      | H(n)
 1000  |  875     || 11000  | 3567     || 21000  | 3700
 2000  | 1560     || 12000  | 3602     || 22000  | 3703
 3000  | 2059     || 13000  | 3621     || 23000  | 3705
 4000  | 2442     || 14000  | 3645     || 24000  | 3707
 5000  | 2747     || 15000  | 3655     || 25000  | 3709
 6000  | 2984     || 16000  | 3670     || 26000  | 3712
 7000  | 3171     || 17000  | 3682     || 27000  | 3714
 8000  | 3332     || 18000  | 3689     || 28000  | 3714
 9000  | 3440     || 19000  | 3693     || 29000  | 3714
10000  | 3514     || 20000  | 3695     || 30000  | 3715

A plot of this: enter image description here

The heuristics of the conjecture:

This is definitely not close to a proof at all, and I still hope if rigorous arguments exists:

The idea is that we want to estimate, for an integer $n$, the probability $P(n)$ that $2^n$ is holy, and then compute $\sum_{n=1}^\infty P(n)$.

We know that $2^n$ has $O(n\ln 2)$ decimal digits, so there are $O(n\ln 2)$ groups of three. For each group there is a $1-10^{-3}$ chance to be not $666$, so very roughly $$ P(n) = (1-10^{-3})^{n\ln 2} \approx e^{-10^{-3}\ n\ln 2}. $$

And note that $$ \sum_{n=1}^\infty P(n) \approx \int_{n=0}^\infty e^{-10^{-3}\ x\ln 2} dx < \infty. $$

The red "estimation line" in the figure above follows from this integral.

Of course, one can easily argue the properness of the heuristic above:

  • The distribution of the digits close to the left are not uniform; they are affected by the growth of logarithmic functions.
  • The distribution of the digits close to the right are not uniform; they are affected by the pattern of $2^n \pmod{10^k}$.
  • $P(n)$ and $P(n+i)$ are not independent, partially because of the awful choice of the number $666$: $6\cdots 6 \times 2^2 = 26\cdots 64$.

Any thoughts are appreciated.

$\endgroup$
  • 5
    $\begingroup$ It doesn't help, but a cute application of Dirichlet denseness theorem shows that there are infinitely many powers of 2 starting with the digits 666.... They are unholly but very rare. $\endgroup$ – N. S. Sep 27 at 2:29
  • 4
    $\begingroup$ Thanks for the comment! At least it shows that unholy powers appears in density at least $\log_{10} 667/666$. Not sure how well we can push this number to somewhere close to $1$ by the similar approach. $\endgroup$ – Hw Chu Sep 27 at 2:41
  • 8
    $\begingroup$ Your conjecture is indeed a known open problem, and in fact we expect that there is some $N>0$ such that $666$ occurs among the digits of the decimal expansion of $2^n$, for every $n>N$ ! See blog.tanyakhovanova.com/2011/02/86-conjecture, johndcook.com/blog/2012/11/23/digits-in-powers-of-2, OEIS A035064, A030706, A007377, A035062. $$ $$ Closely related : math.stackexchange.com/questions/167607, math.stackexchange.com/questions/1199682 $\endgroup$ – Watson Sep 27 at 7:58
  • 2
    $\begingroup$ Here is a relevant open problem by Fürstenberg, which apparently gives an approach to the above conjecture (even though I'm not sure to understand why), according to the page 189 of Ten Lectures on the Interface between Analytic Number Theory and Harmonic Analysis (reference given in John Cook's post linked above). See also problems 10.25 and 10.27 in Yann Bugeaud's Distribution Modulo One and Diophantine Approximation. $\endgroup$ – Watson Sep 27 at 18:09
  • 2
    $\begingroup$ For the sake of completeness, here is an excerpt of Fürstenberg's paper explaining the relation between the two problems (Conjectures 2 and 2' in his paper). Reference: Intersections of Cantor sets and transversality of semigroups in "Problems in Analysis. A Symposium in Honor of Salomon Bochner ". $\endgroup$ – Watson Sep 27 at 18:22
17
+500
$\begingroup$

This is not an answer, but only a few comments.

Your conjecture is indeed a known open problem, and in fact we expect that there is some $N>0$ such that $666$ occurs among the digits of the decimal expansion of $2^n$, for every $n>N$ ! Of course, one can replace $k=666$ by any positive integer $k$ (more accurately, any sequence of digits).

See also this blog post (for the case $k=0$), Problem 24 in Unsolved Problems in Number Theory by Richard Guy, here, or those OEIS sequences : A035064, A030706, A007377, A035062. These are closely related questions : (1), (2), (3).

Here is a relevant open problem by Fürstenberg, which apparently gives an approach to the above conjecture (even though I'm not sure to understand why), according to the page 189 of Ten Lectures on the Interface between Analytic Number Theory and Harmonic Analysis (reference given in John Cook's post linked above). See also problems 10.25 and 10.27 in Yann Bugeaud's Distribution Modulo One and Diophantine Approximation. According to this paper, Fürstenberg's conjecture is just "far out of reach" ! Similarly, in §6.6, p. 138 of Bugeaud's book, it is mentioned that "Erdős asked how often the ternary expansion of $2^n$ omits the digit $2$. It is likely that there are only finitely many such integers $n$ but the problem is still beyond reach"$^{[1]}$ !

For the sake of completeness, here is an excerpt of Fürstenberg's paper explaining the relation between the two problems (Conjectures 2 and 2' in his paper). Reference: Intersections of Cantor sets and transversality of semigroups in "Problems in Analysis. A Symposium in Honor of Salomon Bochner".

To sum up, we expect any given sequence of digits to occur in the decimal expansion of all but finitely many powers of $2$, but this is currently an unsolved problem which is out of reach!


$^{[1]}$ One of the best result known so far is given as exercise 6.4 in Bugeaud's book. Namely, if $N(X)$ denotes the number of positive integers $m \leq X$ such that $2^m$ has no "$2$" in its ternary expansion, then $N(X) \leq 1.62 X^{\log(2) / \log (3)}$. The (intractable) conjecture is that $N(X)$ is bounded.

$\endgroup$
  • 3
    $\begingroup$ Thanks for writing it up as an answer! I will accept it (until it is proven or unproven, at least ;-) ). $\endgroup$ – Hw Chu Sep 29 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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