CODEWITHSUNDEEP
algorithmseries
rahul
rahul

Reputation:

Sum of series: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)

Can someone give me an idea of an efficient algorithm for large n (say 10^10) to find the sum of above series?

Mycode is getting klilled for n= 100000 and m=200000

#include<stdio.h>

int main() {
    int n,m,i,j,sum,t;
    scanf("%d%d",&n,&m);
    sum=0;
    for(i=1;i<=n;i++) {
        t=1;
        for(j=1;j<=i;j++)
            t=((long long)t*i)%m;
        sum=(sum+t)%m;
    }
    printf("%d\n",sum);

}

Upvotes: 8

Views: 34529

Answers (6)

Rail Suleymanov
Rail Suleymanov

Reputation: 359

I encountered similar question recently: my 'n' is 1435, 'm' is 10^10. Here is my solution (C#):

ulong n = 1435, s = 0, mod = 0;
mod = ulong.Parse(Math.Pow(10, 10).ToString());
for (ulong i = 1; i <= n; 
{
     ulong summand = i;
     for (ulong j = 2; j <= i; j++)
     {
         summand *= i;
         summand = summand % mod;
     }
     s += summand;
     s = s % mod;
}

At the end 's' is equal to required number.

Upvotes: 1

Jaska
Jaska

Reputation: 775

I can't add comment, but for the Chinese remainder theorem, see http://mathworld.wolfram.com/ChineseRemainderTheorem.html formulas (4)-(6).

Upvotes: 0

Calyth
Calyth

Reputation: 1673

Are you getting killed here:

for(j=1;j<=i;j++)
    t=((long long)t*i)%m;

Exponentials mod m could be implemented using the sum of squares method.

n = 10000;
m = 20000;
sqr = n;
bit = n;
sum = 0;

while(bit > 0)
{
    if(bit % 2 == 1)
    {
        sum += sqr;
    }
    sqr = (sqr * sqr) % m;
    bit >>= 2;
}

Upvotes: 0

Jaska
Jaska

Reputation:

I think you can use Euler's theorem to avoid some exponentation, as phi(200000)=80000. Chinese remainder theorem might also help as it reduces the modulo.

Upvotes: 5

Mehrdad Afshari
Mehrdad Afshari

Reputation: 422132

Two notes:

(a + b + c) % m

is equivalent to 

(a % m + b % m + c % m) % m

and

(a * b * c) % m

is equivalent to

((a % m) * (b % m) * (c % m)) % m

As a result, you can calculate each term using a recursive function in O(log p):

int expmod(int n, int p, int m) {
   if (p == 0) return 1;
   int nm = n % m;
   long long r = expmod(nm, p / 2, m);
   r = (r * r) % m;
   if (p % 2 == 0) return r;
   return (r * nm) % m;
}

And sum elements using a for loop:

long long r = 0;
for (int i = 1; i <= n; ++i)
    r = (r + expmod(i, i, m)) % m;

This algorithm is O(n log n).

Upvotes: 24

user172818
user172818

Reputation: 4754

You may have a look at my answer to this post. The implementation there is slightly buggy, but the idea is there. The key strategy is to find x such that n^(x-1)<m and n^x>m and repeatedly reduce n^n%m to (n^x%m)^(n/x)*n^(n%x)%m. I am sure this strategy works.

Upvotes: 3

Related Questions