## Programming is too often a substitute for mathematics…

I didn’t immediately recognize the equation that Steve Knight used in his answer to problem 6 of the Euler Project, but it was in fact just the formula for an arithmetic series. This one’s actually pretty easy to come to from an intuitive standpoint.

The story goes that Gauss had one of the meanest school teachers in the world. He made all of the students add the whole numbers from one to one hundred. The children would work for hours scratching away on their little chalk boards trying to get the answer, but Gauss was too lazy for that. He scribbled the answer and threw the chalk board across the room and said, “there it lies.”

What he had done was simplified the problem. If you take the numbers from 1 to 50 and pair them up with the numbers 100 to 51, you get a series of sums: 1 + 100, 2 + 99, … , 49 + 52, 50 + 51. All of these add up to 101. To get the answer he simply multiplied 101 by 50.

Generalizing this technique, to add up the first n natural numbers, you multiply half of n with n plus one… which is (n/2) * (n + 1). Algebraically, this “simplifies” to [n(n+1)]/2. Putting that into prefix notation gives you Steve Knight’s equation: (/ (* n (1+ n)) 2).

Now the people who put together the Euler project did not intend for us to write clever recursive programs. The problems they chose were meant to be so onerous that one would rather do the math than work it out. Us being programers, we miss the point completely!

Now, I’ve seen the formula for doing whatever you want with arithmetic series. I’ve seen stuff for geometric series, too. Arithmetic series are defined recursively where each term equals the previous term plus a constant. The nth term of a geometric series is equal to the first term times the “common ratio” raised to the (n – 1)th power. So we’ve got math for series like 55, 55, 60, … , 2035 and 1, 2, 4, 8, 16, 32, …. But I don’t see math for series like 1, 4, 9, 16, … , 10000.

I don’t see the cutesy thing we were supposed to be doing with this one….  What is the “right way” to sum a list of squares??

### 10 Responses to “Programming is too often a substitute for mathematics…”

1. Rupert Swarbrick Says:

There is a formula, which is n(n+1)(2n+1)/6.

Things to note:
– It’s cubic. Whereas the one for summing linear terms (i.e. arithmetic progressions) is quadratic ( (n+1)n/2 ). You can sort of see it’s going to have to be faster growing than quadratic otherwise eventually you’ll be adding on terms of the same order, but I can’t think of an immediate justification for why it’s not quartic or bigger.

– You can get the formula by doing clever maths (shamefully I can’t remember how and I’m supposed to be doing a maths degree). No doubt a search on google would turn up a proof.

– Or you can be lazy like me and write the first few terms in here: http://www.research.att.com/~njas/sequences/

2. Will Says:

The techniques on how to derive the sum of squares, cubes, etc.. is part of the book Concrete Mathematics by Graham et al.

3. lispy Says:

Thanks, Will. I hadn’t heard of that book. It’s now on my wishlist….

4. Will Says:

Just as an FYI to anyone reading this about Concrete Mathematics. It is an excellent textbook, easily one of my favorite math/CS books (and I’ve got a ton of them from going through a MS in pure math). It is worth noting that the intended audience is advanced undergraduate students or beginning grad level. You’ll be expected to already be somewhat familiar with proof techniques, asymptotics (big-Oh notation), some basic combinatorics (things like combinations and permutations), and some algorithm design (terms like divide and conquer, greedy algorithm, dynamic programming should be reasonably familiar). The book is for a course that is intended to provide most of the math background one would need to tackle Knuth’s TAOCP.

That said, it really is a good book, and does include full solutions to all the exercises which makes it excellent for self-study.

5. BobbyTheProgrammer Says:

On Gauss – his teacher recognized that young Gauss was something special when he presented this solution and recommended him for special training in mathematics.

6. Rudolf Olah Says:

One thing I noticed is the lack of a decimal point. Watch out when you’re dividing by 2 because it’ll truncate the result and you may want consistently want the higher value or the rounded value. It doesn’t matter often, but I remember reading about a problem with binary search: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Of course, as the blog post says, it isn’t a problem unless you’re Google 😛

7. Greg M Says:

The quick hand-waving reason why the formula is cubic is that you’re pretty much integrating a quadratic.

8. pkhuong Says:

Rupert: You’re adding n terms of order (at most) n^2. That’s obviously bounded by n^3. Once you know it’s a polynomial of order 3, you can use a simple extrapolation (Newton or Lagrange, for example) to find the formula.

Rudolf: That’s only in lesser languages. Most lisps have rational numbers. Moreover, that’s not an issue here, since a sum of integers is obviously integral itself (either n or (n+1) is even). As for binary search, the greatest problem is overflow (again, not an issue in decent languages). Rounding (… in binary search!?), truncating or rounding up is an implementation choice that must be taken explicitly, and will then be easy to treat.

9. arnarbi Says:

@Rudolf Olah: There’s no need to worry about it truncating. Notice that in n(n-1)/2 the n(n-1) part is always an even number because no matter what n is, either n or (n-1) is even.

Similar for n(n+1)(2n+1)/6 – one of n and (n+1) is even, and one of n, (n+1) and (2n+1) is always divisible by 3, so the whole product above the line is always divisible by 6.

Side note: To see why one of n, (n+1) and (2n+1) is divisible by 3, consider the following. If either n or n+1 is divisible by 3, we’re done. If neither are, then we need to show that (2n+1) is divisible by 3.

Since out of three consecutive numbers, one must be divisible be three, and (n-1),n and (n+1) are consecutive, then (n-1) must be the one. Thus we have that for some integer k

n-1 = 3k

rewrite this to

n = 3k+1

Now, look at (2n+1) and replace,

2n+1 = 2*(3k+1) + 1
= 6k + 2 + 1
= 6k + 3

which is obviously divisible by three since both terms (6k and 3) are.

cheers,
Arnar

10. Rudolf Says:

pkhuong: ah, that is true. I’ve been stuck in Perl and C++ mode for the last few days, I forgot that Lisp has support for rational numbers.