1 - Sums of Multiples

Problem 1:

Link

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9.  The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Background:

Mathematicians like to tell the story of a young Carl Gauss, a mathematician who made some very important advances in number theory, statistics, and electrostatics.  In some ways he has become mythologized, as is often the case with great historical figures.  A legend is told, passed down, and altered on each retelling.  The story becomes part of the culture of what ever group "owns" the story, and its members take pride in it.  There are dozens of such stories; King Arthur and his knights of the Round Table, Saint Benedict escaping being poisoned through divine intervention, George Washington refusing to lie after chopping down a cherry tree.  But the story I am about to tell regards a very young Carl Friedrich Gauss simply answering a question in math class.

When Carl Gauss was a child, we would call a tween by today's lingo, he attended school like any other boy his age. He lived in the Brunswick region of what was then the Holy Roman Empire. He was born in 1777, so by the time this event was taking place he would be about 13, making the year about 1790. This is a time where Europe is starting to enter what I consider to be the modern age. The United States had just won their Revolutionary war, and the French were in the throws of their own Revolution.

Currently there are many stereotypes about Germans, one of the most notable being that they are very strict.  This stereotype also existed back in the 19th century, and it can also be inferred that the Germans were strict at the tail end of the 18th as well.  So, the young Carl Gauss was in class, and, as the story goes, the school master was fed up with his students goofing around.  As a punishment he told his students to add up the numbers from 1 to 100.  The school master expected the students to take some time with this problem.  At the very least a few minutes, but he was surprised when Carl Gauss, nearly instantly came up to him, and gave the answer 5050.  The school master was shocked one of his students found the answer so quickly.  He didn't know if this was correct off the top of his head, so he took out a very large book of problems and answers.  He found that Gauss was exactly correct in his calculation.  He hadn't missed carrying a digit or anything.

So how exactly did Gauss add up 100 numbers so quickly.  Was he a savant, like Rainman?  Well, no, he realized a very special pattern between the numbers.  All of the other kids in the classroom were doing what the school master intended.  They took one added two to get three, then added three to that and got six, added four and got ten, and so on.  Gauss realized that you could add the sum again, only in reverse order, to make the problem much easier.

$$ S = 1 + 2 + 3 + ... + 100 \\
S = 100 + 99 + 98 + ... + 1 \\
S+S = (100 + 1) + (2 + 99) + ( 3 + 98) + ... +(1 + 100) $$

Each of the sums in parentheses is clearly equal to 101, and since there are 100 instances of that sum we get the clean equation:
$$2S = 100*(101)$$
From here, it's trivial to solve, the product \(5050\) becomes easy to obtain.

More generally, the sequence is called an Arithmetic Sequence, i.e. a sequence in which any two consecutive terms share a common difference.  The sum of an Arithmetic Sequence is:
$$\sum\limits_{i = 1}^{n}a_i = \dfrac{n*(a_n+a_1)}{2}$$

The line of thinking Gauss used to get this answer so quickly is exactly the same line of thinking we need to solve Project Euler problems.  If each problem is a castle, then at the front of it will be walls, moats and ramparts, which will take time to get through.  Alternatively we could storm the castle by taking the secret entrance.  Gauss found that secret entrance to the problem of adding up arithmetic sequences, and in this problem we will put the same principle to use.

The Math:

The sum of a multiples of \(a\) is \(a*(1+2+3+...) = a*\frac{(n)(n+1)}{2}\) where \(n\) is the number of digits in the series.
So the sums of the multiples of 3 and 5 are:
$$ S_3 = 3 + 6 + 9 + 12 + 15 + ...  + 999\\
S_5 = 5 + 10 + 15 + 20 + ...  + 995 $$

As you might have noticed we cannot simple add these two sums together and get our answer, both of these sums include 15, in fact, they include all multiples of 15 less than 1000.

Thanks to what is known as the Inclusion-Exclusion Principle, which states that the union of two sets is equal to the sum of the two sets minus the intersection, we can solve the problem.  What this means in plain speak is we have twice as many multiples of 15 than we need, so we can subtract it out.

The basic formula for the sum of an arithmetic series is \( S = a * \dfrac{n*(n+1)}{2}\) where \(n\) is the number of numbers to add up.  The largest multiples of 3, 5, and 15 below 100 are 999, 995, and 990 respectively, so \(n\) for each would be 333, 199, and 66.

$$Ans = 3*\frac{333*334}{2} + 5*\frac{199*200}{2} - 15*\frac{66*67}{2}$$

To avoid divulging the answer to the puzzle, I will ignore explicitly stating it.

The Code:

Python:

Easy stuff here.  Basically just copying the line from above.

print(3*333*334/2 + 5*199*200/2 - 15*66*67/2)

Another cool python program that I found, note: I did not write this code, involves list comprehension.  there is a neat trick in python where a for loop statement can be used as an iterable object.

print(sum( x for x in range(1000) if x%3 == 0 or x%5 == 0))

This code automatically generates a list of multiples of 3 or 5 below 1000, and prints the sum.  In one line.  That is pretty wild.

If you don't recognise what the % sign means, it is called the modulo operator.  The expression x%n would give the remainder if you divided x by n.  For example 19%4 equals 3, because 19/4 is 4 with a remainder of 3.  If the remainder is 0, that means x would be divisible by n.  n times some number will give you x, meaning, by definition, x is a multiple of n.  Since this is what we want to find out, whether a number is a multiple of 3 or 5, it is used in the code.

Note, this kind of code is what many would consider to by "un-Pythonic."  It skirts understandability in favor of creating the shortest program possible.

My own code is pretty similar in that regard,  it would have been better if I defined the sums before instead of using numbers which seemingly come out of nowhere.  Those numbers are what are known in the programming world as "magic numbers."

Future problems will be much more complicated and I will do well to avoid them.

C:

I did something similar in C to that last python code.  But instead of calling the sum function, which there isn't in the default C, I had a variable called sum, which I added to if a number was a multiple of 3 or a multiple of 5.  When the loop terminates I print out the value of sum.

#include <stdio.h>

main()
{
    int sum;
    sum = 0;
    int i;
    for(i = 0; i<1000; ++i){
        if (i%3 == 0 || i%5 == 0){
            sum += i;
        }
    }
    printf("%d\n", sum);
}

Well, there it is, my first blog post.  I hope you enjoyed reading it as much as I did writing it.  I'm not exactly sure if I'll have a schedule.  All I can say is the next post will be out when it comes out.