¿Cómo se calcula cuántos decimales hay antes de las cifras que se repiten, dada una fracción que se expande a un decimal que se repite?

Question

Si tiene una fracción como $$\frac{7}{26}=0.269230\overline{769230}$$ donde hay un número de dígitos antes de la sección de repetición, ¿cómo se puede saber cuántos dígitos habrá dada sólo la fracción?

Creo que podría seguir el algoritmo estándar de la división larga hasta encontrar el mismo resto por segunda vez y luego utilizar la ubicación de la primera instancia de este resto para calcular el número de dígitos antes de la sección de repetición, pero esto parece muy engorroso.

Después de mucho leer en Internet, me encontré con lo que parece ser una fórmula para ello de Wolfram MathWorld :

Cuando un número racional $\frac{m}{n}$ con $(m,n)=1$ se amplía, el período comienza después de ${s}$ y tiene una longitud ${t}$ donde ${s}$ y ${t}$ son los números más pequeños que satisfacen $10^s\equiv10^{s+t}\pmod{n}$ .

Sé cómo calcular la longitud del período de una fracción, y así en el caso de mi fracción original tenemos $10^s\equiv10^{s+6}\pmod{26}$ pero no sé cómo resolver para ${s}$ ¡en esta ecuación!

Así que en realidad hay dos preguntas aquí: la del título y una solapada sobre cómo tomar logaritmos en una ecuación aritmética módulo.

Answer 1

Reescribe la fracción como $$\frac{m}{n}=\frac{p}{10^sq}$$ donde $p,q$ son coprimos y $q$ no es divisible por $2$ o $5$ mientras que $p$ no es divisible por $10$ . Informática $s$ (el período previo) es fácil; es el mayor de los números de veces $2$ divide $n$ y el número de veces $5$ divide $n$ . Entonces queremos el más pequeño $t$ tal que $10^t\equiv 1\;(\bmod\;q)$ . Por el pequeño teorema de Fermat, tenemos $10^{\varphi(q)}\equiv 1\;(\bmod\;q)$ Así pues $\;t|\varphi(q)$ por lo que basta con comprobar los divisores de $\varphi(q)$ .

Answer 2

Los ordenadores están hechos para ser "engorrosos". Aquí es un algoritmo que convertí en un programa python para hacer algo similar para el Proyecto Euler 26.

Answer 3

En el $2^{nd}$ de esta respuesta obtenemos la respuesta utilizando el instituto que mencionaba el OP, pero que rechazó por ser demasiado engorroso. Pero estudiando la teoría que hay detrás del algoritmo y utilizando la teoría elemental de números, podremos entender, directamente, la teoría de wolframio sobre expansiones decimales en fórmulas/ejemplos (7) - (9) .

Para el divisor cero $[10] \in {\textstyle \mathbb {Z} /26\mathbb {Z}}$ los cálculos muestran que

$\quad x \pmod{26} \text{ where } x \in [10^0, 10^1, 10^2, 10^3, 10^4, 10^5, 10^6, 10^7] = [1, 10, 22, 12, 16, 4, 14, 10]$

El numerador $7$ de la fracción $\large \frac{7}{26}$ se traslada a una unidad, $[7] \in {\textstyle \mathbb {Z} /26\mathbb {Z}}$ .

Así que la unidad $[7]$ se "pasea" por el "gráfico exponencial" de los divisores de cero generado por $[10]$ ,

$\quad [1\cdot7,10\cdot7,\, 22\cdot7,\, 12\cdot7,\, 16\cdot7,\, 4\cdot7,\, 14\cdot7]\quad \text{(not necessary to to calculate any of these residues)}$

Conclusión: En la expansión decimal de $\large \frac{7}{26}$ el bloque repetido de dígitos es de longitud $6$ y comienza en el $2^{nd}$ dígito decimal fraccionario ( $10^7 \equiv 10^1 \pmod{26}$ ).

Una vez hecho esto, podemos obtener fácilmente la respuesta explícita: multiplicar el numerador por $10^7$ y mantener los 7 dígitos del cociente (relleno $0s$ después del punto decimal puede ser necesario) después de dividir,

$\quad 7 \cdot 10^7 = 26\cdot2692307+18$

y (tenemos los siete dígitos del cociente),

$\quad \large \frac{7}{26} \approx 0.2\overline{692307}$

El mismo patrón (1 más 6 bloque) se produce siempre que el numerador de $\large \frac{n}{26}$ satisface

$\quad 1 \le n \lt 26 \land n \text{ is odd } \land n \ne 13$

---

Análisis de la instituto algoritmo (ver algo de teoría aquí ), hay como máximo $26$ divisiones (estimación neófita) que hay que realizar. Así que ¡manos a la obra!

Ampliar $\large \frac{7}{26}$ :

Divide

Aproximado (append $q$ dígito)

$7\cdot 10 = 26 \cdot 2 + 18$

$\large \frac{7}{26} \approx 0.2$

$18\cdot 10 = 26 \cdot 6 + 24$

$\large \frac{7}{26} \approx 0.26$

$24\cdot 10 = 26 \cdot 9 + 6$

$\large \frac{7}{26} \approx 0.269$

$6\cdot 10 = 26 \cdot 2 + 8$

$\large \frac{7}{26} \approx 0.2692$

$8\cdot 10 = 26 \cdot 3 + 2$

$\large \frac{7}{26} \approx0.26923$

$2\cdot 10 = 26 \cdot 0 + 20$

$\large \frac{7}{26} \approx 0.269230$

$20\cdot 10 = 26 \cdot 7 + 18$

$\large \frac{7}{26} \approx 0.2692307$

Ahora el residuo $18$ ya ha aparecido y se ha utilizado después de calcular el primer decimal fraccionario; la respuesta se resume como sigue:

$\quad \large \frac{7}{26} \approx 0.2\overline{692307}$