División de enteros: la longitud de la secuencia repetitiva después del punto decimal

Question

Al dividir dos números enteros, puede haber una secuencia infinita de dígitos después del punto decimal (por ejemplo, en los casos de 1/3, 1/7, etc).

Hasta donde yo sé, si los dos números separados son enteros, esta secuencia infinita será, a partir de cierto punto, la repetición de una cierta secuencia finita (esto puede ser cierto también para dividir números racionales y no sólo números enteros, pero me estoy guardando simple por ahora).

Tomemos, por ejemplo, 1/7, es igual a la 0.14285714285714285714285714285714...

La secuencia se repite es 142857, una secuencia de longitud 6.

Otro ejemplo es 1/31, que es igual a 0.032258064516129032258064516129032...

La secuencia se repite es 032258064516129, una secuencia de longitud 15.

Algunas divisiones no comenzar inmediatamente con la repetición de la secuencia, por ejemplo, 3/14 que equivale a 0.21428571428571428571428571428571... (a partir de 2, a continuación, seguido por repeticiones de 142857, una secuencia de longitud 6).

Finalmente, después de este largo discurso, aquí viene una pregunta que me molesta mucho tiempo: es posible encontrar la longitud de la secuencia de repetición usando los 2 números que se están divididos?

Estoy buscando una función que recibe un numerador y un denominador como parámetros y devuelve la longitud de la secuencia repetitiva. Ejemplos de entrada+salida:

F(1,7) = 6
F(1,31) = 15
F(3,14) = 6
F(1,3) = 1

¿Alguien sabe si esto es posible? Y si es así, ¿cómo lograrlo?

Answer 1

Si m, n son primos relativos, entonces F(m, n) sólo depende de n. (Pero con la condición de que m, n son relativamente materias primas; considerar la posibilidad de que F(7, 21) = 1.) Sea g(n) = F(1, n), y vamos a calcular g(n).

A su vez, dejar que n = p1^(a1) p2^(a2) ... pk^(ak), donde los pi son distintos de los números primos. Entonces g(n) es el mínimo común múltiplo de g(p1^(a1)) , g(p2^(a2)), ..., g(pk^(ak)). Por ejemplo g(11) = 2, ya que 1/11 = .090909...; g(41) = 5, ya que 1/41 = 0.0243902439...; ir g(451) = 10.

Esta página web explica la teoría general, y este se explica cómo se pueden calcular g(n) cuando n es una potencia principal.

Answer 2

La duración del período de una fracción es indiferente para el numerador menos el numerador y el denominador no son en términos mínimos (en cuyo caso, reducen a aplicar el método siguiente).
Sin embargo, cuando ellos son en términos mínimos, tomar el denominador y el factor de salida de todos los factores de la base en el que estamos, ya que no cambian nada (como 2s y 5s en base 10, 3 y 7 en la base 21, etc). Entonces, la longitud del período es igual a n, donde n es el entero más pequeño tal que el denominador se divide bⁿ-1 (donde b es la base). Así, por ejemplo, 1/7 = 0.142857... y el más pequeño de 10ⁿ-1 tal que 7 es un factor que es 7 es 10⁶-1 = 999999, y 999999/7 = 142857, que es, por cierto, su repetición de parte. La misma cosa, incluso obras, por ejemplo, 1/2 -- el más pequeño de n es 0, porque 10⁰ - 1 = 0, y todos los no-cero enteros se dividen 0. Este es uno de los métodos de factorización repunits. Tenga en cuenta que n será siempre ser menor que el denominador.
Del mismo modo, 1/14₇ (que es 1/11 en base 10) = 0.0431162355..., y el menor n tal que 7ⁿ-1 es un múltiplo de 11 es 10 (7^{de 10} - 1 = 282475248, y 282475248 / 11 = 25679568).

Multiplicar por una constante no hace nada para cambiar el período, a pesar de que va a cambiar los números por sí mismos. Curiosamente, sin embargo, cuando el período de n es igual a 1 menos que el denominador (el llamado "max" periódico de longitud), de multiplicar la fracción por una constante (aparte de un múltiplo del denominador en sí) va a producir, en realidad, un ciclo de la época. 2/7 = 0.285714..., 3/7 = 0.428571..., 4/7 = 0.571428..., etc.

Edit: Cuando se divide por factores de la base de que todo el número por el cual se divide ser f. A continuación, $\lceil \log_{base}f\rceil$ (techo de la función) es igual al número de no-repetición de los lugares antes de la repetición de parte de la decimal. Por lo tanto, 1/6, dividido por 2, los rendimientos de 1/3 (1/6 tiene la misma repetición de longitud 1/3), y la hemos dividido por 2. $\lceil\log_{10}2\rceil$ = 1, y, de hecho, 1/6 = 1.1(6...), con 1 que no se repiten decimal.
Además, para la fracción m/n, $\lfloor\log_{base}n\rfloor$ es el número de ceros a la izquierda en la repetición de parte de la decimal.

Answer 3

El k-ésimo dígito de la expansión decimal de a/b es determinado por el valor de a*10^k modulo b. Específicamente, el k-ésimo dígito es igual al número de veces que b divide a 10*(resto al dividir un*10^k por b).

Como empezar el aumento de k, a*10^k ejecuta a través de los distintos valores de Z/b. Finalmente, se tiene que caer en un ciclo infinito, y la duración de ese ciclo es F(a,b).

Supongamos por un momento que a=1. Entonces F(1,b) es la multiplicación de la orden de 10 modulo b. Es decir, es el menor número n tal que 10^k+n=10^k (modulo b) para valores grandes de k (I toma valores grandes de k, ya que el 10 no puede ser una unidad de modulo b ... si te gusta pensar de esa manera, esto es, esencialmente, a deshacerse de la no-repetición de dígitos en el principio).

Si a≠1, entonces usted tiene que calcular el orden de la multiplicación por 10 en el subgrupo de Z/b generado por una.

No sé de ninguna forma se pueden calcular estas órdenes. El simple hecho de hacerlo es casi tan duro como acaba de hacer la división, excepto que usted no mantiene un seguimiento de los cocientes, sólo los restos.

Answer 4

Dividir números racionales es equivalente a dividir números enteros.

Un bastante buen resultado que se conoce acerca de cómo es de grande el período (orden) puede ser. Carmichael del teorema afirma que el orden siempre divide una cierta función del $\lambda(b)$ que se puede calcular rápidamente dada la descomposición en factores primos de a $b$, y este resultado es el mejor posible en el sentido de que para cada b existe una base relativa a que el período de $\frac{1}{b}$ es exactamente $\lambda(b)$. $\lambda$ está determinado por las propiedades siguientes:

• Si $b = p^k$ es una potencia de un extraño prime, $\lambda(b) = (p-1) p^{k-1}$.
• Si $b = 1, 2, 4$,$\lambda(b) = 1, 1, 2$. Si $b = 2^k$ $k \ge 3$, $\lambda(b) = 2^{k-2}$.
• Si $b, b'$ son relativamente primos, a continuación,$\lambda(b b') = \text{lcm}(\lambda(b), \lambda(b'))$. Por ejemplo, $\lambda(21) = \text{lcm}(2, 6) = 6$.

Si estás interesado en estas ideas, es posible que quieras comenzar con el más simple de Fermat poco teorema o la totient teorema.