Using a mathematical identity to speed up certain calculations.

[Maven]

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

The next step is to calculate the sum of multiples of fives under 1000:

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

We can now begin to construct a formula.

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

If you try this formula, you might get an incorrect answer. Why?

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?

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

Now we should get the correct value. I apologize for the syntax, but I don't think this thread supports latex.

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.

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