Encontrar el mínimo de $q$.

Question

Dado $\displaystyle p,q\in\mathbb N, \frac p q=0.123456789...$(es decir, los primeros 9 dígitos después del punto decimal se $123456789$). Encontrar el mínimo de $q$.

He adivinado la respuesta a la se $111111111$$\displaystyle\frac {123456789} {999999999}=0.\dot{1}2345678\dot{9}$, pero no estoy seguro.

Gracias.

Answer 1

El más pequeño $q$ $q=10989019$ correspondiente a $$\frac pq=\frac{1356669}{10989019}=0.12345678900000081899940294943524986\ldots$$ Para ver esto, observe que $$ \frac ab=\frac{1356659}{10988938}=0.1234567889999925379504370668029977\ldots$$ es demasiado pequeño y $$\frac cd=\frac{10}{81}=0.12345679012345679012345679012345679\ldots$$ es demasiado grande. Para cualquier fracción con $\frac ab<\frac pq<\frac cd$, tenemos $$\frac pq-\frac ab=\frac{bp-aq}{bq}>0\qquad\frac cd-\frac pq=\frac{cq-dp}{dq}>0,$$ por lo tanto $$ bp-aq\ge 1\qquad cq-dp\ge 1$$ y por último (porque $bc-ad=1$) $$ q=(bc-ad)q=d(bp-aq)+b(cq-dp)\ge b+d=10989019.$$

Answer 2

Aquí está la magia algoritmo que Hagen von Eitzen utiliza para calcular la respuesta. Este método es muy elegante, y se deriva de Farey secuencias.

Para acortar la computación, voy a resolver los otros análogos cuestión de encontrar el más mínimo $q$ tal que $\frac{p}{q}$ tiene decimal de expansión $.789....$.

Deje $\alpha = \frac{789}{1000}$; estamos buscando números racionales cerca de $\alpha$ con pequeños denominadores. (En general, $\alpha$ puede ser cualquier número real positivo.)

Comience con los dos fracciones $\frac01$$\frac10$. Tenga en cuenta que $\frac01 < \alpha < \frac10$. Suma los numeradores y agregar los denominadores para obtener la fracción $\frac{0 + 1}{1 + 0} = \frac11$. De las tres fracciones que hemos enumerado hasta ahora ( $\frac01, \frac11,$ $\frac10$ ), las dos que están a cada lado de $\alpha$, es decir,$\frac01$$\frac11$.

Tenemos a los dos fracciones $\frac01$$\frac11$,$\frac01 < \alpha < \frac11$. Suma los numeradores y denominadores para obtener $\frac{0 + 1}{1 + 1} = \frac12$. De las tres fracciones $\frac01$, $\frac12$, y $\frac11$, $\alpha$ se entre $\frac12$$\frac11$, así que estos dos.

Tenemos a los dos fracciones $\frac12$$\frac11$. Suma los numeradores y denominadores para obtener $\frac{1 + 1}{2 + 1} = \frac23$. De las tres fracciones $\frac12$, $\frac23$, $\frac11$, $\alpha$ es entre $\frac23$ $\frac11$ , así que estos dos.

Usted puede ver a dónde va esto. A continuación recogemos los pares de fracciones $\frac34$$\frac11$,$\frac34$$\frac45$,$\frac79$$\frac45$,$\frac{11}{14}$$\frac45$,$\frac{15}{19}$$\frac{4}{5}$. Nos detenemos porque $\frac{15}{19}$ tiene decimal de expansión $.789....$ (es la primera de las fracciones que hemos enumerado). Esta es la respuesta. No importa qué decimal de expansión desea ($.123456789$ en su caso), este método siempre , finalmente, darle la fration $\frac{p}{q}$ con un mínimo de $q$.