Project Euler: Task 1

Hello Again!
So, as I said, I’m going to start off with Project Euler… Task 1 to be exact! All of the future blogs in regards to Project Euler will be in the same format, so hopefully it gets easier to see the bits you are looking for over time…

… Oh and by the way, I’d recommend giving a try of the first task on Project Euler first, and if you get stuck, have a look back here for some inspiration! Or if you have already completed it, I want to know your method of thinking, it could be a better solution!

Task Analysis

The first task I will be completing will be in regards to arithmetic series’, or more direct to the task:

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

Sounds pretty simple right? Well, one thing I have learned from programming, is the 4 P’s (Planning Prevents poor Performance) and that saying couldn’t be more true. So I went a bit in depth, and take a look at how I went around this problem.

Design

The Formula behind Arithmetic Series is this:
Summations
Where the total sum of the integers in a series is found by:
n = Total terms in a series
a1 = First term
an = Last Term

This formula can then be used for working out a “Rough Estimate” for our final answer (Important: You will see why it is only an estimate in a minute!)

Sum of multiples of 3 under 1000:

n = 1000/3 = 333.3 Therefore 333 terms.
a1 = 3
an = 333 * 3 = 999

Formula: (333(3 + 999)) / 2
= 166,833

Sum of multiples of 5 under 1000:

n = 1000/5 = 200 Therefore 199 terms (last term would equal 1000, rather than be less than)
a1 = 5
an = 199 * 5 = 995

Formula: (199(5 + 995)) / 2
= 99,500

The approximate answer:

Approximated Answer = 99,500 + 166,833 = 266, 333

The real answer:

The real answer is slightly different. Now this is because, what happens with common multiples? They aren’t added twice, eg: 15 isn’t added twice due to (5 * 3) and (3 * 5). This means that 15 will only be added once, and thus the real value will be less than 266, 333 (Sum of 5’s and 3’s).
Multiples
So get some water, write some notes, make a plan, and think of how exciting and fascinating this coding adventure really is (Of course)…

Development

For the development of my program to do this, I first chose a good IDE for a good language. I prefer C# so I’m writing in visual studio, however something like python isn’t that bad either…

Tip: Do some pseudo code first if you are completely stuck, or if you just want to be sure you are heading down the right path. At times throughout my blog, I will be doing Pseudo code, at other times… Naff it.

The Code Itself
Code

  1. I first of all initialised two variables which I would be using for this program. ‘i’ for the count controlled for loops and ‘sum’ for the total sum. Sum is also initialised at 0 in order to have a value added to it later.
  2. I then created a count controlled loop ( a for loop) which iterates several lines of code. The condition within the for loop on line 14 states that ‘i’ will equal 0, and while ‘i’ is less than 1000, it will be incremented by 1 each time the loop is run.
  3. I then created the selection statement (if statement) which is run off the single truth that if ‘i’ is divided by 5 or ( || ) 3 and it’s remainder is 0  (This is also called Modulus) in either statement, then the value of ‘i’ will be added to the variable of sum.
  4. However, if the integer ‘i’ has not got a modulus of 0 for 3 or 5, then the else statement on line 20 will be run, and the continue statement will carry on to the next iteration of the for loop, until ‘i’ is incremented to 1000, and the loop doesn’t run. It moves on.
  5. Finally, at the end, the sum is written within the console, and the program does not finish until the user has put in an input (in order to avoid the compiler from closing after being run).

Answer = 233,168

Evaluation

Overall, I couldn’t have thought of a much more simpler way to do this mathematical puzzle. Once the program had been run, I got an answer… and it was correct! I entered it on Project Euler, and now I’m thinking about my move for the second task!

It also had completed the puzzle under the one minute rule, where if the answer takes more than one minute to generate, your algorithm is inefficient. All methods of completion for all of the challenges are designed to be suitable for this rule.

Got a burning question? Ask it!
Done it differently? Show it!

Hope you enjoyed this,
Alpha. 🙂

Advertisements

3 thoughts on “Project Euler: Task 1

  1. Pingback: What is Computational Thinking? | Networking A Story

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s