The first digit of 2^n

The sequence of powers of two

produces the sequence a_n of first digits of powers of two (base ten). So, a_1=2, a_2=4, a_3=8, a_4=1, a_5=3, and so on. Does the number seven ever occur in the sequence a_n? Which occurs most frequently, seven or eight? Determine explicitly the probability that 1 occurs as a first digit and repeat for each of 2, 3, 4, ..., 9.

The probability that the number five, for instance, occurs in a_n is the limit

Need a hint? Click here.

Click here for the complete solution.

Hint 1

The solution of this problem will require the following result:

Theorem A Let \alpha be an irrational number, and x_n = \{ n \alpha \} be the fractional part of n \alpha. Then the sequence x_n is uniformly distributed over the interval [0,1), in the sense that for every interval I \subseteq [0, 1) we have

Intuitively, this means that the sequence does not 'prefer' any portion of I, and the proportion of times x_n spends in a given interval is equal to the length of the interval.

Assuming Theorem A true, our problem can be solved without too much effort. On the other hand, a proof of Theorem A requires some work, but also provides a good opportunity for illustrating a number of important notions and techniques in Real Analysis (such as the Fourier series of continuous functions, uniform convergence, and approximation methods for piecewise continuous functions).

Click here for a proof of Theorem A.

Hint 2

Any real number x can be written as x = \lfloor x \rfloor + \{ x \}, where \lfloor x \rfloor denotes the integer part of x and \{ x \} the fractional part. Use this fact to express the first digit of 2^n as the integer part of a fractional power of 10.

Hint 3

Let's fix n \ge 1. Then there will be some integer m \ge 0 such that

and we can write

We want to express both m and a_n as explicit functions of n. Taking the logarithm of (1) (in base 10), we find m < n \log_{10} 2 < m + 1. So we have m = \lfloor n \log_{10} 2 \rfloor. Writing x_n =\{ n \log_{10} 2 \}, we find n \log_{10} 2 = m + x_n, which is equivalent to

Dividing (2) by 10^m, we get 2^n 10^{-m} = a_n + r 10^{-m}. Since r10^{-m} < 1, and using (3), this last equation implies that

Find subintervals I_d of [0,1] such that a_n = d is equivalent to x_n \in I_d.

Hint 4

We know that a_n = \lfloor 10^{x_n} \rfloor. Hence we obtain

So if we denote by I_d the interval [\,\log_{10} d, \log_{10}(d+1)\,), we find that the leading digit a_n of 2^n is equal to d precisely when the number x_n is contained in I_d .

Prove that \log_{10} 2 is irrational. Then use Theorem A to solve the original problem.

The Rest of the Solution

Let's assume that \log_{10} 2 is rational, say \log_{10} 2 = n/m. It then follows that 2^m = 10^n = 2^n \cdot 5^n, which is impossible for any n > 0.

So we conclude that \log_{10} 2 is irrational.

The original question can be rephrased as follows: for each given d, how often (if ever at all) are the numbers x_n = \{ n \log_{10} 2 \} contained in the interval I_d?

To be more precise, the original question is: find \lim_{n \to \infty} \frac{1}{n} |\{k: x_k \in I, 1 \le k \le n \}|.

But this is precisely the content of Theorem A: since \log_{10} 2 is irrational, the limit is I_d , the length of the interval.

So the proportion of time the leading digit of 2^n is d is equal to |I_d| = \log_{10} (1 + 1/d). Note that this function decreases with d, so the digit 1 will occur most often, and 9 least often.

The following table gives the lengths of I_d for d = 1, 2, \dots, 9.

The next table shows the actual distribution N(d) = |\{ n: 1 \le n \ne 100, a_n = d\}| of the first digit a_n in the first 100 powers of 2.

Notes

It should be clear that the same proof can be carried out for the first digit of b^n, for any b, provided \log_{10} b is irrational. This leads us to ask the question: is \log_{10} b irrational as long as b is not a power of 10?

The distribution of the last digit of powers of integers is much more regular. Try to think about it.

Benford's Law is an empirical result about the first digits of real-life data; it has the same distribution as our result. Wikipedia has an article on Benford's Law.