No account? Create an account  Carl Friedrech Gauss's parlor trick. - Adventures in Engineering — LiveJournalThe wanderings of a modern ronin.   Date: 2008-11-22 06:53 Subject: Carl Friedrech Gauss's parlor trick. Public Music: KMFDM - Get Out Of My Head
Runner-up Music: Consolidated - Brutal Equation

I tried to sleep tonite. I really did. But it's another one of those nights where my brain decided it would be fun to keep me wide freakin' awake. Oh, I'm sure the bottle of Mt. Dew at 8pm didn't help. But seriously, being kept awake 11 hours by that? Nope.

You know what's been going through my head all night, while I couldn't sleep? That story about Gauss. The one about how he blew the mind of his math teacher in grade school. Have you heard it? It's probably apocryphal, but it's a great story anyway. I think I first heard it from my high school calc teacher. While I couldn't sleep, I re-derived the math from the story in my head.

But before we begin, let me give you this perl script:

#!/usr/bin/perl -w

if(scalar @ARGV != 2) { print "Usage: \$0 lownum highnum\n"; exit; }

\$sum = 0;
for (\$ARGV..\$ARGV) { \$sum += \$_; }
print "Sum = \$sum\n";

This calculates the sum of all numbers between the first and second command line arguments, inclusive. For instance: "sum.pl 1 3" would add 1 + 2 + 3 and print "Sum = 6". You may find this script useful to check the sums as I tell the story. Or, if you don't trust me, go ahead and write your own program to do sums of series. I'll wait. ;]

...

How the hell did he do that?

When he was asked to do the numbers between 1 and 100, Gauss wrote them down:

1 2 3 4 5 6 7 8 .... 93 94 95 96 97 98 99 100

He looked at the outermost pair of numbers: (1, 100). Equals 101, duh. Then he looked at the next outermost pair: (2, 99). Hey wait, that's 101 too! (3, 98)? 101! (4, 97)? 101! (5, 96)? 101! Every pair adds up to 101! And there are 50 pairs. So, 50 x 101 = um, (100 + 1) * 50 = (100 * 50) + (1 * 50) = 5000 + 50 = 5050.

200 didn't take much longer. Gauss wrote down:

1 2 3 ... 198 199 200

"Each pair sums to 201... and there are 100 pairs."

201 * 100 = 20,100!

Having got the hang of it now, when asked about 800, Gauss mentally did 801 * 400 (which is just 8 * 4 = 32 with four additional zeros, plus 400) and the rest is history.

Want to go a little deeper into the math?

The equations are not too tough. Call x the lower number and y the higher number. The sum of pairs is easy, it's (x + y).

How many pairs is tougher. In the general case, there are two possibilities:

A) (y - x) might be odd. In this case, the number of pairs is (y - x + 1)/2.

Consider adding the numbers 1 to 10. There are (10 - 1 + 1)/2 = 5 pairs: ((1,10) (2,9) (3,8) (4,7) (5,6)).

B) (y - x) might be even. In this case there are simply (y - x)/2 pairs, but there's also a lone number that doesn't fit in any pair.

Consider the numbers 1 to 9. The pairs are ((1,9) (2,8) (3,7) (4,6)) and the loner, 5 (= (x+y)/2). There are (9 - 1)/2 = 4 pairs, but (9 + 1) * 4 is not the correct answer. You must do (9 + 1) * 4 + 5.

So, let's take these individually.

In the case that we have no loner and all numbers fall into pairs, the answer for the sum of the series is:

(x + y)(y - x + 1)/2

= (xy - x² + x + y² - yx + y)/2

xy cancels with -yx...

= (y² - x² + y + x)/2

And in the other case, where we have a loner number, the answer for sum of series is:

(x + y)(y - x)/2 + (x + y)/2

= (xy - x² + y² -yx)/2 + (y - x)/2

= (y² - x²)/2 + (y + x)/2

look ma, same denominator!

= (y² - x² + y + x)/2

Which is the same as what we got in the first case. Handy how that works out...

So, consider this. Let's say for some reason you want to know the sum of the series 121 to 787. A handy perl script is nowhere to be found, but you do have a calculator. So:

(787² - 121² + 787 + 121)/2

= (619369 - 14641 + 787 + 121)/2

= (604728 + 908)/2

= 302818

Which is exactly what you get if you run "sum.pl 121 787"!

One last wrinkle. The case where x = 1 is particularly nice because parts of the equation cancel each other out. Consider summing (x=)1 to (y=)15:

(y² - x² + y + x)/2

-x² + x always cancels when x = 1...

= (y² + y)/2

= (225 + 15)/2

= 240/2

= 120

Really. That's it. The sum of numbers from 1 to 15 is 120. Check with the perl script.

Memorize your squares (or learn mental math tricks to compute them fast) and you can do some seriously crazy stuff.

Quick: What's the sum of the numbers from 1 to 400? Let's see, 4² = 16, tack on the four zeros that we dropped, that's 160,000 (= y²). Add 400 (= y), thats 160,400. And 160,400 / 2 = ? Well, 16 divided by 2 is 8, so 160,000 / 2 must be 80,000. And 400 / 2 is 200. So: 80,200. The sum of the numbers from 1 to 400 is 80,200.

And now you know little Carl Friedrich flipped out his teacher. And what my maniac brain has been doing to me all night, instead of letting me sleep... User: Date: 2008-11-22 15:53 (UTC) Subject: (no subject)
Oh shi-! I just remembered what set me thinking about the sum of series like 14 damn hours ago.

It was that #!@\$% "You have two bowling balls" job interview question that I found on Reddit.

Damn you Reddit! Daaaaaaaaaaaaammnn yyyyyyyyyyyyyooouuu!!! User: Date: 2008-11-22 15:58 (UTC) Subject: (no subject)
asta:~/gauss> ./sumseries.pl 1 14
Sum = 105
asta:~/gauss> User: Date: 2008-11-22 15:59 (UTC) Subject: (no subject) Keyword: Trajedy... for YOUUUUUUUUUUUU!!!!
I could have been playing Dead Space all night, damnit!

 User: Date: 2008-11-22 17:37 (UTC) Subject: (no subject)
That's sum insomnia you've got there.  browse          