Project Euler Problem 9: Special Pythagorean triplet

• You may immediately

      return a * b * c;
  

  as soon as the values are found.

• The loop

      for (int cValue= 1; cValue<=value/2; cValue++)
  

  is superfluous: you already have a and b, and you know that \$a+b+c\$ must be equal to value, so

      cValue = value - aValue - bValue;
  

  suffices.

• Thou shalt not brute force.

  Recall that the Pythagorean triple \$a, b, c: a^2 + b^2 = c^2\$ can be expressed as $$a = k(u^2 - v^2)\\ b = 2kuv\\ c = k(u^2 + v^2)$$ with coprime \$u,v\$. Since they must add up to a particular value \$N\$ (in your case, 1000), conclude that \$2k(u^2 + uv) = N\$, or \$v = \dfrac{N}{2ku} - u\$.

We know that sides must be positive, so we have

• \$u > v \rightarrow u > \dfrac{N}{2ku} - u \rightarrow u > \sqrt{\dfrac{N}{4k}}\$, and

• \$v > 0 \rightarrow \dfrac{N}{2ku} - u > 0 \rightarrow u < \sqrt{\dfrac{N}{2k}}\$

  Now loop over the range [sqrt(125), sqrt(500)] looking or the divisors of 500 (the range is as small as [11 .. 22], and the only divisor is 20). I intentionally will not explain how to recover \$a, b, c\$ once the divisor is found. It is pretty straightforward.

Performance errors

You have implemented some sort of a brute force solution which makes it extremely inefficient, this might work for a few more problems at Project Euler but pretty soon you will realize you need to put some thought in your code. There are few factors that damage your performance:

1. You have 3 for loops that makes your algorithm time complexity which in most cases is avoidable.

2. The fact that you have a for loop for 'c' doesn't makes any sense. That suggests that you haven't run a debugger even once on your program or haven't payed attention to what's going on, because there are some obvious problems there even in your first iteration.

3. You have to manually check if aValue<bValue && bValue<cValue is true, if it was always true you would've had lesser iterations.

4. Your method IsPythagoreanTriplet is good as it is, but it's still not optimal because it requires you to know all 3 parameters, knowing 2 is enough.

5. Even after you find the correct number, you keep on iterating instead of breaking or instantly returning from your loop/method respectively. This will not only remove the extra if statements that you're unhappy with but will improve performance slightly.

Fixing the points above is pretty much equivalent to writing the program anew.

Let's start by writing a faster IsPythagoreanTriplet().

This is what the Pythagorean formula looks like: .

We can make some points about how our program functions currently.

1. 'a' and 'b' can be only integers.
2. The desired sum is also an integer.

From that we can conclude that 'c' must also be an integer. Here is how the formula would look like if we were to find 'c':

In order for our conclusion to be correct, must be a square number.

Following that logic we can write a simple method to determine if is a square number and if that's the case than we have a triplet:

private static bool IsPythagoreanTriplet(long a, long b)
{
    double rawResult = Math.Sqrt(a * a + b * b);
    return rawResult == (long) rawResult;
}

That's alright but it would be also handy if we can somehow return the already calculated result for 'c' (if the numbers can form a triplet), just to avoid calculating it again in outside this method, we can do something like this:

private static bool IsPythagoreanTriplet(long a, long b, out long c)
{
    double rawResult = Math.Sqrt(a * a + b * b);
    long roundedResult = (long) rawResult;
    if (rawResult == roundedResult)
    {
        c = roundedResult;
        return true;
    }
    c = default(long);
    return false;        
}

That seems pretty good let's move on.

Faster and simpler GetProductOfPythagoreanTripletThatSumTo().

Goals:

1. Use less than 3 loops.
2. Avoid sets that don't make sense. 3.Get rid of the unnecessary parameter check (aValue<bValue && bValue<cValue).
3. Quit iterating once we got the desired result.

Fixing point 1 will also fix point 2, so let's start with that.

As I stated in my Performance errors section, I believe you would've noticed some weird sets appearing if you did ran a debugger, this is something that I highly emphasize on.

You are looking for 'c' with a for loop, while you can instantly obtain it using the formula. You're effectively looking for multiple solutions to the same operation, are there multiple answers to 2 + 2 = x? You don't start counting from 1 upwards and test every single number on your way, you simply add the two numbers to get the result.

Moving on to point 3. We can fix that by enforcing this rule in our for loops.

In order for this rule to be true we need to verify that:

b >= a + 1

Notice that this is our only constraint here, as we don't care about 'c' as we are going to form it as a sum of 'a' + 'b' which instantly makes it at least 'a' bigger than 'b'.

This is rather simple to implement as we are going to set this our base value in the for loop.

Lastly fixing point 4 is probably the easiest. We just gonna return value at the moment we find the correct result.

With all of that in mind we can write something like this:

private static long GetProductOfPythagoreanTripletThatSumTo(int desiredSum)
{
    for (long a = 1; a < desiredSum / 2; a++)
    {
        for (long b = a + 1; b <= desiredSum / 2; b++)
        {
            long c;
            if (IsPythagoreanTriplet(a, b, out c) && a + b + c == desiredSum)
            {
                return a * b * c;
            }
        }
    }
    return 0;
}

The problem poses two equations :

• a^2 + b^2 = c^2
• a+b+c=1000

If we quickly work with this, we get c=1000-a-b. Doing this will remove the need for the ValuesSumTo method, since c is dependent on a and b. Meaning we just removed one for loop from your code.

Now, still following the original problem, we know that a<b<c. So, in the for nested loops, we could make aValue increment until we reach b's value!

for (int bValue = 1; aValue <=value/2; aValue++)
{
    for (int aValue = 1; bValue; bValue++)
    {
            var cValue = 1000-aValue-bValue;
            if (ValuesSumTo(value,aValue,bValue,cValue) && IsPythagoreanTriplet(aValue,bValue,cValue) && aValue<bValue && bValue<cValue)
            {
                a = aValue;
                b = bValue;
                c = cValue;
                valuesFound = true;
            }
        }
        if (valuesFound)
            break;
    }
}

Another problem I see is that you use break when you don't really need to. Your condition to break is right after the assignation of your valuesFound assignation, so why not just break at that point. And right after your break, you return the values. So you should return the product right away!

Next, instead of having a and aValue variables, let's try to keep it simple with only a .

static long GetProductOfPythagoreanTripletsThatSumTo(int value)
{
    bool valuesFound = false;
    for (int b = 0; b <= value/2; b++)
    {
        for (int a = 0; a < b; a++)
        { 
            var c = value - a - b;
            if (IsPythagoreanTriplet(a,b,c))
            {
                return a*b*c;
            }
        }
    }

    throw new InvalidOperationException("@value doesn't allow a pythagorean triplet that works");
}

Also, you notice we removed two conditions from your code : && aValue<bValue && bValue<cValue.

The first one is now in the second for loop and the third one doesn't need to be checked since c will always be greater than b (if you don't believe me, do the maths :p)

We still have one problem. What if it doesn't work? What if there's no pythagorean triplet that fits with the value provided? Anyway, my code doesn't compile because of this. We'll throw an Exception if something doesn't work.

Finally, I don't see how your code compiles since value is a reserved keyword. If you really want to use value, you need to add @ in front. But I recommend changing that variable name to something more meaningful like valuesSum.

I know code dominate answers are discouraged
But rather than loop all can increment intelligently
The larger side dominates so increment it until over
Integer math is faster

public static void ABC2()
{
    // a + b + c = 1000
    // aa + bb = cc 
    // aa + bb = (1000 - a - b)^2
    int a = 1, b = 490, aabb, cc, count = 0;
    while (true)
    {
        if (a > b)
            break;
        count++;
        aabb = a * a + b * b;
        cc = (1000 - a - b) * (1000 - a - b);
        if (aabb < cc)
        {
            b++;
        }
        else if (aabb > cc)
        {
            b--;
            a++;
        }
        else
            break;
    }
    Debug.WriteLine("a {0} b {1} c {2} count {3}", a, b, 1000 - a - b, count);
}

public static void ABC()
{
    // a + b + c = 1000
    // aa + bb = cc 
    // c = sqrt(aa + bb) 
    // can set a = b and solve for a starting point
    double a = 292,  b = 292, c, abc;
    int count = 0;

    while(true)
    {
        count++;
        c = Math.Sqrt(a * a + b * b);
        abc = a + b + c;
        if (abc > 1000)
            a--;
        else if (abc < 1000)
            b++;
        else
            break;
    }
    Debug.WriteLine("a {0} b {1} c {2} count {3}", a, b, c, count);

    //don't have a starting point 
    //even if all are same length then at least 333 for the long side
    a = 1; b = 300;
    count = 0;
    while (true)
    {
        count++;
        c = Math.Sqrt(a * a + b * b);
        abc = a + b + c;
        if (abc < 1000)
        {
            b++;
        }
        else if (abc > 1000)
        {
            b--;
            a++;
        }
        else
            break;
    }
    Debug.WriteLine("a {0} b {1} c {2} count {3}", a, b, c, count);
}