?

Log in

No account? Create an account
Carl Friedrech Gauss's parlor trick. - Adventures in Engineering — LiveJournal
The wanderings of a modern ronin.

Ben Cantrick
  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[0]..$ARGV[1]) { $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. ;]


So the story goes... One day back in the late 1700's, little Carl Friedrich Gauss was in math class. His math teacher wanted to keep the class busy for a while, and said: "Everyone, I want you to compute the sum of all the numbers between 1 and 100, inclusive." So all the kids groan and start scribbling away. About two minutes later, little Carl Friedrich pipes up and says, "Teacher, is the answer 5,050?" The teacher has used this trick before and knows that's the right answer. He says, "Very good, Carl Friedrich! The rest of you, keep adding until you get that answer. Carl Friedrich, I have a special problem for you. Please tell me the sum of all numbers between 1 and 200." Little Carl Friedrich looks back down at his paper, but about ten seconds later looks back up and says, "It's 20,100." The teacher blinks visibly. He doesn't know if that's the right answer or not. So he says, "Uh, okay. Now please add up the numbers between 1 and 800." Little Carl Friedrich doesn't even look down at his paper. He looks up for a second, then looks back at the teacher and says: "320,400".

...

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...
Post A Comment | 4 Comments | | Link






Ben Cantrick
  User: mackys
  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!!!
Reply | Thread | Link



Ben Cantrick
  User: mackys
  Date: 2008-11-22 15:58 (UTC)
  Subject:   (no subject)
asta:~/gauss> ./sumseries.pl 1 14
Sum = 105
asta:~/gauss>
Reply | Parent | Thread | Link



Ben Cantrick: Trajedy... for YOUUUUUUUUUUUU!!!!
  User: mackys
  Date: 2008-11-22 15:59 (UTC)
  Subject:   (no subject)
Keyword:Trajedy... for YOUUUUUUUUUUUU!!!!
I could have been playing Dead Space all night, damnit!
Reply | Thread | Link



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



browse
May 2015