A long time ago, a mathematician by the name of Carl Friedrich Gauss was attending grade school. The teacher of his class wanted a break, so the teacher decided to assign the class a very time consuming problem. Sum all of the numbers between 1 and 50. 1+2+3..+..+49+50. So the students of the class set to work on the daunting task of summing all of these numbers. After a minute or two, the teacher noticed that Gauss wasn't doing anything. After investigation, the teacher found out that Gauss had discovered a new way to solve the problem without having to sum up each element by hand. The identity he found was: the sum of i from 1 to n is (n(n+1))/2.

What is the moral of the story? Don't use a loop if you can do something in constant time.

A good web site for practicing programming skills is Project Euler. Of particular interest, the very first problem can be solved using the method above.

Try to solve it on your own before reading the rest of this post.

Keep trying......

Alright. So you need to know the sum of multiples of three or five for every single number under one thousand.

The first step is to calculate the sum of multiples of threes under 1000:

The next step is to calculate the sum of multiples of fives under 1000:The sum of i from [1 to n] is (n(n+1))/2; as a result, 3 * sum of i from [1 to n] is 3(n(n+1))/2.

where n = floor(N/3) => floor(999/3) = 333

N is the total number you want to count up to.

We can now begin to construct a formula.The sum of i from [1 to m] is (m(m+1))/2; as a result, 5 * sum of i from [1 to m] is 5(n(n+1))/2.

where m = floor(N/5) => floor(999/5) = 166

If you try this formula, you might get an incorrect answer. Why?3(n(n+1))/2 + 5(m(m+1))/2

where n = floor(N/3) => floor(999/3) => 333

where m = floor(N/5) => floor(999/5) => 199

It turns out that there is a set theory problem lurking behind the scenes. The left hand component will generate values like 3*5 while the right hand component will generate values like 5 * 3. So we are calculating 15 twice in the above formula (along with other similar values).

So it turns out we got one more step to do. We need to subtract off the extra calculation we are doing. How do we do that?

Now we should get the correct value. I apologize for the syntax, but I don't think this thread supports latex.3(n(n+1))/2 + 5(m(m+1))/2 - (3*5)(o(o+1)/2

where n = floor(N/3) => floor(999/3) => 333

where m = floor(N/5) => floor(999/5) => 166

where o = floor(N/15) => floor(999/15) => 66

The above method is the smart man's approach to solving the problem. Notice that it can be implemented in code without using a single loop.

*updated thanks to Schmidt for pointing out the index error.

Here is how the above mathematics is implemented in visual basic.

Code:Public Class Form1 Function CalculateResultBest(ByVal num As Long) As Long Dim n As Integer Dim m As Integer Dim o As Integer n = Math.Floor(num / 3) m = Math.Floor(num / 5) o = Math.Floor(num / 15) CalculateResultBest = ((3 * n * (n + 1)) / 2) + ((5 * m * (m + 1)) / 2) - ((15 * o * (o + 1)) / 2) End Function Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load MsgBox(CalculateResultBest(999)) End Sub End Class