Republic of Mathematics blog

How many zeros are there in 2^n?

Posted by: Gary Ernest Davis on: April 23, 2011

An old problem asks if 2^{86} is the highest power of 2 whose base 10 representation: 2^{86}=77371252455336267181195264 , does not contain the digit 0.

For instance, the next 14 powers of 2 do indeed contain the digit 0:

2^{87} =   1547425\textbf{0}491\textbf{0}67253436239\textbf{0}528
2^{88} =   3\textbf{0}9485\textbf{0}\textbf{0}9821345\textbf{0}68724781\textbf{0}56
2^{89} =   61897\textbf{0}\textbf{0}1964269\textbf{0}137449562112
2^{90} = 123794\textbf{0}\textbf{0}3928538\textbf{0}274899124224
2^{91} =   247588\textbf{0}\textbf{0}7857\textbf{0}76\textbf{0}549798248448
2^{92} =   495176\textbf{0}157141521\textbf{0}99596496896
2^{93} = 99\textbf{0}352\textbf{0}314283\textbf{0}42199192993792
2^{94} =   198\textbf{0}7\textbf{0}4\textbf{0}628566\textbf{0}84398385987584
2^{95} = 39614\textbf{0}81257132168796771975168
2^{96} = 7922816251426433759354395\textbf{0}336
2^{97} = 158456325\textbf{0}28528675187\textbf{0}879\textbf{0}\textbf{0}672
2^{98} =   31691265\textbf{0}\textbf{0}57\textbf{0}5735\textbf{0}3741758\textbf{0}1344
2^{99} =   6338253\textbf{0}\textbf{0}1141147\textbf{0}\textbf{0}7483516\textbf{0}2688
2^{100} = 126765\textbf{0}6\textbf{0}\textbf{0}2282294\textbf{0}14967\textbf{0}32\textbf{0}5376

x

How many zeros?

Instead of asking the existential question “Is there a zero in the base 10 representation of 2^n for n\geq 87?” we can ask the more quantitative question: “How many zeros are there in the base 10 representation of 2^n.

Here are plots of the number of zeros in the base 10 representation of 2^n for n up to 100, 500, 1000, 10000, 50000 respectively:

We see, progressively, what seems to be oscillations around a straight line.

What could this straight line be?

And how large are the oscillations?

A straight line model

The number of digits of 2^n is  \lfloor log_{10}(2^n)\rfloor +1, where \lfloor x\rfloor is the integer part of x.

Neither the first nor last digit of 2^n is 0, so there are \lfloor log_{10}(2^n)\rfloor -1 digits of 2^n that can be 0.

If we assume that all 10 digits 0,1,\ldots 9 are equally distributed among these \lfloor log_{10}(2^n)\rfloor -1 places then we expect to see about n\frac{log_{10}(2)}{10} zeros in base 10 representation of 2^n for large enough n

So we take as a linear model for the number of zeros in base 10 representation of 2^n the quantity n\frac{log_{10}(2)}{10}\approx .030103n

To get a visual feel for how this fits let’s plot the actual number of zeros along with this linear model:

The nature of the “error”

We now have a statistical model for the number of zeros, Z(n) in the base 10 representation of 2^n:

Z(n)=n\frac{log_{10}(2)}{10}+\epsilon_n

where we will refer to \epsilon_n as the “error” (meaning how much Z(n) differs from the linear model).

How does the error behave?

In particular, how is it distributed?

Below is a histogram of the error \epsilon_n for n\leq 50,000, together with a normal curve of the same mean and standard deviation:

We can see the the empirical distribution of the error is “peakier” than the normal distribution, and this is borne out by the kurtosis which is 3.9789 \approx 4, substantially greater than a kurtosis of 3 for the normal distribution.

Plotting these histograms for various values of n indicates that the variance of the distribution of the errors \epsilon_n varies linearly with n, or, what amounts to the same thing, the standard deviation varies with \sqrt{n}.

Bounding the error

What we really seek is a bound on the errors sufficient to show that Z(n)=n\frac{log_{10}(2)}{10}+\epsilon_n>0 for large enough n.

What does computation suggest?

Below is a plot of the size of the error \vert\epsilon\vert divided by n.

It appears that \frac{ \vert\epsilon\vert}{n}\leq \frac{1}{50} even for quite small n:

If this does hold good then Z(n)\geq n\frac{log_{10}(2)}{10} - \frac{n}{50} >0

So now we have a more precise statement: prove that \vert Z(n)-n\frac{log_{10}(2)}{10}\vert\leq \frac{n}{50} for n\geq 200.

Maybe techniques of higher order Fourier analysis (Higher-Order_Fourier_Tao) could be brought to bear on this problem since they are useful in proving other equidistribution theorems? Then again, just because Weyl’s polynomial equidistribution  theorem can be interpreted as a higher-order Fourier analysis application may have nothing at all to do with equidistribution of digits in 2^n.

 

6 Responses to "How many zeros are there in 2^n?"

The tens digit can also never by 0. (You can reason it out or just look at the 2^n mod 100 cycle.) I don’t think it affects the slope of your model, but it would affect the intercept. Maybe that would make your histogram be better centered on the normal curve.

@Xan: “The tens digit can also never by 0.”

2^23 = 8,388,608

Did I misinterpret what you said?

I think I wrote the first and last digit, the first digit being the coefficient of 10^0.

You wrote Epsilon/n <= 50 above your final figure. I think you meant to write Epsilon/n <= 1/50. Otherwise, it was an interesting read.

Thanks – fixed.

Leave a Reply to Gary Ernest Davis Cancel reply