Parte fraccional de $b \log a$

Question

Del problema...

Encontrar el mínimo entero positivo $b$ tal que los primeros dígitos de $2^b$ 2011

... He podido reducir el problema a la siguiente en su lugar:

Encontrar un mínimo $b$ tal que $\log_{10} (2.011) \leq \operatorname{frac}(b~\log_{10} (2)) < \log_{10} (2.012)$, donde $b$ es un número entero positivo

¿Hay un algoritmo que puede ser aplicado para resolver esto o necesitas a paso a través de todos los b posibles hasta encontrar la solución correcta?

Answer 1

Esta es una elaboración de Gerry Myerson la respuesta (y user6312 del comentario).

Como usted derivados, queremos encontrar un entero $b$ tal que para algún entero $k$, $$(2.011)10^k < 2^b < (2.012)10^k$$ que, tomando logaritmos de base 10, etc., es equivalente a ($\{x\}$ denota la parte fraccionaria de $x$): $$\log_{10}{2.011} < \{b~\log_{10}{2}\} < \log_{10}{2.012}.$$

Debido a $\log_{10}{2}$ es irracional, la secuencia de $\{b~\log_{10}{2}\}$ ($b$ variación sobre los enteros positivos) es denso en $[0,1]$, por lo que se garantiza que las hay infinitamente muchos $b$ que $\{b~\log_{10}{2}\}$ se encuentra en el intervalo de $(\log_{10}2.011, \log_{10}2.012)$. De hecho, la secuencia también se distribuyen de manera uniforme en la unidad de intervalo, de modo que $\log_{10}2.012 - \log_{10}2.011 \approx 0.0002159$ es la fracción de números enteros con esta propiedad, y, de hecho, un equipo que busca el 21 de tales enteros en los primeros 100000 y 216 en el primer 1000000.

Dado un número irracional $\theta$, cuestiones sobre la fabricación de $\{q\theta\}$ cerca de $0$ (por entero $q$) se llama homogénea de diophantine aproximación; cerca de algunos de número arbitrario $\alpha$ se llama homogénea diophantine aproximación, que es lo que tenemos aquí.

Aquí es una manera, no es posiblemente la más sencilla, para encontrar como $q$ (basado en el Módulo de 16 de Edward Burger Explorando el Número de la Selva, un gran libro):

• El uso de la continuación de la fracción de $\theta$ etc., encuentra relativamente primer enteros $m$ $n$ tal que $|\theta n - m| < \frac1n$.

• Deje $N$ ser el entero más cercano a $\alpha n$ (de modo que $|\alpha n - N| \le \frac12$).

• Escribir $N$ $vm - un$ $|v| \leq \frac{n}2$ (utilizando el algoritmo de Euclides, etc.)

• Entonces, para$q = n + v$$p = m + u$, tenemos $$ |\theta q - p - \alpha| < \frac{3}{q} $$

Resultando de todo esto (después de que el primer paso) es sólo algunas de álgebra básica. Para nuestro problema con $\theta = \log_{10}2$$\alpha = \log_{10}2.011$, la primera convergente que es lo suficientemente bueno es $m/n = 643/2136$. A continuación, $N$ es el entero más cercano a$n\alpha = 2136\alpha$$N = 648$. Lo escribimos como $N = v(643) - u(2136)$$v = -288$$u = -87$. Por lo $q = n + v = 2136 - 288 = 1848$$p = m + u = 643 - 87 = 556$. Y, de hecho, tenemos $1848\log_{10}2 \approx 556.30343$ y su parte fraccionaria se encuentra entre el$\log_{10}{2.011} \approx 0.30341$$\log_{10}{2.012} \approx 0.30363$.

Answer 2

Busca números enteros $b$ y $p$ tal que $b\log_{10}2-\log_{10}(2.011)-p$ es pequeña y positiva. El estudio general de tales cosas se llama "aproximación del diophantine no homogéneo," que término de búsqueda debe ayudarle a empezar, si quieres algo más analítica que una búsqueda de fuerza bruta. Como indica 6312, fracciones continuadas entrara en él.

Answer 3

Aquí es una forma de escopeta para hacerlo. Esto no es elegante, pero funcionó.

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

Tengo 1848, 3984, 6120 en esta búsqueda poco. Así, el primer entero es de 1848.