'S' is for Simply Summing

'S' is for ... simply summing.

Okay, this post was going to be about symmetries and super-symmetries, then I was going to transition to sieves, like the Sieve of Eratosthenes, and how that relates to fizz-buzz, ...

But then I thought: 'eh.'

Yeah, that's what I thought: 'eh.'

I'm a moody brute, filled with deep, indiscernible thoughts, 'cause that's how I roll.

So, yeah: eh. This one will be a simple post today.

Sums.

Sum the numbers 1.

Yeah, I just said that; humor me.

Okay, the sum of 1 is 1. Toughie.

Next, sum 1 + 2.

3, right? Still with me?

Okay, 1 + 2 + 3.

Got it? 6. No probs.

Now: sum 1 to 10. No laptop help, just sum it yourself.

A little more fun, right? So, that's 55.

Okay, no computers: sum 1 to 100.

Hm, hm, hm. Done yet?

La-di-dah. You're not even trying, are you? You're just reading this post.

Okay, the sum from 1 to 100, inclusive, no computers is ... 5,050.

1 to 1000: 500,500.

Pattern? You bet.

1 to ... oh, I don't know: 123:

That's a might harder, but, no computers:

62 00 + 12 4 0 + 18 6 = 7,626.

Okay, let's verify, by asking my Haskell interpreter: 

Prelude> sum [1 .. 123]

7626

Yeppers, I was right. I was also as fast as a person typing a program into their computer to solve it, if they were using a functional programming language, and much, much faster than a person using a computer if they weren't and called up Excel, for example (loading ... loading ... loading ... blue screen of death) (You really need to virus-clean your computer, because I see you don't have a Mac, do you, tsk, tsk!) or if they pulled out their HP calculator from their high school days because they are that old, boys and girls!

You see this thing in my hand, children? This is not a smart phone, it's a calculator.

Children: Ooh! Papa, can I borrow it for a sec ...

Children, borrowing it, the puzzling over it: Um, Dad, ... where's the Plants vs. Zombies 2 app?

Yeah, a calculator, it calculates. And that's it. No google, no nothing, just numbers and numeric operations.

Children, looking uncomprehendingly at the thing in their hands, then, tossing the cootied thing from their hands and run to their rooms, screaming, remembering with horror the time Dear Old Dad got out an LP and told them that music came out of it, but ... it didn't have playlists!

Yeah. Calculator. But would your calculator get you that sum that fast? I mean, after you go to the CVS to buy a new battery. Those things are long-lasting, but thirty years later? And you expect your calculator to still just work?

Pfft! Heh.

Pick a number (natural number), any number, I'll sum it for you, from the origin.

Sum 1 to 31415.

Okay

31415 * 15708 = 314,15 0,000 + 157,075, 000 + 21,990,5 00 + 0 + 251,320 = 493,466,820

Okay, that took a bit longer, let's see what Haskell says:

Prelude> sum [1..31415]

493466820

Okay. Damn! ... Sometimes I impress even myself.

How do I do this? How do I add all the numbers from 1 to 31,415 and in under a minute? And perfectly, perfectly, correctly?

Well, I'll tell you.

But first, I'll tell you a story.

Once upon a time, there was a little boy named Gauss, and he was a naughty, little, precocious lad, always getting into trouble for dunking Susie Derkins' pigtails in the inkwell at his desk, and that would be fine if she had jet black hair, but you know the Viking types, right? All blond-haired, blue-eyed things, and getting your honey-blond long-flowing locks dunked into ink was not on the agenda for poor, little Susie, who cried, and had to be sent home to console herself with an appointment at the beautician's who thought the Goth-look actually fit Susie well, so she came back the next day as Suze-in-black-leather-and-studs which was disruptive for the class in other ways, so Gauss found himself at detention again.

But this time the math teacher had had enough of little Gauss' pronouncements and recitations of π to sixty-seven places, and decided to teach the little scamp but good.

Not that I'm channeling, or anything. It's not 'Mary Sue'-writing; it's 'walking in your character's moccasins a mile' ... even though Gauss probably didn't wear moccasins all that often, anyway.

Still with me?

So, mean-old Herr Schopenhauer told little Gauss. "Okay, twerp, this is gonna be a light one on you. You can go home after you sum the number from one to one hundred."

Huh? One to one hundred? But that will take all night!

"That's right," said mean old Herr Bergermeister Meisterburger, "so you'd better get crackin'!" And he cackled evilly with Schadenfreude.

The Head-Master had several names, don't you know, ... and a peridiction for Schadenfreude with his afternoon tea and muffin.

So, what could little Gauss do? He got cracking, the poor lamb.

1 = 1

1 + 2 = 3

1 + 2 + 3 = 6

1 + 2 + 3 + 4 = 10 ... obviously, you just add the last number to the previous sum

1 + 2 + 3 + 4 + 5 = 15 ... now, wait a minute ...

1 + 2 + 3 + 4 + 5 + 6 = 21 ... there seems to be another pattern here ...

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 ... Gauss looked at the chalkboard, then ...

Got it! Little Gauss thought.

Then he wrote:

1 + 2 + 3 + ... + 98 + 99 + 100 = 5,050.

"G'nite, Teach!" Gauss crowed, and off he skipped home with Suze, where they shared a chocolate milk and a strawberry poptart ... before all that sugar glaze had been added to the crust (shudder).

And Herr Herren HerringSchönheit was left stuttering a "Vat? Vat? Git back here, you rapscallion!"

Okay, what's a rap-scallion? Is it a thug onion with 'tude, a glock, and a triple-platinum pedigree?

But all Herr whatz-his-name could do was sputter, because little Gauss got it.

The sum from one (zero, actually) to any number reduces to a simple formula:

sum [1..n] = n * (n + 1) / 2

Either n or n + 1 is even, so one of them is divisible by two, so it works.

Try it out:

1 = 1 * (1 + 1) / 2 = 1 * 2 / 2 = 1

1 + 2 = 2 * (2 + 1) / 2 = 2 * 3 / 2 = 3

1 + 2 + 3 = 3 * (3 + 1) / 2 = 3 * 4 / 2 = 3 * 2 = 6

... so obviously:

1 + 2 + 3 + ... + 31,415 = 31,415 * (31,415 + 1) / 2 = 31,415 * 15,708 = that big number I computed earlier. Yeah, almost five-hundred million!

Put that into your "ceci-n'est-pas-unu-pipe" and smoke it. I'd buy that for a dollar.

Now, there's something you can impress your friends at Happy Hour with.

Epilogue

Okay, so you can sum 1 to ... whatevs, but what if a friend asks you, very kindly, and very politely, 'Okay, Ms. Smartypants, how about summing 1,000 to 2,000? What's that, huh? Betcha can't do that! Huh? Amirite? Amirite? Lookacha sweating bullets now, arencha? So, well, what is it? Huh?"

Yeah, really politely. Like that.

Now you could say, "But-but-but, Gauss' summer[-function, not -time] doesn't work like that."

But then you'd have feet of clay and egg on your face.

And with this hot summer coming, you don't want egg on your face. Trust me on that one.

So. What to do?

Think about it, that's what.

You simply make your 1,000 your zero, by scaling each number back by 1,000, then get your sum, then scale back each number by 1,000. For each time you applied the scale, you apply the scale to the result.

So, the sum of 1,000 to 2,000 inclusive is:

1,000 + 1,001 + 1,002 + ... 1,998 + 1,999 + 2,000 =

scaled back is

0 + 1 + 2 + ... + 998 + 999 + 1000 = 1000 * (1000 + 1) / 2 = 500,500

Now scale each number forward again, by adding 1,000 back to each number. You did that 1,001 times, right? (Don't forget to count the zero.) That's a rescalation (that's a word now) of 1,001,000. Add that to your sum to get 1,501,500.

There's your answer.

Let's check:

Prelude> sum [1000..2000]

1501500

Bingo! Tickets! This must be the Front Row!

And you, very politely, just told your friend where they could put their superior 'tude, too.

Win-win! Good times; good times!

See y'all tomorrow. By the way, what's the number of moves needed to solve the Towers of Hanoi? Not that 'Towers of Hanoi' is going to be my topic for 'T.'

Not at all.