How many zeros are there in 2^n?

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

In: Uncategorized
Comment!

0 Shares

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