# How to solve this problem?

I want to solve this problem, but I'm stuck. Can anyone can help me out?

$$S = \left(\sum_{k=1}^N k^xx^k\right)\bmod M$$

How can I find $S$ if $N$ , $M$ and $x$ are given. Also, $1 ≤ N$, $M ≤ 2·10^9$ and $1 ≤ x ≤ 50$.

Thanks.

-
Maybe you should give $k$? It seems that $x$ is varying... –  Yuchen Liu Apr 24 '12 at 7:52
Do you mean $k=1$ in the subscript? –  anon Apr 24 '12 at 7:54
I reedit problem. –  Elmi Ahmadov Apr 24 '12 at 8:01

$$\sum_{k=1}^N k^xx^k=\text{Li}_{-x}(x)-x^{N+1} \Phi (x,-x,N+1)$$

where $\Phi (x,y,z)$ is the Lerch Transcendent function and $\text{Li}_x(y)$ is the Polylogarithm function (found by Mathematica).

So, to find S, you just need compute:

$$S=\text{Li}_{-x}(x)-x^{N+1} \Phi (x,-x,N+1) \mod M$$

Example:

$x=32,N=153,M=217$

$S=\text{Li}_{-32}(32)-(32)^{153+1} \Phi (32,-32,153+1) \mod 217=$

1618887402645091569139560124883099530302801907743763661965533026655621 1234532441977373355549440532216161925108618699304271249590709705266275 6496708627677925911448742482749243246235165958155955647381434616274989 4284867394970351259385987107024392969700273376561757822645414989646045 454218392408692916256 $\mod 217=185$

But probably, you will have problems with high values, you will need programs who can manipulate extremly large numbers. But if you aren't interested in math, but about to compute the result, you can find the value of the modular operation step by step in the sum.

-
When you say founded do you mean found? –  Pedro Tamaroff Apr 24 '12 at 16:19