Encontrar cualquier dígito (base 10) de un número binario $2^n$

Question

Yo estaba haciendo un poco de Matemáticas / CS trabajo, y he notado un patrón en los últimos dígitos de $2^n$.

Yo estaba trabajando en Python, en caso de que alguien se está preguntando.

El último dígito es siempre uno de los 2, 4, 8, 6; y tiene un período de 4:

n = 1, str(2 ^ 1)[-1] = 2
n = 2, str(2 ^ 2)[-1] = 4
n = 3, str(2 ^ 3)[-1] = 8
n = 4, str(2 ^ 4][-1] = 6

Yo estaba interesado, así que busqué más. El penúltimo dígito también tiene un patrón que se repite, esta vez con un período de 20:

n =  2, str(2 ^  2)[-2] =  0
n =  3, str(2 ^  3)[-2] =  0
n =  4, str(2 ^  4)[-2] =  1
n =  5, str(2 ^  5)[-2] =  3
n =  6, str(2 ^  6)[-2] =  6
n =  7, str(2 ^  7)[-2] =  2
n =  8, str(2 ^  8)[-2] =  5
n =  9, str(2 ^  9)[-2] =  1
n = 10, str(2 ^ 10)[-2] =  2
n = 11, str(2 ^ 11)[-2] =  4
n = 12, str(2 ^ 12)[-2] =  9
n = 13, str(2 ^ 13)[-2] =  9
n = 14, str(2 ^ 14)[-2] =  8
n = 15, str(2 ^ 15)[-2] =  6
n = 16, str(2 ^ 16)[-2] =  3
n = 17, str(2 ^ 17)[-2] =  7
n = 18, str(2 ^ 18)[-2] =  4
n = 19, str(2 ^ 19)[-2] =  8
n = 20, str(2 ^ 20)[-2] =  7
n = 21, str(2 ^ 21)[-2] =  5

Hay una manera que puedo generalizar esto para que yo pueda encontrar en cualquier dígito de cualquier $2^n$ con la necesidad de calcular el valor de $2^n$?

Si no, hay una manera de encontrar el período del patrón, dado un índice (de la parte de atrás de la entero) a mirar?

Answer 1

La razón por la que el observador de la conducta es la periodicidad de las $n \mapsto 2^n \bmod 10$ o $n \mapsto 2^n \bmod 10^k$ fijos $k$. Esto de la wikipedia artículo, así como esta, entre otras, las matemáticas.SE de respuesta son relevantes.

Específicamente, para un entero positivo fijo $k$, $m \mapsto 2^m \bmod 10^k$ es cuasi-periódica con período de $p = \phi(5^k) = 4 \cdot 5^{k-1}$, es decir, para todos $m \geq k$, $2^m \equiv 2^{m+p} \mod 10^k$.

Así, el último dígito tiene período de $4$, el penúltimo, tiene plazo,$20$, el tercero desde el final del período de $100$ y así sucesivamente.