Project Euler 142: Perfect Square Collection

Project Euler 142: Perfect Square Collection

Written by on 30 March 2013

Topics: Project Euler

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.

7 Comments For This Post I'd Love to Hear Yours!

  1. Scott Dennison says:

    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

  2. Kristian says:

    Hi Scott

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

  3. Jean-Marie Hachey says:

    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)

  4. Karl Keller says:

    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

  5. Kristian says:

    That is fixed, thanks for noticing.

  6. Selenae says:

    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) ?

  7. Akhil Dureja says:

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

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.