Sum of squares#4725

Sum of squares (Editorial)

The specified sum can be computed using a loop. However, we will also derive the formula. Let $f (n) = 1^{2} + 2^{2} + 3^{2} + ... + n^{2}$ f(n) = 1^2 + 2^2 + 3^2 + ... + n^2. Consider the sum:

k = 1 \sum n ((k + 1)^{3} - k^{3}) = (n + 1)^{3} - 1 = n^{3} + 3 n^{2} + 3 n

\sum_{k = 1}^n \left((k + 1)^3 - k^3\right) = (n + 1)^3 - 1 = n^3 + 3n^2 + 3n

Expand the sum as follows:

k = 1 \sum n ((k + 1)^{3} - k^{3}) = k = 1 \sum n (3 k^{2} + 3 k + 1) = 3 k = 1 \sum n k^{2} + 3 k = 1 \sum n k + k = 1 \sum n 1 = 3 f (n) + 3 \cdot \frac{n + 1}{2} n + n

\sum_{k = 1}^n \left((k + 1)^3 - k^3\right) = \sum_{k = 1}^n \left(3k^2 + 3k + 1\right) = 3 \sum_{k = 1}^n k^2 + 3 \sum_{k = 1}^n k + \sum_{k = 1}^n 1 = 3f(n) + 3 \cdot {n + 1 \over 2} n + n

Then, equate the right-hand sides of both equations:

n^{3} + 3 n^{2} + 3 n = 3 f (n) + 3 (n + 1) n /2 + n, n^{3} + 3 n^{2} /2 + n /2 = 3 f (n), 2 n^{3} + 3 n^{2} + n = 6 f (n), f (n) = \frac{n}{6} (n + 1) (2 n + 1)

n^3 + 3 n^2 + 3n = 3 f(n) + 3(n + 1) n /2 + n, \\ n^3 + 3 n^2 / 2 + n / 2 = 3f(n), \\ 2 n^3 + 3 n^2 + n = 6 f(n), \\ f(n) = {n \over 6}(n + 1)(2n + 1)

Algorithm implementation

Implement the program using a loop.

scanf("%lld",&n);
for(i = 1; i <= n; i++)
  sum += i * i;
printf("%lld\n",sum);

Algorithm implementation — formula

Implement the program using the formula.

scanf("%lld",&n);
sum = n * (n + 1) * (2 * n + 1) / 6;
printf("%lld\n",sum);

Java implementation

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long n = con.nextLong();
    long sum = n * (n + 1) * (2 * n + 1) / 6;
    System.out.println(sum);
    con.close();
  }
}

Java

Python implementation — formula

Implement the program using the formula.

n = int(input())
sum = n * (n + 1) * (2 * n + 1) // 6;
print(sum)

Python implementation — loop

Implement the program using a loop.

n = int(input())
sum = 0
for i in range(1, n + 1):
  sum += i * i;
print(sum)