Happy Birthday, Gauss

Google had told me (via their daily doodle) that today is the 241 birthday of Carl Friedrich Gauss, so I thought it's a perfect time to honour his memory in a little trivia item - Gauss was definitely one of the greatest mathematicians, with his discoveries and contributions spread all over the literature. But one of his most beloved discoveries was made when he was only a school child. His teacher used to give the class frustrating arithmetic exercises to keep them busy and quiet for a while. Once he gave them the task to calculate the sum of all numbers between 1 and 100.

All the children set and started to calculate, adding one number at a time.

Gauss, being Gauss, had noticed an interesting fact: The sum of 1 and 100 equals to the sum of 2 and 99 which equals to the sum of 3 and 98 and so on. So the sum of all the number in this range could be viewed as (1 + 100) * 50

Gauss got up of his chair after just a few moments, and handed to the teacher his correct solution.

So this is how Gauss invented the formula for summing an arithmetic series.

And it has a nice implementation on us. When writing this kind of computer program, we can sum the elements in O(n), using a loop that iterates through each element. Or we can just use the formula, and do it in O(1).

Hail Gauss, and Happy Birthday :)