I've just started to learn algorithm by joining Project Euler, and trying to understand the below formula
//3+6+9+12+......+999 = 3*(1+2+3+4+...+333)
//5+10+15+...+995 = 5*(1+2+....+199)
// 1+2+3+...+n = n*(n+1) / 2
//solution: (p * (n * (n + 1))) / 2
I simply couldn't form the linkage, how do OP actually form the formula of n * (n+1) / 2? Can anyone please break it down further? Many thanks in advance!
This answer consists of two sections.
Section 1: The General Summation Formula.
Consider finite (sorted) sequences $S$ of the form
$\quad k,\, k + g,\, k+2g,\, k+3g,\, \dots,\, k+(n-1)g$
where $k$, $g$, and $n$ are positive integers.
We are seeking a summation formula for the terms in $S$.
The integer $n$ is the length of the list $S$ of numbers.
If $n$ is even we can employ an summation algorithm that keeps on 'pairing off' the largest with smallest numbers. There are $\frac{n}{2}$ pairs of numbers and so the sum of all the numbers in $S$ is given by
$$\tag 1 \frac{n}{2}\,[k + (k + (n-1)g)]$$
If $n$ is odd then there are $\frac{n-1}{2}$ pairs of numbers and the middle term has value
$\quad k + \frac{n-1}{2}g = \frac{[k + (k + (n-1)g)]}{2}$
So the summation of all the terms in the odd case is given by
$\quad \frac{n-1}{2}\,[k + (k + (n-1)g)] + \frac{[k + (k + (n-1)g)]}{2}$
Fortunately, this formula is algebraically the same as the formula derived when there are an even number of terms.
So the summation of all the terms in $S$ is given by $\text{(1)}$.
Note that when $k = g$ the summation is given by
$$ g \frac{n(n+1)}{2}$$
Section 2: Deriving the $\frac{n(n+1)}{2}$ Summation Formula Using Sigma Notation
Recall
$$ \sum_{i=1}^n n = n^2 $$ Let
$\quad x = \sum_{i=1}^n i$
Then
$\quad 2x = \sum_{i=1}^n i + \sum_{i=1}^n i = \sum_{i=0}^{n-1} (i + 1) + \sum_{i=0}^{n-1} (n - i) = \sum_{i=0}^{n-1} (n + 1) =$
$\quad \quad (n + 1)^2 - (n+1) = n(n+1)$
So
$$ \sum_{i=1}^n i = \frac{n(n+1)}{2}$$