Project Euler (problem 1)

I just discovered Project Euler and I thought I'd start going through the problems, in order, to keep up my math and programming knowledge. Here's the text of the first problem:

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.

There seem to be two straightforward ways to solve this problem. You could write a program that goes through every integer below 1000, adding the ones that are a multiple of 3 or 5. You could also come up with an expression for the sum, and then carry out the necessary calculations by hand. I'll try both methods here.

First, the program, since I think it will be faster for this problem. This code was written in an IPython notebook.

sum = 0

for i in range(1000):

    if (i % 3 == 0) or (i % 5 == 0):

        sum += i

print sum

Then, by "hand": The solution can be found using fewer operations by applying some logic. We want to sum every multiple of 3 or 5. We can do this by summing the multiples of 3, adding the sum of the multiples of 5, and then subtracting the sum of the multiples of 15, since multiples of 15 would be counted twice otherwise.

1000/3 is 333 remainder 1. This means that the sum from threes is 3 * (1 + 2 + ... + 332 + 333). Similarly, the sum from the fives is 5 * (1 + 2 + ... + 198 + 199). The sum that needs to be subtracted because of the doubly-counted fifteens is 15 * (1 + 2 + ... + 65 + 66). Adding together the first two expressions and subtracting the third gives:

-7 * (1 + 2 + ... + 65 + 66) + 8 * (67 + 68 + ... + 198 + 199) + 3 * (200 + 201 + ... + 332 + 333)

The first set of parentheses contains 66 terms. It's apparent that they can be simplified: 1 + 66 = 67, 2 + 65 = 67, and so on, until 33 + 34 = 67. Therefore, the value contained is just 33 * 67. A similar approach can be used to simplify the other sums in parentheses, giving:

-7 * (33 * 67) + 8 * (66.5 * 266) + 3 * (67 * 533)

This result matches the brute force method, so everything worked out.

Most of the problems in Project Euler can be easily brute-forced with a fairly simple program, but by coming up with better algorithms, every problem should be solvable in under 1 second on an everyday computer. This encourages the use of elegant solutions that save computer time, and provides a more interesting challenge.

First Post

I'll use this to keep track of the things I'm working on. I just bought an arduino after thinking about it for years, and right before I'm supposed to graduate. I probably won't get much homework done for the last couple weeks of the quarter. Anyway, I'm still at school and don't have many electronic components. Here's my first project.

A blinking LED to simulate a heartbeat. All I needed was a resistor and an LED. Here's what it looks like in operation. It's kind of hard to see in the video, so try it yourself if you can

Here's the code. If you know which COMS port your arduino is on, and you have the codebender plugin installed, you should be able to load it directly onto your arduino from this page.


Some interesting things to note are that the LED's brightness is very nonlinear with pwm value. Changes on the low end of the scale have a much larger effect than changes on the high end. The difference between 5 and 6 (out of 255) is much larger than the difference between 200 and 255, at least to our eyes. Also, to make the pulsing look like something living, it has to be pretty different from an actual heartbeat. Much slower, and smoothed out. It just doesn't seem right otherwise.