5
$\begingroup$

From the problem...

Find the minimal positive integer $b$ such that the first digits of $2^b$ are 2011

...I have been able to reduce the problem to the following instead:

Find minimal $b$ such that $\log_{10} (2.011) \leq \operatorname{frac}(b~\log_{10} (2)) < \log_{10} (2.012)$, where $b$ is a positive integer

Is there an algorithm that can be applied to solve this or would you need to step through all possible b until you find the right solution?

  • 0
    Usin$g $continued fractions is convenient only with computation anyway, and with computation, using continued fractions gives faster solutions. (E.g. if instead of "2011" we wanted a power of 2 that begins with a longer string like "12345678", then brute force would not be fast enough.)2011-06-19

3 Answers 3

5

This is an elaboration of Gerry Myerson's answer (and user6312's comment).

As you derived, we want to find an integer $b$ such that for some integer $k$, $(2.011)10^k < 2^b < (2.012)10^k$ which, taking logarithms to base 10 etc., is equivalent to ($\{x\}$ denotes the fractional part of $x$): $\log_{10}{2.011} < \{b~\log_{10}{2}\} < \log_{10}{2.012}.$

Because $\log_{10}{2}$ is irrational, the sequence $\{b~\log_{10}{2}\}$ (for $b$ varying over positive integers) is dense in $[0,1]$, so you are guaranteed that there are infinitely many $b$ for which $\{b~\log_{10}{2}\}$ lies in the interval $(\log_{10}2.011, \log_{10}2.012)$. In fact, the sequence is also uniformly distributed in the unit interval, so that $\log_{10}2.012 - \log_{10}2.011 \approx 0.0002159$ is the fraction of integers with this property, and indeed a computer search finds 21 such integers in the first 100000 and 216 in the first 1000000.

Given an irrational number $\theta$, issues about making $\{q\theta\}$ close to $0$ (for integer $q$) are called homogeneous diophantine approximation; making it close to some arbitrary number $\alpha$ is called inhomogeneous diophantine approximation, which is what we have here.

Here is one way, possibly not the simplest, to find such $q$ (based on Module 16 of Edward Burger's Exploring the Number Jungle, a great book):

  • Using the continued fraction of $\theta$ etc., find relatively prime integers $m$ and $n$ such that $|\theta n - m| < \frac1n$.

  • Let $N$ be the closest integer to $\alpha n$ (so that $|\alpha n - N| \le \frac12$).

  • Write $N$ as $vm - un$ with $|v| \leq \frac{n}2$ (using Euclidean algorithm etc.)

  • Then, for $q = n + v$ and $p = m + u$, we have $ |\theta q - p - \alpha| < \frac{3}{q} $

Proving all this (after the first step) is just some elementary algebra. For our problem with $\theta = \log_{10}2$ and $\alpha = \log_{10}2.011$, the first convergent that is good enough is $m/n = 643/2136$. Then $N$ is the closest integer to $n\alpha = 2136\alpha$ so $N = 648$. We write it as $N = v(643) - u(2136)$ with $v = -288$ and $u = -87$. So $q = n + v = 2136 - 288 = 1848$ and $p = m + u = 643 - 87 = 556$. And indeed, we have $1848\log_{10}2 \approx 556.30343$ and its fractional part lies between $\log_{10}{2.011} \approx 0.30341$ and $\log_{10}{2.012} \approx 0.30363$.

  • 0
    @Sp3000: BTW, if you take $v$ which does not satisfy $|v| \le n/2$, then you won't get $3$ but instead (I think) something like $2 + \frac{2|v|}{n}$, so if $q$ is large enough it can still be ok. In fact, I guess this is how the other solutions (not given by the algorithm above) are generated.2011-06-19
2

Here is a shotgun way to do it. This is not elegant, but it worked.

def foo(x):     x = str(x)     if len(x) < 4:         return x     return x[:4] for k in range(1,10000):     q = 2**k     q = foo(q)     if foo(q) == "2011":         print k 

I got 1848, 3984, 6120 in this little search. So your first integer is 1848.

  • 0
    I realised that you could probably brute force the problem but I was more interested in any heuristics for the general problem of "find minimal $b$ such that $a^b$ starts with $n$". That is why I tried to work with logs and a precision library instead of strings, but I'm not too sure which method would be faster.2011-06-19
2

You are looking for integers $b$ and $p$ such that $b\log_{10}2-\log_{10}(2.011)-p$ is small and positive. The general study of such things is called "inhomogeneous diophantine approximation," which search term should get you started, if you want something more analytical than a brute force search. As 6312 indicated, continued fractions come into it.

  • 0
    @WAS: That is true, but the question is whether 1848 being the same as the answer to the question (see ncmathsadist's answer) is a coincidence or not.2011-06-19