somme de la série géométrique (mod m)

Question

J'ai une série

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

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

Je veux trouver la somme. Je ne peux pas appliquer la formule Progression Géométrique (PG) car le résultat aura alors un dénominateur et ensuite je devrai trouver l'inverse modulaire qui peut ne pas exister (si le dénominateur et m ne sont pas en coprime). J'ai donc fait un algorithme alternatif en supposant que ces puissances feraient un cycle de longueur beaucoup plus petit que k (parce que c'est une équation modulaire et donc j'obtiendrais quelque chose comme 2,7,9,1,2, 7,9,1 ....) et ce cycle se répètera dans la série ci-dessus. Donc, au lieu d'itérer de 0 à k, je trouverais simplement la somme des nombres dans un cycle, puis calculerais le nombre de cycles dans la série ci-dessus et les multiplierais. Donc, j'ai d'abord trouvé i^m (mod m) et ensuite multiplié ce nombre encore et encore en prenant modulo à chaque étape jusqu'à ce que j'atteigne à nouveau le premier élément.

Mais quand j'ai réellement codé l'algorithme, pour certaines valeurs de i, j'ai eu des cycles de très grande taille. Et donc pris beaucoup de temps avant de se terminer et donc mon hypothèse est incorrecte.

Y a-t-il un autre modèle que nous pouvons trouver? (Fondamentalement, je ne veux pas itérer sur k.) Alors s'il vous plaît donnez-moi une idée d'un algorithme efficace pour trouver la somme.

Answer 1

Comme vous l'avez noté, le calcul d'un module arbitraire m est difficile car de nombreuses valeurs peuvent ne pas avoir un mod m inverse multiplicatif. Cependant, si vous pouvez le résoudre pour un ensemble de modules alternatifs soigneusement sélectionnés, vous pouvez les combiner pour obtenir une solution mod m.

facteur m dans p_1, p_2, p_3 ... p_n de telle sorte que chaque p_i est une puissance d'un nombre premier

distinct Puisque chaque p est une puissance de choix distincts, ils sont deux à deux premiers entre eux. Si nous pouvons calculer la somme de la série par rapport à chaque module p_i, nous pouvons utiliser le Chinese Remainder Theorem pour les réassembler dans une solution mod m.

Pour chaque module d'alimentation principale, il y a deux triviales cas particuliers:

Si i^m est congru à 0 mod p_i, la somme est trivialement 0.

Si i^m est congru à 1 mod p_i, alors la somme est congruente avec k mod p_i.

Pour d'autres valeurs, on peut appliquer la formule habituelle pour la somme d'une suite géométrique:

S = somme (j = 0 à k, (i^m)^j) = ((i^m TODO: Montrer que (i^m - 1) est coprime à p_i ou trouver une solution alternative quand ils ont un GCD non trivial. Espérons que le fait que p_i est un pouvoir principal et aussi un diviseur de m sera d'une certaine utilité ... Si p_i est un diviseur de i. la condition tient. Si p_i est premier (par opposition à un pouvoir premier), alors le cas particulier i^m = 1 s'applique, ou (i^m - 1) a un inverse multiplicatif.

Si la formule de somme géométrique n'est pas utilisable pour une p_i, vous pouvez réorganiser le calcul de sorte que vous ne devez itérer 1-p_i au lieu de 1 à k, en profitant du fait que les termes répètent avec une période pas plus que p_i.

(Étant donné que votre série ne contient pas de j = 0 terme, la valeur que vous voulez est en fait S-1.)

On obtient ainsi un ensemble de congruences mod p_i, qui satisfont aux exigences du CRT. La procédure pour les combiner dans une solution mod m est décrite dans le lien ci-dessus, donc je ne vais pas le répéter ici.

Answer 2

C'est l'algorithme pour un problème similaire, je rencontrais

Vous savez probablement que l'on peut calculer la puissance d'un nombre dans le temps logarithmique. Vous pouvez également le faire pour calculer la somme des séries géométriques. Comme il estime que

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

vous pouvez récursive calculer la série géométrique sur la main droite pour obtenir le résultat. De cette façon, vous n'avez pas besoin de division, donc vous pouvez prendre le reste de la somme (et des résultats intermédiaires) modulo n'importe quel nombre que vous voulez.

Answer 3

Sur la base de l'approche de @braindoper un algorithme complet qui calcule

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

ressemble à ceci dans 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]] 
] 

Paramètres:

• a est le "rapport" de la série. Il peut s'agir de n'importe quel nombre entier (y compris des valeurs nulles et négatives).
• n est l'exposant le plus élevé de la série. Autorisés sont des entiers> = 0.
• m est le module entier = 0

Note: L'algorithme effectue une opération Mod après chaque opération arithmétique. Ceci est essentiel, si vous transcrivez cet algorithme dans un langage avec une longueur de mot limitée pour les entiers.

Answer 4

Cela peut se faire via la méthode de repeated squaring, qui est le temps O(log(k)) ou O(log(k)log(m)) temps, si l'on considère m une variable.

En général, a[n]=1+b+b^2+... b^(n-1) mod m peut être calculée en notant que:

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

La deuxième étant seulement le corollaire de la première. Dans votre cas, b=i^m peut être calculé en O(log m) temps.

Le code Python suivant implémente ceci:

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 

Ce peu de magie a une raison mathématique - l'opération sur des paires définies comme

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

est associative, et la règle 1 signifie essentiellement que :

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

La mise en équation répétée fonctionne toujours lorsque les opérations sont effectuées ssociatif. Dans ce cas, l'opérateur @ est O(log(m)), donc l'équarrissage répété prend O(log(n)log(m)).

Une façon de voir cela est que la matrice exponentiation:

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

Vous pouvez utiliser une méthode similaire pour calculer (a^n-b^n)/(a-b) modulo m car la matrice exponentiation donne:

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