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

share|improve this question
1  
What about wikipedia:bernoulli-polynomials , or googling for "sums-of-like-powers" ? –  Gottfried Helms Nov 17 '12 at 14:36
    
please note I made a mistake in my answer. –  sperners lemma Nov 17 '12 at 18:20

1 Answer 1

up vote 3 down vote accepted

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).

share|improve this answer
1  
$\varphi(x)$ doesn't do you any good, because the numbers from $1$ to $x$ are not all relatively prime to $x$. In general, it is not true that if $a\equiv b\pmod {\varphi(x)}$ that $a^{\varphi(x)}\equiv b^{\varphi(x)}\pmod x$ –  Thomas Andrews Nov 17 '12 at 18:10
1  
If $x=8$ then $\varphi(x)=4$ and $2^5\equiv 0 \not\equiv 2^1\pmod 8$ even though $5\equiv 1\pmod 4$ –  Thomas Andrews Nov 17 '12 at 18:13
1  
Yeah, I got the formula wrong in my comment above, but my counter-example is for your second version. There, $a=2$, $x=8$, $n=1$ and $n'=5$. –  Thomas Andrews Nov 17 '12 at 18:14
1  
One quick reduction occurs when $n$ is odd. Then the expression $1^n+2^n+...+x^n \equiv 0\pmod x$. That's because $a^n + (x-a)^n \equiv 0\pmod x$. –  Thomas Andrews Nov 17 '12 at 18:19
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$. –  Thomas Andrews Nov 17 '12 at 18:25

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.