April | 2012 | Spin Foam

(This post solves the puzzle given in the previous post.)

Doing an empirical analysis

As we are interested in powers of two starting with a given set of digits, without caring about their overall magnitude, let’s plot a histogram of the values of

$\displaystyle \frac{2^n}{10^m}$ ,

with $n$ going from 1 to 100000 and $m$ chosen to get values between 0.1 and 1.

By using a simple python script and matplotlib, we get the following distribution:

Distribution of the first digits (considered as a fraction between 0.10 and 0.99) of the first 100000 powers of two.

The distribution follows Benford’s law quite precisely

The previous plot, adding the prediction given by Benford's law.

making us expect a uniform distribution in log space

Distribution of the first digits (considered as a fraction between 0.10 and 0.99) of the first 100000 powers of two but grouped in logarithmic bins.

As the leading digits expressed as fractions cover the interval between 0.1 and 1 quite densely, we can expect that some power of two will start with the digits 31415926535897932384626433832795028841971, but this plot is quite far from being a proof.

Translating the problem

We are looking for a power of two $2^n$ starting with a given sequence of $m$ digits, $k$ . By expressing the digits sequence as a fraction between 0.1 and 1, $k/10^m$ , we can represent the desired condition by the following inequality:

$\displaystyle \frac{k}{10^m} \cdot 10^d \le 2^n < \frac{k+1}{10^m} \cdot 10^d$ .

As logarithms are monotonically increasing, we can apply them on both sides of the inequality:

$\displaystyle \log_{10}\frac{k}{10^m} + d \le n \log_{10} 2 < \log_{10}\frac{k+1}{10^m} + d$ .

If we assume $k+1$ is not a power of ten, we can translate the inequality to the fractional parts of each member:

$\displaystyle \left\{\log_{10}\frac{k}{10^m} + d\right\} \le \left\{n \log_{10} 2\right\} < \left\{\log_{10}\frac{k+1}{10^m} + d\right\}$

$\displaystyle \log_{10}\frac{k}{10^m} \le \left\{n \log_{10} 2\right\} < \log_{10}\frac{k+1}{10^m}$ .

Now the problem is reduced to see if we can find a multiple of $\log_{10} 2$ such that its fractional part falls between two given real numbers. In the next section we will see how this problem can be solved.

Solving the problem

By the Archimedean property of the real numbers, we know that there must be a natural number $q$ such that

$\displaystyle \frac{1}{q} < \log_{10}\frac{k+1}{10^m} - \log_{10}\frac{k}{10^m}$ .

Now, let’s analyze the distribution of $\{n\log_{10}2\}$ for $n$ in the range 1, …, $q+1$ . As we have $q+1$ numbers inside the unit interval, we must have two numbers with separation less than or equal to $1/q$ (it’s easy to prove by contradiction). Then there are two exponents, $r$ and $s$ , such that

$\displaystyle 0 \le \left\{r\log_{10}2\right\} - \left\{s\log_{10}2\right\} \le \frac{1}{q}$ ,

$\displaystyle 0 < \left\{(r-s)\log_{10}2\right\} \le \frac{1}{q}$ ,

where we know that the inequality with zero is strict because $\log_{10}2$ is irrational. Then we can use the Archimedean property again to extend the inequality:

$\displaystyle \frac{1}{t} < \left\{(r-s)\log_{10}2\right\} \le \frac{1}{q}$ .

It's intuitively easy to see (and not very difficult to prove) that we must have a number $u$ such that

$\displaystyle u\left\{(r-s)\log_{10}2\right\} < \log_{10}\frac{k}{10^m} < (u+1)\left\{(r-s)\log_{10}2\right\} < \log_{10}\frac{k+1}{10^m}$

As all the involved numbers are in the range [0.1, 1), we can put the multipliers inside the fractional parts and we can also discard the first inequality because it's not important for our proof:

$\displaystyle \log_{10}\frac{k}{10^m} < \left\{(u+1)(r-s)\log_{10}2\right\} < \log_{10}\frac{k+1}{10^m}$ .

Removing the fractional parts:

$\displaystyle \log_{10}\frac{k}{10^m} + \lfloor(u+1)(r-s)\log_{10}2\rfloor < (u+1)(r-s)\log_{10}2$

$\displaystyle (u+1)(r-s)\log_{10}2 < \log_{10}\frac{k+1}{10^m} + \lfloor(u+1)(r-s)\log_{10}2\rfloor$

Exponentiating:

$\displaystyle \frac{k}{10^m} \cdot 10^{\lfloor(u+1)(r-s)\log_{10}2\rfloor} < 2^{(u+1)(r-s)}$

$\displaystyle 2^{(u+1)(r-s)} < \frac{k+1}{10^m}\cdot 10^{\lfloor(u+1)(r-s)\log_{10}2\rfloor}$

Conclusion

We have found that we can get a power of two starting with the sequence of digits we want, though we haven’t found any bounds on the required exponents. In fact, the powers of two follow Benford’s law and we can use that to estimate the magnitude of the required exponent:

$\displaystyle P({\rm power\ of\ two\ starts\ with\ required\ digits}) \approx \log_{10}\left(1 + \frac{1}{3.2 \cdot 10^{40}}\right)$

$\displaystyle P({\rm power\ of\ two\ starts\ with\ required\ digits}) \approx \frac{1 + \frac{1}{3.2 \cdot 10^{40}} - 1}{\ln 10}$

$\displaystyle P({\rm power\ of\ two\ starts\ with\ required\ digits}) \approx 10^{-41}$

So we can be quite confident that an exponent smaller than $10^{43}$ should meet the requirements, though it’s obviously impossible to find it by brute force. But it should be feasible to compute values of $u$ , $r$ and $s$ and getting the first 100 digits of $2^{(u+1)(r-s)}$ .