Project Euler #1

So I’ve been threatening to do this basically since day 1…

To aid in my programming learning, I’m doing various programming puzzles… via Project Euler, Exercism.io, Coding Bat and others…

But I think another part of the learning process is explaining things, or sometimes at least why I did what I did…

So I want to discuss my solutions… Instead of boring you here with code, I’ll link my GitHub Gist, as well as my JSFiddle solutions.

First of all, the 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.

Now, first, the key word here is under. But we’ll get to that in a second.

At first, this looks like it can be solved with a simple loop, and really, for this exact problem, it can be, with little concern about cost. However, what if this was changed to 1 million, or 10 million, or 100 million…

Well, on most modern-day computers, looping through 1 to 1,000,000 takes about 2 seconds… 1 to 10,000,000 takes about 20 seconds… while 1 to 100,000,000 takes over 3 minutes… while 2 seconds is not horrendous, 20 seconds is bad, and 200 seconds is down right insufferable – at least from today’s web standards…

The solution for this is simple, and usually overlooked… Its taking a simple equation 3 times and your done.

Wait, what?!

All this is looking for is the sum of all multiples of 3 under 1000 (so 3+6+9+12…+996+999) and the sum of all multiples of 5 under 1000 (important to note since 1000 is divisible by 5, if we use it, we’ll get the wrong result) (so 5+10+15+20…+990+995). Now, if you remember your high school math, there was this equation that allows you to get the sum off all the consecutive integers that made up a number… so, for example, the sum of the consecutive integers for 10 is 1+2+3+4+5+6+7+8+9+10=55. The formula is n(n+1)/2… or 10(11)/2 >> 110/2 = 55. So having that, all we have to do is realize that the sum of 3+6+9+12 (quick example) = 30 is the same as (1+2+3+4)*3 >> 10 * 3…

Now, if that’s the case, then the sum of consecutive multiples of three would be 3 * ((n/3)(n/3+1) / 2), or in this case, we know that 999 is the last, and 333 is 1/3 of that, so 3 * 333 * 334 / 2 = 166833, and the same would be true of for 5 (5 * 199 * 200 / 2 = 99500). So we would think, at first glance, that our answer is 266333. However, we’d be wrong!

Wait, what?!

Well, we forgot one thing. In using this equation, every multiple of 15 (3×5) is being added in twice… once for the 3 side of it, and once for the five side of it… so all we have to do is subtract out one of them… so 15 * 66 * 67 / 2 = 33165… Now, if we take 166833 + 99500 - 33165 = 233168, which would be the exact same value our loop gives us…

So if we did this to get the results for 100,000,000 instead of 1000, we’d get our solution in under 1/100th of a second, vs 3 1/3 minutes, and at way fewer CPU cycles, which could be very important for some algorithms you write!

So that is my first foray into Project Euler, and the programming puzzles!

Young and Innocent -Elefante
Never B Flat, Sometimes B Sharp, Always B Natural

Starting to learn python…

So, since the tag line of my blog is “Music, Coding, Life, Learning & Linux”… I figure I’ll cover 3 of those topics with this… my learning to code in Python… On Linux!

I’m using Michael Kennedy’s “Explore Python Jumpstart by Building 10 Apps” (linked here!)

The 10 apps are:
Hello (you Pythonic) World
Guess that number game
Birthday countdown
Journal app and file I/O
Real-time weather client
LOLCat Factory App
Wizard Battle App
File Searcher App
Real Estate Analysis App

First, I really like this learning program…  Michael does a nice job of explaining things in easy chunks… and no, this is not an advertisement for the course, it’s just the course I chose when deciding to learn python (since I listen to his Talk Python to Me podcast)…

I’m currently through Real-time weather client, which is nice app, and uses web-scraping to pull information about the weather from a given location, and then pulling said information out of the ‘web-page’…

 

I found that really interesting, as one of the mini-programming projects I have wanted to do is pulling author story info from different fan sites to see if any of my favorite fan authors have written any new stories… So that is one of the first projects I’ll be writing about on here…

I don’t want to discuss the course too much, as it’s a paid course, and I don’t want to give away anything that I don’t have permission to give away, but I’ll probably be turning a lot of what I learn in this course and others into my own personal apps for my own needs, and those I’ll discuss and put on GitHub for anyone to peruse!

I’m also planning on discussing my FreeCodeCamp experience with Javascript (although I’ve been a JS programmer for a couple of years now, I want to write about the experience from start to finish), and also discussing my take on Project Euler and other coding challenges, my takes on my solutions and such…

Until next time!