Gracias por el A2A.
Sea [math] k = 10n + t [/ math] el divisor de interés. Estamos produciendo alguna secuencia [matemática] N_0, N_1, N_2, \ ldots [/ math]. Nos gustaría saber que:
1.) El algoritmo se detiene: la secuencia termina en algún término finito [math] N_l [/ math].
2.) [matemática] N_0 \ equiv 0 \ mod k [/ matemática] si y solo si [matemática] N_l \ equiv 0 \ mod k [/ matemática].
Estos dos hechos juntos probarían que este algoritmo funciona. Vamos a demostrar algo un poco más fuerte:
- ¿Por qué [math] 2 ^ {- 149} [/ math] es el espacio normalizado más pequeño en el formato de precisión simple IEEE 754?
- ¿Cuál es el resto cuando 48 ^ 46 se divide por 49 ^ 2?
- Cómo determinar si una ecuación lineal de diofantina se puede resolver sobre enteros no negativos
- ¿Existe la transformada de Laplace de 1 / t?
- Cómo contar el número de posibilidades de separar una cadena de n caracteres i veces
2. *) [matemática] N_i \ equiv 0 \ mod k [/ matemática] si y solo si [matemática] N_ {i + 1} \ equiv 0 \ mod k [/ matemática].
Reduzcamos el algoritmo a lo esencial. Tenemos un número entero fijo [math] d_k [/ math], que determinaremos más adelante. (Esto es lo que llamas el SN. Me doy cuenta de que en algunos de tus ejemplos lo tienes como medio entero; en realidad no importa demasiado. Si lo revisas, todo debería funcionar esencialmente como lo describo aquí , excepto que se habrá movido un factor de 2).
En cada paso, tomamos nuestro número entero [math] N_i [/ math] y lo escribimos como [math] N_i = qk + r [/ math], donde [math] q [/ math] y [math] r [/ matemáticas] son enteros. Tenemos:
[matemáticas] N_i = q (10n + t) + r = 10nq + (tq + r) = 10 (nq + m) + (tq + r – 10m) [/ matemáticas]
El factor de [matemática] 10m [/ matemática] que se suma y resta en el último paso se elige de modo que [matemática] 0 \ leq tq + r – 10m <10 [/ matemática]. Sorprendentemente, es casi irrelevante para lo que viene después. El siguiente término en la secuencia estará dado por:
[matemáticas] N_ {i + 1} = nq + m + d_k (tq + r – 10m) = q (n + td_k) + m (1 – 10d_k) + d_k r [/ matemáticas]
Ahora, observe que los coeficientes [math] n + td_k [/ math] y [math] 1 – 10d_k [/ math] no dependen en absoluto de la secuencia de [math] N_i [/ math]. Esto debería indicarnos que estas son las cosas con las que deberíamos jugar.
Específicamente, vamos a elegir [math] d_k [/ math] tal que:
[matemáticas] n + td_k \ equiv 0 \ mod k [/ matemáticas]
[matemáticas] 1 – 10d_k \ equiv 0 \ mod k [/ matemáticas]
¿Es esto posible? Es, siempre y cuando [math] k [/ math] y [math] 10 [/ math] sean coprime, en otras palabras, [math] t = 1, 3, 7, \ text {or} 9 [/ math ] Bajo tales condiciones, tenemos de la segunda ecuación que [math] d_k \ equiv 10 ^ {- 1} \ mod k [/ math], por lo tanto:
[matemáticas] n + td_k \ equiv n + t 10 ^ {- 1} \ equiv 10 ^ {- 1} (10n + t) \ equiv 10 ^ {- 1} k \ equiv 0 \ mod k [/ matemáticas]
¿Cómo ayuda esto? Bueno, recuerda que hemos escrito:
[matemáticas] N_i = qk + r [/ matemáticas]
[matemáticas] N_ {i + 1} = q (n + td_k) + m (1 – 10d_k) + d_k r [/ matemáticas]
Ahora, reducimos el módulo [math] k [/ math]:
[matemáticas] N_i \ equiv r \ mod k [/ matemáticas]
[matemáticas] N_ {i + 1} \ equiv d_k r \ mod k [/ matemáticas]
Como [math] d_k \ equiv 10 ^ {- 1} \ mod k [/ math], [math] r \ equiv 0 [/ math] si y solo si [math] d_k r \ equiv 0 [/ math].
Todo lo que queda es especificar cuándo termina el algoritmo. Esto va a estar relacionado con la pregunta de cuándo [matemáticas] N_i> N_ {i + 1} [/ matemáticas]. Un poco de reflexión muestra que esto está garantizado siempre que [math] N_i> 10 d_k [/ math].
Entonces, especificaremos que el algoritmo se detiene una vez [math] N_ {i + 1} \ leq 10 d_k [/ math]. Y ahora hemos terminado, porque sabemos que obtendremos alguna secuencia [matemática] N_0> N_1> N_2> \ ldots [/ matemática] de enteros, y dado que solo hay muchos enteros finitos menos que [matemática] N_0 [/ matemática ] y mayor que [math] 10 d_k [/ math], esta secuencia es finita. El algoritmo se detiene.
Así que eso es, por eso funciona este método. En cuanto a que es nuevo … bueno, ciertamente no lo he visto antes. Me recuerda mucho a la regla de divisibilidad para 9 y al algoritmo euclidiano. Desafortunadamente, es mucho menos eficiente que cualquiera de esos métodos. Esta no es una forma rápida de verificar si un número divide a otro. Eso no quiere decir que no haya preguntas interesantes que puedas hacer sobre este algoritmo … pero ¿no es siempre así?
Por lo que vale, me gusta un poco. Es una demostración clara de la aritmética de congruencia, y es un algoritmo que es fácil de hacer a mano. Es algo estéticamente agradable en ese sentido.