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??