Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

Your sum have this value:

$$\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.

share|improve this answer
    
When you say founded do you mean found? –  Pedro Tamaroff Apr 24 '12 at 16:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.