Older blog entries for maragato (starting at number 25)

Euler 5

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #5 statement is –

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

My first attempt was using brute force, but it didn’t go very well. It took a considerable amount of time, so I decided to think about the problem a bit. In the end, it boils down to the a relation between the lesser common multiplier and the greater common divisor.

1
2
3
4
5
6
7
8
9
10
11
12

def gcd(a, b):
        if b== 0: return a
        return gcd(b, a % b)
 
def lcm(a, b):
        return a * b / gcd(a, b)
 
if __name__ == "__main__":
        b = 2
        for i in range(3,20):
                b = lcm(b, i)
        print b

While the original code took several seconds before I killed it, this runs in 0.015s.

Syndicated 2010-08-03 17:30:36 from Roberto Teixeira's blog

Because acme hurt my pride[1] by making fun of the still inexisting KDE interface for Apt, I've started creating KApt as a kpart last night. Quite straightforward actually. It already can query packages and update package lists. I just forgot to put it on CVS, but I'll do it tonight.

[1] it's a joke, Arnaldo :-)

We'll use a modified version of libapt in Kalypso. That's decided and I am working on it. The RPM part is working fine since the Apt version we're baseing ours on was Conectiva's Apt 0.3.19cnc55. The problem is that Debian changed its libapt at some time in the past.

Also, when porting to RPM, some of the deb code stopped working so I have to fix that. I installed a Debian system on a VMware box and now I'm working on getting our libapt working on Debian as well as RPM-based distros.

As a side note, Conectiva Apt was not ready to be compiled with gcc3 which gave me a good headache.

I've just learned that Apt's author has not integrated the rpm port into the main tree yet. This is a problem, as I will no longer be able to use libapt as a backend for the kde classes. Two bad. I'll be discussing with some people today what is the best approach right now. In the meantime I'm redoing the classes using librpm as the backend just in case.

I'm back updating Advogato. I'm now working in some classes to handle binary packages (DEP and RPM) to work on the new kde installer.

As I side note I've been thinking about Kivio for some time. It's a nice application but it's also a useless application the way it is now in KOffice. It's great for TheKompany.com but not so great for us. I'm thinking about doing some work on Kivio to make it usable in KOffice, but I'm affraid TheKompany will cry.

I give up! You win, Ark, you win...

Last night I realised I cannot defeat Ark. Seriously, Ark is so full of bugs and hacks that I can no longer fix it. When I took over Ark because the former maintainer simply disappeared from the net without a trace, I read on the TODO file "this thing is in serious need of a total reengineering" and "hacks on top of hacks on top of hacks". I knew it was going to be tough, but I did not know how much...

So, last night, I launched the kapptemplate script and began writing KArchiver from scratch. KArchiver will replace Ark as KDE archive utility. I am getting way too many bug reports on Ark. Bugs that I cannot fix without rewriting large parts of the code, so I think coding something from scratch is the best option right now.

So, that's it. If you use Ark and find a bug, please report it anyway as I will fix what is simple, and if it's not a simple fix, at least it might give me some ideas for the new code. Also, please post in Ark your wishlists for KArchiver. If you don't know it already, the Right Place(tm) to report bugs and wishes is here.

First let me tell you that Brasil Telecomm rules. They installed my ADSL connection two days ago, while the "promise" was to install early next week. Good work guys! :-)

Another milestone today was the fact that this is the first time ever that I managed to log into my advogato account on the very first attempt! (I always had to try two or three times to remember this bloody password! I'm going to change it now :)

Well, I spent most of the night porting kojima's libraptor to KDE. He insisted that I used his own library instead of porting, but the new lib is much more KDE-friendly now... also, he used a lot of STL, something that we are not very fond of in KDE.

My new box is working fine. It's a PIII 900MHz. I wish I could have afforded that juicy Athlon 1.2GHz but money is short currently :-/

The only thing that did not work was that bloody PCTel modem, but this is not a real problem since Brasil Telecomm has promissed me they'll install my ADSL connection early next week.

Meanwhile, I am back at porting Synaptic to KDE. I am also modifying it now to allow me to try an idea I have had for a KDE installer/upgrader:

Synaptic theoretically would work in any RPM- and DEP-based distribution, covering almost every big distribution in the market (Slackware would be out, I guess). When the user launches the Synaptic-base KDE installer, it will check which distro the user is running and send this information to a server (something like install.kde.org). In the server, a simple daemon responds with the appropriate Apt package source corresponding to the user distro. This would have the great advantage of freeing our bandwidth, since we would point to a source from the distro vendor. Also, it would allow distributions to more easily update their own packages everytime they need to do so.

I haven't posted for quite some time but this doesn't mean I haven't done much :-) Things at KDE development are begining to settle as we approach the release date (25 Feb 2002). We are not yet in "hard freeze" but new features are begining to give space to bugfixes and performance enhancements.

The day KDE 2.2.2 was launched I was interviewed by a newspaper called Estado de Minas. Pretty cool even though the questions were somewhat dull. The downsize was that I had to swallow all the jokes I had done about Marcelo Tosatti (the new kernel 2.4 mantainer) when he had a series of interviews and photo sessions. Of course, just as the photographer took pictures of me, Marcelo passed by... Murphy's Law I guess.

Oh, let me tell you that objprelinking doesn't work anymore with Conectiva Linux. I don't know why, but it seems to have no effect on performance after our binutils package was modified. Helio (our KDE packager) is trying to figure out what it wrong.

I am going to buy a new box today. Let's see if this makes it possible to actually code at home (it's frustrating to wait 5 minutes to compile after a one line change in code).

I've improved yesterday's patch quite a bit today. I dreamed of the fix last night... weird. Anyway, it now works great and Rodrigo almost got convinced to change from Pine to Kmail today, guess I'm almost there ;-)