Diversions: project Euler

I’ve set the stage to enetertain myself doing some programming over the next few days. Call it a method of procrastination, I could have better things to do. Like begin analyzining offline data looking for photons coming from {\pi^0} decay (what is that??)

I have Ubuntu 11.04 which I installed yesterday. It comes with g++ and python by default. Im an old c++ user, so this comes as a relief. Though I would like to learn python, and in particular, Haskell, so I installed that as well. I have high hopes with haskell as I am quiet impressed with its functional programming paradigm. I feel this is quiet close to the requirements of physicists and mathematicians, though I’d have to know more to form an opinion about it.

As with this Latex document (which will be converted to HTML and put up on my blog thanks to Luca Travesan’s Python Script) I am doing all my editing in vim. So its a convenient thing, I browse the web, where I am looking for text-heavy content anyway, on lynx. It might seem surprising but all the little queries I have about linux n00bs and syntax problems are handled and asnwered pretty well on a text based browser. Heck, I can even check gmail, though I havent found a way of updating wordpress from that. Hmm. Interesting.

So the thing that is nice about all this is that I can work without any meaningless distractions, advertisements, images etc. Now time to get started.

Problem 1: This was was easy, I did a simple brute force technique and got the answer. Euler1.cpp:

#include <iostream>
using namespace std;

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

Now Im thinking if there is a way of making this more efficient. Surely, 148k+ have solved this problem and more than half of them must have a conscience that prevents them from sleeping at night with this excuse of a solution. Well, it is a solution in all its dignity, no denying that, but let’s see….

I can reduce the number of iterations by introducing a closed formula for additions by multiples of 3, 5 etc, then iterating and subtracting from the sum, all the common numbers which got added twice. I can remove that iteration step as well by introducing a closed formula for numbers that are common multiples of 3 and five, in short, multiples of fifteen. So the basic algorithm is this, add multiples of 3 , add multiples of 5, subtract multiples of 15.

So looking for \displaystyle (3+6+9 \cdots+999)+(5+10+15+\cdots+995)-(15+30+45+\cdots + 990)

euler1a.cpp

#include <iostream>
using namespace std;
int main() {
int k=1000, j=k/3,l=k/5,m=k/15;
 k=3*(j*(j+1)/2)+5*(l*(l-1)/2)-15*(m*(m+1)/2);
 cout<<k<<endl;
return 0; }

I am not in the habit of using int main() and return, and prefer to use void main() whenever I can, but for some reason the compiler gives an error that I cannot debug from the ubuntu forums. Ill give this problem a rest for now.

That being done, let me try to implement this in Haskell. For now, I dont know what I hope to accomplish except to learn Haskell’s syntax.This was a basic problem which could be done without performing iterations, atleast that is what I’ve done to the best of my knowledge. I know there are a plethora of solutions to these problems out there, but I think that I’ll make a 5 question rule. That I would not compare my solutions to those by others until I have solved five further problems in this project. If I stick to my timeline this should mean I should post a comparision five days later. Hmm.

As a final thought, to make this problem more general:

Sum all multiples of {m} and {n} from {1} to {k}

The simple case would be when both {m} and {n} are co-prime, i.e they have no prime factors common, then the sum would be as above:

\displaystyle  S=\lfloor\frac{k}{n} \rfloor \left( \lfloor\frac{k}{n} \rfloor+1\right) +\lfloor\frac{k}{m} \rfloor \left( \lfloor\frac{k}{m} \rfloor+1\right)-\lfloor\frac{k}{mn} \rfloor \left( \lfloor\frac{k}{mn} \rfloor+1\right) \ \ \ \ \ (1)

In the general case, when {m} and {n} can be any two numbers with some prime factors common, say {\{p_1,\cdots ,p_k\}} then we just replace {mn} by {p_1p_2\cdots p_k}.

Now, there’s a lot of fuss Ive made about this problem. I am quiet pleased myself in the this one hour of working. Here’s a couple of things I hoped to accomplish and did, many of them occured while I was working:

  • Installed ubuntu
  • Would there be a cool way to work just in terminal so I dont have to touch the mouse and be interrupted? I dicovered vim editor and lynx. The early drawback has been the painful navigation structure. But I trust that it’ll pay off in the future. For the moment I’m a bit squeaky with the basics and havent been able to commit the nagivation keys to memory. Ill be learning more as I use it more.
  • Ran a succesful C++ program without error after a long time.
  • Installed haskell and ran my first succesful Haskell program
  • Set up a blog and downloaded a cool script that smiply converts latex documents to html. It would have been cooler though if wordpress had mathjax or mathml enabled as the script converts all the mathematical formulas into jpeg images. Blogspot does have this facility, but I do not use blogspot for a variety of reasons.

Well, that’s it for the day. Got my feet wet. Ill be doing one problem from project euler each day from now on. Once Im finished uploading this on the web I’ll get to finish Chapter One of Concrete Mathematics by Knuth and Gang. Have to do the exercises, and the second chapter, on sums, seems quiet interesting. Hopefully Ill be done with most of it today.

PS: I would link to codepad as a good online compiler to quickly check any code you see posted online for verification.

About these ads

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: