Project Euler
For the next few weeks, we'll focus on Project Euler - like questions. A key component of these problems is that they are generally meant to be solved with a short computer program. Usually, a little mathematical insight will make the difference between a program that runs in a reasonable amount of time and one that does not. To get the basic idea, let's take a look at the first problem:
Project Euler question 1
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.
While quite easy, this problem illustrates the general idea. Typically, there's an easier version of the problem that allows you to check your work; I call this the pre-problem. Then, the question itself requires either more computing power or a more clever algorithm.
Let's take a look at some Python code that solves the pre-problem.
Note that's live code. Hit the "Evaluate" button to generate the answer. Do you see how to modify the code to get the answer to the actual question?
Improving our code
Let's suppose now that we'd like to find the sum of all numbers less than 1 million that are divisible by 17 or 19. Emulating the code above (and including some code to time the computation), we might write:
That is not particularly fast. Rather than checking every, though, we can simply list every seventeenth and nineteenth number starting from zero. I guess we'll have to remove the ones that we counted twice, though. Here's some code that uses that approach:
Well, that's a lot faster!
Problem 1
Find the sum of all the multiples of below .
To submit your solution, you should respond to my email with subject line "Problems Lab 1 #1". Be sure to include the Sage Cell Server's Short link to the Python code that you wrote to generate your solution.