Cálculo suma de la serie geométrica (mod m)

Question

que tiene una serie

S = i^(m) + i^(2m) + ............... + i^(km) (mod m) 

0 <= i < m, k may be very large (up to 100,000,000), m <= 300000 

Quiero encontrar la suma. No puedo aplicar la fórmula de progresión geométrica (GP) porque el resultado tendrá denominador y luego tendré que encontrar la inversa modular que puede no existir (si el denominador y m no son coprimos).

Así que hice un algoritmo alternativo suponiendo que estos poderes harán un ciclo de longitud mucho menor que k (porque es una ecuación modular y obtendría algo así como 2,7,9,1,2, 7,9,1 ....) y ese ciclo se repetirá en la serie anterior. Entonces en lugar de iterar de 0 a k, simplemente encontraría la suma de números en un ciclo y luego calcularía el número de ciclos en la serie anterior y los multiplicaría. Así que primero encontré i^m (mod m) y luego multipliqué este número una y otra vez tomando módulo en cada paso hasta que alcancé el primer elemento nuevamente.

Pero cuando en realidad codifiqué el algoritmo, para algunos valores de i, obtuve ciclos que eran de gran tamaño. Y por lo tanto, me tomó una gran cantidad de tiempo antes de terminar y, por lo tanto, mi suposición es incorrecta.

¿Hay algún otro patrón que podamos descubrir? (Básicamente no quiero iterar sobre k.) Así que por favor dame una idea de un algoritmo eficiente para encontrar la suma.

Answer 1

Como habrás notado, hacer el cálculo para un módulo arbitrario m es difícil porque muchos valores pueden no tener un mod m inverso inverso. Sin embargo, si puede resolverlo para un conjunto cuidadosamente seleccionado de módulos alternativos, puede combinarlos para obtener una solución mod m.

Factor m en p_1, p_2, p_3 ... p_n tal que cada p_i es una potencia de una distinta primer

Puesto que cada p es un poder primos distintos, son primos entre sí por pares. Si podemos calcular la suma de la serie con respecto a cada módulo p_i, podemos usar el Chinese Remainder Theorem para volver a montarlos en una solución mod m.

Para cada módulo de potencia principal, hay dos casos especiales triviales:

Si i^m es congruente a 0 mod p_i, la suma es trivialmente 0.

Si i^m es congruente a 1 mod p_i, entonces la suma es congruente con k mod p_i.

Para otros valores, se puede aplicar la fórmula habitual para la suma de una secuencia geométrica:

S = suma (j = 0 a k, (i^m)^j) = ((i^m)^(k + 1) - 1)/(i^m - 1)

TODO: Demuestre que (i^m - 1) es coprime a p_i o encuentre una solución alternativa para cuando tengan un GCD no trivial. Afortunadamente, el hecho de que p_i sea una potencia principal y también un divisor de m será de alguna utilidad ... Si p_i es un divisor de i. la condición se mantiene. Si p_i es primo (en oposición a una potencia principal), entonces se aplica el caso especial i^m = 1, o (i^m - 1) tiene un inverso multiplicativo.

Si la fórmula de la suma geométrica no es utilizable para algunos p_i, que podría cambiar el cálculo por lo que sólo necesita iterar a partir del 1 al p_i en lugar de 1 a k, aprovechando el hecho de que los términos se repiten con un período no más de p_i.

(Debido a que su serie no contiene un término j = 0, el valor que desea en realidad es S-1.)

Esto produce un conjunto de congruencias mod p_i, que satisfacen los requisitos de la CRT. El procedimiento para combinarlos en una solución mod m se describe en el enlace anterior, por lo que no lo repetiré aquí.

Answer 2

Este es el algoritmo para un problema similar me encontré

Usted probablemente sabe que se puede calcular la potencia de un número en el tiempo logarítmica. También puede hacerlo para calcular la suma de la serie geométrica. Dado que contiene que

1 + a + a^2 + ... + a^(2*n+1) = (1 + a) * (1 + (a^2) + (a^2)^2 + ... + (a^2)^n), 

puede calcular recursivamente la serie geométrica en la mano derecha para obtener el resultado.

De esta manera no necesita división, por lo que puede tomar el resto de la suma (y de los resultados intermedios) del módulo de cualquier número que desee.

Answer 3

Basado en el enfoque de @braindoper un algoritmo completo que calcula

1 + a + a^2 + ... +a^n mod m 

tiene este aspecto en Mathematica:

geometricSeriesMod[a_, n_, m_] := 
    Module[ {q = a, exp = n, factor = 1, sum = 0, temp}, 

    While[And[exp > 0, q != 0], 
    If[EvenQ[exp], 
     temp = Mod[factor*PowerMod[q, exp, m], m]; 
     sum = Mod[sum + temp, m]; 
     exp--]; 
    factor = Mod[Mod[1 + q, m]*factor, m]; 
    q = Mod[q*q, m]; 
    exp = Floor[ exp /2]; 
    ]; 

    Return [Mod[sum + factor, m]] 
] 

Parámetros:

• a es la "relación" de la serie. Puede ser cualquier número entero (incluidos valores cero y negativos).
• n es el máximo exponente de la serie. Permitidos son números enteros> = 0.
• m es el módulo entero = 0

Nota: El algoritmo lleva a cabo una operación después de la MOD cada operación aritmética. Esto es esencial si transcribe este algoritmo a un lenguaje con una longitud de palabra limitada para enteros.

Answer 4

Esto se puede hacer mediante el método de repeated squaring, que es O(log(k)) tiempo, o O(log(k)log(m)) tiempo, si se tiene en cuenta una variable m.

En general, a[n]=1+b+b^2+... b^(n-1) mod m se puede calcular observando que:

1. a[j+k]==b^{j}a[k]+a[j]
2. a[2n]==(b^n+1)a[n]

La segunda ser sólo el corolario para la primera.

En su caso, b=i^m se puede calcular en O(log m) tiempo.

El siguiente código Python implementa esto:

def geometric(n,b,m): 
    T=1 
    e=b%m 
    total = 0 
    while n>0: 
     if n&1==1: 
      total = (e*total + T)%m 
     T = ((e+1)*T)%m 
     e = (e*e)%m 
     n = n/2 
     //print '{} {} {}'.format(total,T,e) 
    return total 

Este poco de magia tiene una razón matemática - la operación en pares definido como

(a,r)@(b,s)=(ab,as+r) 

es asociativo, y la regla de 1 significa, básicamente, que :

(b,1)@(b,1)@... n times ... @(b,1)=(b^n,1+b+b^2+...+b^(n-1)) 

repitió la cuadratura siempre funciona cuando las operaciones son una ssociative. En este caso, el operador @ es O(log(m)) vez, por lo que la cuadratura repetida toma O(log(n)log(m)).

Una forma de ver esto es que la exponenciación matriz:

[[b,1],[0,1]]^n == [[b^n,1+b+...+b^(n-1))],[0,1]] 

Usted puede utilizar un método similar para calcular (a^n-b^n)/(a-b) módulo m porque exponenciación matriz da:

[[b,1],[0,a]]^n == [[b^n,a^(n-1)+a^(n-2)b+...+ab^(n-2)+b^(n-1)],[0,a^n]]