Problem 338 (3)

I am still trying to solve this problem, but there isn’t much progress. My current implementation of function F bases on the following observation:

F(w, h) <= the number of different d for which d | w and (d – 1 or d + 1) | h is true, where a | b denotes that a divides b with no remainder. There is no equality sign because I have no idea how to check if a particular solution is not a one already found.

My current implementation:

private static int F(int w, int h) {

if ((w & 1) == 1 && (h & 1) == 1) { //both are odd

return 0;

}
int result = 0;
Set<Integer> set = new HashSet<Integer>();
set.add(w);
set.add(h);
for (int d = 2; d <= w; d++) {

if (w % d == 0 && h % (d-1) == 0) {

if (set.add(w – w / d)) { //if not in the set

set.add(h *  d / (d – 1)); // (w*h) / (w – w/d)
result++;

}

}

}
for (int d = 2; d <= h; d++) {

if (h % d == 0 && w % (d-1) == 0) {

if (set.add(h – h / d)) {

set.add(w *  d / (d – 1));
result++;

}

}

}
return result;

}

I think I need some break from the Project Euler and maybe even programming for few days…

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 12, 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: