June 21, 2010

Problem Submission

Every career opportunity I am interested in requires knowledge of Java. I don't work with compiled languages often, they're not required for my work or consulting. My IDE of choice is a text editor that remembers my indent level and warns of lonely brackets.

I downloaded Eclipse and dug in this past weekend. For motivation and direction, I signed up for Project Euler. I was quickly reminded of my eight year absence from academia. The first problem seemed easy:

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.

In short, take the sum of all powers of three and five, and subtract powers of fifteen, for all values less than one thousand. My solution:

int x, sum = 0;

for ( x = 1; x <= 333; x++ ) {
sum += x * 3;

for ( x = 1; x <= 199; x++ ) {
sum += x * 5;

for ( x = 1; x <= 66; x++ ) {
sum -= x * 15;


The above performs admirably enough with the small numbers provided, and I doubt moving up to 64-bit integers would noticeably increase run time. However, I was quickly disillusioned of its elegance. When you submit an answer on the Project Euler site you are given the option to join the solution discussion; an eye opener to say the least. One solution reminded me that I do not often tackle problems of this nature. I failed to recognize, or perhaps forgot, that a for loop is the equivalent of an arithmetic series.

int sum = 999 * (1 + 333) / 2 + 995 * (1 + 199) / 2 - 990 * (1 + 66) / 2;


Is the equivalent solution, yikes! I similarly beat the second problem into submission with brute force, thinking that Fibonacci numbers would not be so easily abbreviated. Despite reaching the correct answer, I learned that the sequence increases at roughly the golden ratio (commonly: phi). I regained some confidence with the solution to the third and last problem I tackled this weekend, which was roughly the same as other answers. Looking forward, as I intend to keep at Project Euler as a way to familiarize myself with Java, most of the problems involve primes.

No comments: