Project Euler: Problem 1
The First of Many
I’ve decided to program more often.
I’ve also said that many times before.
However, I think I finally found something that will help me stick with the habit: a huge collection of puzzles.
As far back as I can remember, I have loved solving puzzles. I think that’s a big reason why I was so successful in the maths and sciences in school and decided to go into engineering: it’s all one big puzzle.
But programming is a skill I have fallen behind on. I’ve read at least one book on Python and done most of the exercises, but don’t feel confident in my abilities. One thing I have determined is lacking in my development is a daily practice.
Thankfully I stumbled upon Project Euler. Immediately I was hooked.
I opened Sublime and started solving problems as quickly as I could.
But a few problems in I decided to write about it as well, mostly for myself. So here goes: I’m going to try to document my thoughts as I’m solving problems.
Here’s the structure:
- Problem
- Approach
- Challenges
- Solution
- Next Steps and Further Developments
Let’s give it a go now.
Problem:
Find the sum of all the multiples of 3 or 5 below 1000.
Approach:
Loop through all numbers from 1 to 1000, and if a number is a multiple of 3 or 5, add it to the running sum.
I created a function to calculate running sum of all numbers that are a multiple of n under a given limit k:
Be careful not to add numbers twice: for example, 15 is a multiple of both 3 and 5, so we need to add it once but not twice.
Challenges:
I couldn’t think through a good way of eliminating multiples of 15 without storing all the numbers, which felt inefficient.
The result I decided on was to calculate the sum as a combination of 3 results: sum of multiples of 3 + sum of multiples of 5 - sum of multiples of 15.
Solution:
Next Steps:
If this problem were expanded such that multiples of numbers with common factors were required, I would create a function that doesn’t sum multiples of numbers. This might involve storing each number into an array so it doesn’t get counted twice, which feels inefficient but might be an appropriate result.
