3
$\begingroup$

I am writing a program in which I want to make changes to make it more efficient.

What the program does is it takes three inputs $m$, $n$ and $x$ and I have to find the value of the following equation: $ 1^n+ 2^n+\cdots + m^n \mod{x} $

Is there a better way than calculating the whole value and then solving for answer? Because if $n$ and $m$ are large it takes a lot of computation time which I am trying to avoid.

  • 0
    please note I made a mistake in my answer.2012-11-17

1 Answers 1

3

If $x$ is small compared to $n$ and/or $m$ there are some good optimizations you can do:

  • Edit: This is wrong, don't do this: Replace $n$ with its remainder on division by $\varphi(x)$. this only works for the bases coprime to n, which is a good proportion so it may still be worth it to do that.. for ones that aren't coprime...

  • Use binary exponentiation.

  • Split the sum into blocks $[1^n + 2^n + ... + x^n] + [(x+1)^n + (x+2)^n + \ldots] + \ldots$ which are all equal, so you only need to compute the sum of $x$ terms rather than $m$.

If $x$ is large compared to $n$ then (as already mentioned in comments) it will be more efficient to compute the sum using a closed form polynomial (which you may need to compute before use).

  • 1
    Sorry, that only works when both $x$ and $n$ are odd. If $x$ is even and $n$ odd, then $1^n+2^n+..+x^n\equiv (\frac{x}{2})^n \pmod x$. If $x$ is divisible by $4$ and n>1, then $(\frac x 2)^n \equiv 0\pmod x$.2012-11-17