Problem 338

After solving about 20 of problems from Project Euler I have decided to choose more difficult problem. Maybe it is a bit too difficult, but yes – I have chosen the most difficult problem available in Project Euler.

I have already written first implementation of functions F and G, which has taken me almost 4 hours today morning. Both functions work correctly and return correct values, but they are not well optimized. Even though G(10) is  calculated almost immediately and G(10^3) in about two seconds, calculation of G(10^4) takes 31 minutes and I am not even going to try with G(10^5).

My current implementation of function F uses two separate loops with a lot of divisions and a set of edges to avoid repetitions. This implementation cannot be used for final solution, but it gives correct answers so I am able to ensure that my future implementation works correctly. More details may be found here. I will describe everything more precisely when I solve the problem (hopefully it will happen).

I have spot some connections between the result of F and divisors of edges given. I am not quite sure if I should consider prime divisors and their exponents (e.g. 12 = 2^2 * 3) or maybe just a total number of divisors. The first approach seems to be more promising so now I will focus on this.

I have already implemented some structure for divisors finding – I have used the code from the problem 12, which I will describe later.

At this point I am sure that F(1, a) returns 1 – a & 1 for any a > 2, but I don’t think that this optimization will be enough to change anything…

About Jaroslaw Pawlak

I have done MSci in Computer Science at King’s College London and currently work as Software Engineer specialising in Java. I spend most of my time in front of computer improving my programming (and other) skills or just relaxing with a good game. I also train some sports but at the moment I am not a member of any club. I love cycling and volleyball, but I have also played a lot of football, tennis and trained martial arts.

Posted on June 8, 2011, in Project Euler. Bookmark the permalink. Leave a comment.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: