On Powers of 2

Let's start with an interesting little problem.
Problem. Consider a sequence a(n) consisting of the first digits of the consecutive powers of 2:

1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1, 2, 4, 8, ...

Will 7 ever appear in this sequence?

This problem (in different versions) is well known in mathematical literature. It can be found e.g. in A walking mathematician by Zbigniew Marciniak (Delta 7/1991) or in the famous book Ordinary differential equations by V.I.Arnold. It is usually accompanied by auxiliary facts or suggestions intended to make a solution more accessible. Nevertheless, I do not know of any publication, in which the problem would be presented together with a complete solution, all details included. Let's try to remedy this unfortunate situation.

To start with - a desperate solution using a piece of paper and a pencil or some more advanced version of this set of tools (a good calculator? a computer?). An assiduous reader will easily verify that

Going further with this experiment he can see that 7 is the first digit of 56-th, 66-th, 76-th, 86-th and 96-th power of 2 (but the first digit of 106-th power of 2 is 8, not 7). This method, however, is clearly far from being elegant.

It's time then for a better solution, which would also allow to draw other conclusions. First of all, we must try to realize what is the meaning of the statement that 7 is the first digit of a number

The answer is simple: 7 is the first digit of if and only if for some natural k we have

We can get a simpler description of this condition if we take the decimal logarithms of both sides; this yields k + log(7) < n log(2) < k + log(8). Since decimal logarithms of 7 and 8 lie between 0 and 1, we conclude that k is the integer part of the number n log(2), which leads to the following inequalitites:

And now it suffices to bring together some known facts.

Lemma 1. The number log(2) is irrational.

Lemma 2. If a number x is irrational and c(n):=nx-[nx], then for any a and b belonging to [0,1] infinitely many members of the sequence c(n) lie in the interval (a,b).

Before we prove these two lemmas let's have a look at their consequences. First, by applying Lemma 2 to x=log(2), a=log(7), b=log(8) we get that 7 is the first digit of infinitely many powers of 2. If we apply again Lemma 2 to numbers x=log(2), a=log(77)-1, b=log(78)-1, then because of the equalities 1=[log 77]=[log 78], we conclude that the figure seven can even appear twice in the first two places of the decimal notation of a power of 2. Using an analogous argument we readily discover that any finite sequence of digits can appear at the beginning of a decimal notation of a power of 2, like 1995 or 1234 or 567890 etc. At the end of this article we exhibit a table of important historical dates compared with corresponding powers of 2 - to satisfy the sceptics.

We can even deduce more:

Corollary. If an integer p > 1 is not an integer power of 10, then any sequence of digits can appear at the beginning of the decimal notation of n-th power of p for some n.

To prove the corollary just observe that log(p) is irrational and then repeat the same argument as above.

Now, Dear Reader, go ahead and try to prove both Lemmas. (If you prefer, click and read them.)

Proof of Lemma 1.

Proof of Lemma 2.

But then, why does 7 not appear among the first memebrs of the sequence we introduced at the very beginning? Why does this deceitful sequence pretend to be periodical? The reason is simple. The number log(2)=0.3010299956... can be very well approximated by the rational number 0.3, and for all rational x the sequence c(n) = nx - [nx] is periodical. This is why after seeing the first initial members of the sequence a(n) we come to an erroneous conclusion that the sequence has period 10 and 7 is not a member of it, while 8 appears quite often.

In 1910 Waclaw Sierpinski, Hermann Weyl and P.Bohl proved independently of each other that for an irrational x the sequence c(n)=nx - [nx] is homogeneously distributed over the interval [0,1]. More precisely, if we take arbitrary a and b (with a < b) from [0,1], and let k(n,a,b) denote the number of elements of the set

then

Speaking in more illustrative terms, the theorem states that if we walk along a circumference of perimeter 1 long enough making steps of irrational length, then we shall step on each hole with a frequency which is directly proportional to the size of the hole.

Let's translate this fact into our language of powers of 2. Let a(7,n) and a(8,n) be the number of sevens and eights, correspondingly, among the first n members of the sequence a(n). By the last formula, we have

so consequently

This means that looking at sufficiently long initial fragments of the sequence a(n) we will see slightly more sevens than eights.

The result of Bohl, Sierpiński and Weyl which we have previously mentioned and our little fact on sevens and eights are in fact simple consequences of a very general and deep ergodic theorem due to G.D.Birkhoff (1931), but that's another story.

A calendar of powers of 2

A problem for the reader: For what n does the number have four consecutive sevens at the beginning? What about five sevens? How to estimate from above the least n such that the decimal notation of begins with 1995 consecutive sevens?

Pawel Strzelecki
Institute of Mathematics, Warsaw University and ICM, Warsaw University