(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
with going from 1 to 100000 and 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 starting with a given sequence of digits, . By expressing the digits sequence as a fraction between 0.1 and 1, , we can represent the desired condition by the following inequality:
As logarithms are monotonically increasing, we can apply them on both sides of the inequality:
If we assume is not a power of ten, we can translate the inequality to the fractional parts of each member:
Now the problem is reduced to see if we can find a multiple of 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 such that
Now, let’s analyze the distribution of for in the range 1, …, . As we have numbers inside the unit interval, we must have two numbers with separation less than or equal to (it’s easy to prove by contradiction). Then there are two exponents, and , such that
where we know that the inequality with zero is strict because is irrational. Then we can use the Archimedean property again to extend the inequality:
It's intuitively easy to see (and not very difficult to prove) that we must have a number such that
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:
Removing the fractional parts:
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:
So we can be quite confident that an exponent smaller than should meet the requirements, though it’s obviously impossible to find it by brute force. But it should be feasible to compute values of , and and getting the first 100 digits of .