Introduction

I was 12 or 13 years old when I became certain that I am not a genius. I don’t remember how the subject came up, but my father told me a story. It was a story about the childhood of famous mathematician Karl Friedrich Gauss. This is how I remember it. Blah blah.

Karl Friedrich Gauss

Karl (German for Carl) was 10 years old. It was a cold winter’s day in Brunswick. Karl’s teacher was suffering an unbearable hangover, and dreading the task of standing on two legs before a classroom full of innumerate saxon youth, he resorted to the battle tested and foolproof strategy all teachers use from time to time. Busywork, of course.

Herr Professor instructs the children to do the following: add up all the numbers from 1 to 100. All of the dullards before him begin their wretched task the only way they know how. 1 + 1 = 2. 2 + 2 = 4. 3 + 4 = 7. 4 + 7 = 11. Feel free to follow along if you hate yourself.

As the teacher kicks back and begins to read Goethe or whatever, he is shortly interrupted by the precocious young Karl Friedrich Gauss. The answer, Herr Professor, is 5050. The teacher, unenthusiastic about Gauss’s obvious cheating, demands to know how the boy completed the assignment so quickly.

Adding the numbers one by one

Let’s start with a simpler problem, mainly so we can fit the whole thing on the screen. If we were really adding up only 1-10 there would be little reason to go off the beaten path. 1-100 is arguably still manageable. What about 1-1000? 1-1000000000 would even take my laptop a couple of seconds (1.734s add the time I wrote this) to add them up one by one (try it yourself!)

#include <stdio.h>
#include <time.h>

int main(void) {
  long long total = 0;
  long long n = 1000000000;

  // begin measuring
  clock_t start = clock();

  for (int i = 1; i <= 1000000000; ++i) {
    total += i;
  }

  // stop measuring
  clock_t end = clock();
  float seconds = (float)(end - start) / CLOCKS_PER_SEC;

  printf("total: %lld\n", total);
  printf("time to complete: %2.7f", seconds);
}

Setting up the trick

Sometimes weird patterns emerge that allow us to take shortcuts. When adding up integers one by one, we are greeted with one such pattern. Consider the obvious fact that 9 + 1 = 10. Ok cool who cares… but so does 8 + 2, and 7 + 3…

They all equal 10!

Adding them up is much easier now

We can exploit this neat fact to get some stuff done.

You can transform it into a multiplication problem

And now you can see how Gauss solved the problem

Proof by Induction

You can prove that this formula actually works for any number n where you are adding from 1 to n.