[ACCEPTED]-Sum of series: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)-series

Accepted answer

Score: 24

Two notes:

(a + b + c) % m

is equivalent to

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

and

(a * b * c) % m

is equivalent 4 to

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

As a result, you can calculate each term 3 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 2 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 1 is O(n log n).

Score: 5

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

Score: 3

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

Score: 1

I encountered similar question recently: my 3 'n' is 1435, 'm' is 10^10. Here is my solution 2 (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 1 number.

Score: 0

Are you getting killed here:

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

Exponentials 2 mod m could be implemented using the sum 1 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;
}

Score: 0

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

Source: stackoverflow.com

[ACCEPTED]-Sum of series: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)-series

Python: Combining Low Frequency Factors/Category Counts

Pandas pd.Series.isin performance with set versus array

How to filter strings in pandas series index

Quick way to check if the pandas series contains a negative value

Finding the intersection between two series in Pandas using index

How to extract hour, minute and second from Series filled with datetime.time values

Setting flag column depending on whether column contains a given string

Splitting pandas dataframe column (into two) after the first letter in the cell

Dask item assignment. Cannot use loc for item assignment

How to extract values from pandas Series without index