¿Cómo podría simplificar
ps
Dado que sólo hay$$2^x\mod 10^9$ posibles valores mod$10^9$, en algún lugar el patrón debe repetirse. Podría tener un programa de computadora trudge a través de él, pero estoy tratando de almacenar potencialmente 10 mil millones de valores y supongo que hay una manera más fácil. Necesito poder calcular esto para valores de$10^9$ tan bajo como$x$ y valores demasiado altos para ser almacenados efectivamente. No puedo usar el teorema de Euler desde$3$.
Suponiendo que usted está lanzando un equipo en el problema:
El truco para encontrar la longitud del ciclo relativamente rápidamente sin necesidad de utilizar una gran cantidad de memoria es calcular dossecuencias: $$ a_n = 2^n\bmod 10^9 \qquad \qquad b_n = 2^{2n} \bmod 10^9 = 4^n \bmod 10^9 $$ Entonces, cuando usted encuentra un $n\ge 1$ tal que $a_n=b_n$, ha encontrado un valor que sin duda está en el ciclo, y la búsqueda de la longitud del ciclo es entonces sólo una cuestión de recorrer desde allí hasta llegar de nuevo al punto de partida.
Después de que usted haya encontrado la duración del período $N$ se puede determinar la longitud de la parte inicial de la sqequence antes de entrar en el ciclo de calcular sucesivamente $$ a_n = 2^n \bmod 10^9 \qquad \qquad c_n = 2^{N+n} \bmod 10^9 $$ Luego la primera a la $n$ tal que $a_n=c_n$ es el índice donde la primera repetición de la menstruación.
La mayor potencia de$2$ que divide$10^9$ es$2^9=512$. A partir de ahí tenemos$$ 2^{9+n} \bmod 10^9 = 2^9\left(2^n \bmod \frac{10^9}{2^9}\right) $ $ La secuencia$2^n \bmod 5^9$ satisface las condiciones para aplicar el Teorema de Euler; Encontramos que tiene el período$\varphi(5^9)=4\cdot 5^8=1562500$. (Aunque en realidad no es trivial que el período no sea un divisor de este - vea el teorema de Carmichael ).
Así que obtenemos $ 2 ^ n \ bmod 10 ^ 9 = \begin{cases} 2^n \bmod 10^9 & n < 1562509 \\ 2^{((n-9)\bmod 1562500)+9} \bmod 10^9 & n \ge 1562509 \end {casos} $$
La periodicidad con un ciclo de longitud n en el desplazamiento de m puede ser expresada por $$ 2^{m+n}-2^m \equiv 0 \pmod {10^9 } \tag 1 $$ Entonces podemos proceder $$ \begin{eqnarray} 2^m ( 2^n - 1 ) &\equiv &0 \pmod{10^9} \tag {2.1} \\ 2^m ( 2^n - 1 ) &= &k \cdot 2^9 \cdot 5^9 & \to m=9 \\ 2^9 ( 2^n - 1 ) &= &k \cdot 2^9 \cdot 5^9 \\ ( 2^n - 1 ) &= &k \cdot 5^9 \tag {2.2} \end{eqnarray}$$ En general, tenemos los poderes de 5 en $2^n-1$ por $$ \{2^n-1,5\}= \underset{4}{\desbordado{n}{\sim}} \cdot \left(1+\{n,5 \} \right) \etiqueta 3 $$ donde
Así que para tener el lado derecho de (3) en por lo menos 9, n debe ser divisible por 4 y también debe contener 5 para la alimentación de 8, por lo $n = j \cdot 4 \cdot 5^8 $ con $j \gt 0$ y $$ 2^9(2^{j \cdot 4 \cdot 5^8} -1 )\equiv 0 \pmod {10^9} $$ El ciclo de la compensación es $2^9 = 512$ y el cyclelength es $ 4\cdot 5^8= 1562500$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
