The Defiant Coder

brb compiling

A Simple Problem with Natural Numbers

leave a comment »

I’m a huge fan of Project Euler. Ever since I stumbled upon the site, I’ve been trying my hand at each of the problems. I’ve only had the time to defeat two of the perplexing twists thus far, one of them being extremely simple and the other being a little more complicated. The best part about it isn’t solving the problems, but optimizing them using theory or programming tricks.

Problem

Find the sum of all the multiples of 3 or 5 below 1000.

Intuitively, a quick and dirty solution comes to mind: Check if a number is divisble by 3, check if a number is divisible by 5; if either of these conditions are true, add it to the total sum. Simple enough, right?

Your naive algorithm will look something like this:

#include "stdafx.h"
#include "stdio.h"
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{

 int totalSum=0;

 for (int i = 1; i < 1000; i++)
 {
   if (i % 3 == 0 || i % 5 == 0)
   {
    totalSum += i;
   }
 }
 cout << totalSum << endl;
 return 0;
}

VC++ Win32 Console Application | 20 lines | 0.78 msec execution time

Using this code, you’ll observe a runtime of 0.78 msec, and obtain the solution of 233168. The entire procedure did not even take a second, so why bother optimizing it? Because we can.

The first thing to note is the problem asks for numbers less than 1000, which means less than or equal to 999. In this simple function, we’re simultaneously checking if a number is divisible by 3 and 5, or n mod 3 = 0 OR n mod 5 = 0. Now, we can apply the corollary that if a number is divisible by 5 and 3, then it is also divisible by 15 (to put it simply, if n mod a = 0 and n mod b = 0, then n mod (ab) = 0). What this means is we can apply arithmetic progressive series to our function. This seems like a good idea because computationally speaking, addition and subtraction are less taxing than division and multiplication. If we sum all multiples of 3 to 1000, and all multiples of 5 to 1000, and then subtract any duplicates (ie. multiples of 15), we will arrive at our answer.

Doing so makes use of the following formulae:

arithmeticprogression

Where n is the number of numbers in the arithmetic progression, a1 is the first term, and an is the last term. d represents the common difference between terms. The problem becomes not knowing how many terms are in the series. However, we are able to solve for n as follows:

an = a1 + (n-1)d
1000 = 3 + 3(n-1)
(997/3 + 1) = n
333.333 = n

Since we’re talking about natural numbers, it is sufficient to take the integer floor of the series, and so we are left with 333 terms, and our sum is given by:

S = 333(3 + 999)/2 = 166833

What we also notice above is that the first term is also equal to the common difference. If we set a = d, then we arrive at:

S = n(2d + (n-1)d)/2 = 333(2*3 + (333-1)*3)/2 = 166833

As above. With this knowledge, we can combine the series where d = 5 and subtract the series where d = 15 to arrive at:

S_total = 333(2*3 + (333-1)*3)/2 + 200(2*5 + (200-1)*5)/2 - 66(2*15 + (66-1)*15)/2 = 166833 + 100500 - 33165 = 234168

At this point, you will notice that the solution is off by a factor of 1,000. Why does this happen? 1000 is a multiple of 5, and 15, and we used 1000 as our n rather than 999. The problem explicity asks for numbers below 1000, not equal to it, so we have to include it in our final calculation, or use n = 999 instead.

This new information can translate into code as follows:

#include "stdafx.h"
#include "stdio.h"
#include <iostream>
#include <math.h>

using namespace std;

double arprogression(double n, double d)
{
	return floor((n*(2*d + (n-1)*d))/2);
}

int _tmain(int argc, _TCHAR* argv[])
{
	double totalSum=0;
	totalSum = arprogression(333,3) + arprogression(200,5) -
                                         arprogression(66,15) - 1000;
	cout << totalSum << endl;
	return 0;
}

VC++ Win32 Console Application | 17 lines | 0.44 msec execution time

Although the execution time hasn`t changed noticeably, the second algorithm is much more elegant. Admittedly, we are cheating a little, as we’re supplying magic numbers for the total number of terms and the common difference. If we make this a general algorithm, we will have to find these parameters within the code, which will also take computation time. For the purposes of our problem, we have solved it both naively and slightly more elegantly by using arithmetic progression.

If you can think of an even more elegant way of solving the problem, feel free to comment!

-DC

Written by backendofforever

October 4, 2009 at 4:34 pm

On Defiance of Parents

leave a comment »

I think one of the most notable things that has helped me succeed and reach the point I’m at today has been defiance.

Now, you think, defiance? Being a rebel? But why?

Let me put it this way. A young teenager living in suburbia with his traditional,  “must sit down for every meal” parents is bound – no, must – become defiant. He will test his parents again and again. In doing so, he’ll mold his mind in such a way that he’s now able to think outside the box and into his dreams – the things he really wants. He may be shunned for doing so, but it’s the only way to obtain happiness. If you follow the path set out by someone else, you can’t truly achieve what it is you desire. You’ll make your parents happy, but you’ll sell yourself short, which reinforces my point: certainly some degree of defiance is needed to succeed in the life of Generation Y.

Growing up with traditional European parents has tried my patience in every way. Their demands for respect were quickly dismissed and met with equal force back. A day where I would actually want to sit at the dinner table and tell them how my school day went was as rare as real ingredients are in McDonald’s Chicken McNuggets. I’d remain quiet for the entire hour, my mother often sneaking in a, “How was your day?” to make sure I hadn’t been ignoring her, at the very least.

Perhaps my logic is flawed in that not all parents are like mine, and not all Gen Ys had poor relationships with their parents growing up. I often wonder if it’s more of a European ideology. They want their kids to grow up as they did, and marry in the same racial and religious background. Straying from this is a mortal sin, and although they may often say, “Do what makes you happy,” what they really mean is, “You better marry an Italian girl if you want your share of inheritance.”

Well, to that, I defiantly say: At the end of the day, money is money, and happiness cannot be purchased off of a shelf.

But really, are all European parents like mine were as I grew up?

-DC

Written by backendofforever

October 4, 2009 at 11:07 am

An Introduction

leave a comment »

I can’t believe WordPress expects you to drop $20 USD a year to be able to customize your CSS. Wouldn’t you rather just direct that $20 to an inexpensive webhost and be able to customize everything, rather than just CSS? Yeah, me too. But for now, I’m going with the cheaper solution – a standard theme that surely has been seen before on at least 1,500 other blogs.

Allow me to introduce myself. I’m twenty-three and stuck in suburban Ontario, as I have been all my life. I live west of downtown Toronto, about 15 minutes out, and drive pretty much everywhere.

I’m a coder. I program for a living as a full-time Programmer/Analyst. Although my job is painfully boring at times, I really enjoy watching my code unfold in front of me and solve dozens of problems. I don’t really fit the programmer stereotype (i.e. bald, angry, large, and in charge) , but I am slim, do have bad vision, am always ravenously hungry, and no, I will not fix your computer. I don’t even fix my mother’s computer anymore. It sometimes makes me wish I didn’t know as much as I do about technology, kinda like how the citizens of NYC expect Spider-Man to put the Green Goblin to rest. Not to throw a cliche at you, but with great power comes great responsibility, I guess?

But I digress. I also program for fun. And I love math. I love psychology and analyzing social scenarios. I can sit in a local cafe for hours just staring at people in the distance, creating my own story for each of them. I’ll look to my left and see a young, attractive woman sipping on Earl Grey, her nose buried in the center of Robertson Davies’ The Rebel Angels. To my right, a rowdy gentleman yells at his disagreeable associate over his iPhone. I sit calmly at my table for two, smiling to myself as I write my next blog entry. I’m not blogging in public right now, but there’s something about blogging in a public place which feels so invigorating. I’m a lot more descriptive and my writing style changes to a much more immersed version. Somehow.

I’ll have three types of entries in this blog: Code-related, Life and career-related, and other stories from moments in my life. I think this is a fair introduction, so stay tuned for more.

-DC

Written by backendofforever

October 3, 2009 at 11:26 am

Posted in Uncategorized

Tagged with , , ,

Hello world!

with one comment

WordPress, you got it all wrong, I think what you meant was:

cout << "Hello World!" << endl;

Written by backendofforever

October 3, 2009 at 11:20 am

Posted in Uncategorized