Problem 338 (4)

I was wondering about swapping the order of computations i.e. first looking for some edge 1 ≤ x ≤ √wh and then, having x, looking for such d that d | w and d+1 | h or d-1 | h.

I have assumed that h ≥ w. There are generally two possibilities:

1. d | h and (d-1) | w, then:

one edge = h * (d-1) / d
second edge = w * d / (d-1)

2. d | h and (d+1) | w, then:

one edge = w * d / (d+1)
second edge = h * (d+1) / d

So now x can be one of those four edges. This gives d = h / (h-x), d = x / (x – w), d = x / (w – x) or d = h / (x – h). This can be simplified to (h – x) | h or (w – x) | x. Also w*h must be divisible by x. This change decreased computation time: G(1000) has been calculated in about 800ms instead of 1600ms, while G(10^4) in 12 minutes instead of 31. I could optimize it further by doing some calculations on prime numbers and choosing only those x which are divisors of w*h, but firstly I have no idea how to do this and secondly, it will still be far from calculating the answer for G(10^12).

private static int F(int w, int h) { // h >= w

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

return 0;

} else if (h < w) {

return F(h, w);

}
int result = 0;
for (int x = 1; x * x <= w * h; x++) {

if (w * h % x != 0 || x == w) {

continue;

}
if (h % (h – x) == 0 || x % (x – w) == 0) {

result++;

}

}
return result;

}

By the way, I will not be 41st who solved this problem… Someone has recently done it before me… They must have found my blog and run my code on the super-computer!

But seriously, key to the problem must lie in the function G. It invokes function F (1 + 2 + 3 + … + N) times, what for N = 10^12 gives 10^12 * (1 + 10^12) / 2 ≈ 10^24 invocations. If average computation time of function F was 1ns (now the smallest is about 400ns), it would give 31,709,791 years. It’s… quite a lot…

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 13, 2011, in Project Euler. Bookmark the permalink. 6 Comments.

  1. I’m also stuck at about this point. My function F works fine, and is reasonably fast, but I can’t think of any way of computing G(10^12) with it in less than 10^24 calls. I guess tomorrow I’ll start looking for patterns in F.

  2. We don’t need to find pattern for any F. After having a short break I figured out that G(N) = G(N-1) + ( F(1, N) + F(2, N) + F(3,N) + … + F(N, N) ). I am thinking now how to calculate this sum, but from the other side. Having N in F(A, N) it may be enough to find how many different As give a rectangle of particular sizes. I don’t know how to explain it better – maybe it’s because I don’t know what exactly I’m looking for :)

  3. I got to this point and got stuck, too!

    Not sure it helps much, but in your formula above, when N is prime F(1,N)+…+F(N,N) is ((N-1)/2)

    I couldn’t see any other useful patterns. Searching on the net there are some cryptic hints (in Japanese) that there is an O(N^2/3) algorithm to solve this. This also matches the suggestion on the Project Euler forum that the puzzle is solvable in 10-20 seconds processing time. A conclusion from that seems to be that there is a way to do this that does not involve calculating each value of G for 1..N

    Adrian

  4. Thanks for that. When N is prime there are two cases – either second argument (let’s say A) is odd (so F returns 0 what I described earlier) or there exists exactly one such D that D | N and (D+1) | A. D = 1. But there are still too many other cases (I mean when N is not prime).

    And about using G with different argument, in calculations of G – for sure it will not be a solution, but it may suggest another idea. It’s like implementing function F. It’s probably useless for the final solution, but it gives another possibilities. I just think that any progress is useful ;)

  1. Pingback: Python:Project Euler Number 338 – IT Sprite

  2. Pingback: Project Euler Problem 338 - MathHub

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: