0
$\begingroup$

I want to evaluate $\sum_{i=1}^{n} (x+i)^4$ So what i did is, after expanding it i reduce it to following form

$ x^{4} * n + 4 x^{3} * \sum_{i=1}^{n}i + 6x^2\sum_{i=1}^{n}i^{2} + 4x*\sum_{i=1}^{n}i^{3} + \sum_{i=1}^{n}i^4$

After doing this problem reduced to find $\sum_{i=1}^n i^a$ for $1\le a\le4$ .

This can be easily solved if $\sum_{i=1}^{n}i^4 = (n*(n+1)*(2n+1)*(3n^2 +3*n-1))/30 $ can be computed mod M ( M is not prime).

I know 30 = 6*5, so 6 will get canceled by n or (n+1) or (2n+1). Now for 5 there are 4 cases

1) n%5==1 then 3n^2+3n-1 is divisible by 5 
2) n%5 = 2 then (2n+1) will help to cancel 5
3) n%5= 3 then  3n^2+3n-1 is divisible by 5 I 
4) n%5 = 4 then n+1 will help to cancel 5.

I am not able to come up with solution when case 1 or case 3 appears. Basically i dont want to compute n^2, can anybody help me to arrive at solution

$\endgroup$
8
  • 1
    $\begingroup$ This is already pretty efficient. If $x$ is a nonnegative integer, you could write this as $\sum_{i = 1}^{x + n} i^4 - \sum_{i = 1}^x i^4$ and then use your closed form. $\endgroup$
    – Travis Willse
    Sep 10, 2014 at 13:11
  • $\begingroup$ @Travis thanks, my programe was taking 1.3 ms, after using new formula it took 1.8ms.. $\endgroup$
    – thetatheta
    Sep 10, 2014 at 13:30
  • 1
    $\begingroup$ @Travis - that's quite clever! $\endgroup$
    – Hypergeometricx
    Sep 10, 2014 at 15:10
  • $\begingroup$ @hypergeometric Thank you. $\endgroup$
    – Travis Willse
    Sep 10, 2014 at 17:57
  • $\begingroup$ @Travis My problem is solved, but i have one doubt. Let say I compute the above formula for all n=1 to $10^5$ and store it in some arrray dp[]. Now if i am given some value x<=$10^{10}$ and I am asked to compute formula $\sum_{i=1}^{x}i^4$ and output result mod m <=$10^5$ how can i use existing table to calculate it. $\endgroup$
    – thetatheta
    Sep 10, 2014 at 19:22

1 Answer 1

Reset to default
0
$\begingroup$

Another approach, using binomial coefficients: $$\begin{align} \sum_{i=1}^{n}(x+i)^4&=\sum_{i=1}^{n}\left[\binom{x+i+3}4+11\binom{x+i+2}4+11\binom{x+i+1}4+\binom{x+i}4\right]\\ &=\ \ \quad \binom{x+n+4}5+11\binom{x+n+3}5+11\binom{x+n+2}5+\binom{x+n+1}5\end{align}$$ which is nice and symmetrical and be easily evaluated.

If a factorised form is required, then substitute $y=x+n$ to get the rather untidy $$\frac 1{30}y(y+1)(2y+1)(3y^2+3y-1)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .