Project Euler 142: Perfect Square Collection

Problem 142 of Project Euler seems to be one in the easier end, at least if you aren’t afraid of a little algebra. The problem reads

Find the smallest x + y + z with integers x > y > z > 0 such that x + y, x – y, x + z, x – z, y + z, y – z are all perfect squares.

I don’t think we can manage to iterate over all possible values of x, y and z. So let us see if we can use the relations that has to be squares to something. We will just name them such that

Then we can write the following relations

So from this it follows that if we can find a, c and d. Then we can deduce the rest of the numbers with the above relations. That means instead of iterating over x,y,z we can now iterate over a,c and d, and thereby ensure that half of our relations are satisfied from the beginning.

Based on a-f we can find x,y and z as

There is an additional little trick to this. We can see that e+f has to be even in order to be divisible by 2. That means they must have the same parity. Looking at the relations that f = a-c and e = a-d, it follows that c and d must have the same parity. So we can cut away some values of d when we iterate.
I implemented it very simply by

long a, b, c, d, e, f;
bool solved = false;
long result = 0;

for (long i = 4; !solved; i++) {
    a = i * i;
    for (long j = 3; j < i && !solved; j++) {
        c = j * j;
        f = a - c;
        if (f <= 0 || !IsSquare(f)) continue;

        long kstart = (j % 2 == 1) ? 1 : 2;
        for (long k = kstart; k < j; k += 2) {
            d = k * k;
            e = a - d;
            b = c - e;

            if (b <= 0 || e <= 0 || !IsSquare(b) || !IsSquare(e)) continue;

            long x = (d + c) / 2;
            long y = (e + f) / 2;
            long z = (c - d) / 2;

            result = x + y + z;
            solved = true;
            break;
        }
    }
}

This solves the problem in just under 15 ms on my machine.

You can find the source code here.

Posted by Kristian

7 comments

Scott Dennison

I’m still trying to wrap my head around this one, but I think you have a problem with the LaTeX underneath “Then we can write the following relations”
f = y – z = (x + y) – (x – z) = a – c
when it should read, if I am not mistaken.
f = y – z = (x + y) – (x + z) = a – c

Hi Scott

You are absolutely right. Thanks for noticing that. It is now corrected in the post.

Jean-Marie Hachey

Table 1
The five smallest Perfect Square Collection.
[Re: Project Euler 142: Perfect Square Collection]

http://img248.imageshack.us/img248/2011/pe142table1.jpg

___

Figure 1
Evolution of x, y and z in the first five series.
[Re: Project Euler 142: Perfect Square Collection]

http://img849.imageshack.us/img849/6881/pe142fig1.jpg

As we can see in Figure 1, x increases steadily,
while y and z pass through a maximum and then decrease.
Sums increase continuously.

___

Sources:
1) Project Euler 142
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem142.cs
2) Microsoft Visual C# 2010 Express
3) Microsoft Office Excel (2007)

Karl Keller

Just a typo for “z” in your problem analysis :

Based on a-f we can find x,y and z as
x = (a + b)/2
y = (e + f)/2
x = (c + d)/2 ” << this should be z = ( c – d ) / 2

That is fixed, thanks for noticing.

How do you know that the first result found by this algorithm will minimize x+y+z?
Minimizing a doesn’t necessarily minimize (x+y+z = a + c/2 + d/2)

I can see that a > c > d, so the limits for j and k loops make sense.
Shouldn’t you keep searching i while a < (smallest solution found so far) ?

Akhil Dureja

It should be z=(c-d)/2

Leave a Reply