Sum the first N numbers in your program

Today I want to talk about a little math trick… sum the first N numbers, where N is an arbitrary number of your choice.

To do the job, you may be tempted to use a loop, something similar to the code below (in C#):

int result = 0;
for (int i = 1; i <= 100; i++)
    result += i;
// Now the variable 'result' contains the value of the sum

Putting the above code apart, you can save some CPU machine cycles using the following math formula:

$S = \frac {N({N+1})}{2}$

Obviously it is not my invention, but it can be found in any math book…
Therefore, regardless of whether you want to add the first 100 numbers or the first 1,000,000 numbers, the only thing you have to do is apply the formula above.

For example:

Sum of the first 100 numbers: 100 * 101 / 2 = 5,050

Sum of the first 1,000,000 numbers: 1,000,000 * 1,000,001 / 2 = 500,000,500,000

And so on….

It is interesting how you can get to the demonstration…
Suppose you want to sum the first 4 number, from 1 to 4.
You can write the following:

$S = 4 + 3 + 2 + 1 = 10$

Now rewrite it using the N symbol instead of numbers, and below write the same sequence in reverse order:

$S = N + (N - 1) + (N - 2) + (N - 3)$

$S = (N - 3) + (N - 2) + (N - 1) + N$

If you sum each member of the first equation with the corresponding member of the second equation you will get the following equation:

$2S = (2N - 3) + (2N - 3) + (2N - 3) + (2N - 3)$

This equation tells us that the double of the sum equals 4 times (2N – 3). So, since N = 4, to calculate S we can write the following:

$S = \frac {N (2N - 3)}{2}$

Be careful… the above formula works only for N = 4. This happens because the number 3 you see in the formula also depends on N. To make the formula work for the general case we only have to replace 3 with N – 1:

$S = \frac {N (2N - (N - 1))}{2}$

$S = \frac {N (2N - N + 1)}{2}$

And now the final formula:

$S = \frac {N (N + 1)}{2}$

Bye bye!!

Related Posts