Project Euler 143: Investigating the Torricelli point of a triangle

Project Euler 143: Investigating the Torricelli point of a triangle

Written by on 6 April 2013

Topics: Project Euler

Problem 143 of Project Euler is a notorious problem. Notorious for having the fewest correct answers per time it has been released. If you sort by number of solvers, you will see a pretty good correlation between problem number and place on that list. However, this problem is moved quite a bit down that list. The problem reads

Let ABC be a triangle with all interior angles being less than 120 degrees. Let X be any point inside the triangle and let XA = p, XB = q, and XC = r.

Fermat challenged Torricelli to find the position of X such that p + q + r was minimised.

Torricelli was able to prove that if equilateral triangles AOB, BNC and AMC are constructed on each side of triangle ABC, the circumscribed circles of AOB, BNC, and AMC will intersect at a single point, T, inside the triangle. Moreover he proved that T, called the Torricelli/Fermat point, minimises p + q + r. Even more remarkable, it can be shown that when the sum is minimised, AN = BM = CO = p + q + r and that AN, BM and CO also intersect at T.

If the sum is minimised and a, b, c, p, q and r are all positive integers we shall call triangle ABC a Torricelli triangle. For example, a = 399, b = 455, c = 511 is an example of a Torricelli triangle, with p + q + r = 784.

Find the sum of all distinct values of p + q + r ≤ 120000 for Torricelli triangles.

After solving it, I can see why there are so few other people who have solved it. Because it was really difficult, and took a whole lot of research for me. My research into this topic lead me through something about the Fermat point on Wikipedia, which was interesting, but not really that useful for solving this problem.  The next thing I digged into was how to construct a circumscribed circle, which is really extensively covered on Wikipedia again (that always seems to pop up first). Actually the clue is far down the page, which shortly mentions Cyclic quadrilaterals.  Which is a four sides construction with all points lying on a circumscribed circle. Which is exactly what we have with the equilateral triangles ABO, BCN and ACM  joined by the point we are trying to find T.

Before taking the next sentence, I denote angle with three letters. If I am decribing the angle  of the line intesection between the line segments AO and BO I will write AOB, meaning the angle forming in the point o.

The characteristic of this cyclic quadrilateral is that opposite angles are sum to 180.  So in the case of ABOT, we know that angle AOB is 60 degress since that is part of an equilateral triangle. That means the angle ATB must be 120 degrees. And that is correct for all the angles ATC, CTB and AOB.

triangle

So now that we have the fact about one of the angles in the triangle in the picture we can express one of the sides as a function of the two others. Standard trigonometry will tell us that . Furthermore we have that cos(120) = 1/2 so that gives us

So if p, r are integers and is a perfect square, then c is integer as well.

We can set up the same relations for the other two triangles. such that we have

This means that we can start building an algorithm for finding the solution. Which goes as

  1. Find all integer pairs x,y such that and is square.
  2. For each pair (a,b) in the list search the list to find pairs (a,c) and (b,c)
  3. if a triple (a,b,c) is found and then mark that length as a solution
  4. Sum up all solutions to get the answer

Step number 1

Brute force checking all combinations for possible pairs would take something like operations, where n is the limit, which in our case is 120.000. So that is quite a big number.

Once again I am no where clever enough to have done this on my own, but using the theory from Pythagorean triples I thought there might be away to generate this kind of triangle as well. A little investigations turns up this website, which gives us what we need in order to generate triples that fulfill what we are looking for. After I solved the problem, I realize there are more explanations to why this can be decomposed, but I will leave that for you to discover.

For any coprime integers u and v where and we get a primitive triplet for our sides p,r and c from the figure can be written as

Then we can generate other triplets by multiplying this triplet with an integer k. We need to store the two first in order to find our solution. The third one is not used for anything in our case. Since we only have to search for u values less than the square root of the limit, which means that our search is limited to u < 347.

We can write the code as

int limit = 120000;
int limitSQ = 347;

List<Tuple<int, int>> pairs = new List<Tuple<int, int>>();

for (int u = 1; u < limitSQ; u++) {
    for (int v = 1; v < u; v++) {
        if (GCD(u, v) != 1) continue;
        if ((u - v) % 3 == 0) continue;

        int a = 2 * u * v + v * v;
        int b = u * u - v * v;

        if (a + b > limit) break;
        for (int k = 1; k * (a + b) < limit; k++) {
            pairs.Add(new Tuple<int,int>(k*a, k*b));
            pairs.Add(new Tuple<int,int>(k*b, k*a));
        }
    }
}

Step number 2 and 3

In order to make step 2 efficient we will sort the triples we have found, such that the first value in the pair is sorted in ascending order. Then we will make an index of where the different values of the first value is first found in the sorted list. Since that means we can efficiently search for corresponding pairs.

Once we have created the index, we will loop through all candidate pair (a,b) and find all candidates for (a, c) and (b,d) and then check if there are any matches where c=d. In that case we have found a set of pairs that fulfill the integer criteria. The only thing left is to check if the sum a+b+c is smaller than the limit.

When we have found a set that fulfills the requirements we mark that value as found. The reason we don’t just count the hit, is that I don’t know if there will be duplicates. In fact after solving it, I have checked and there are duplicates.

This takes quite a bit of code, and looks like

pairs.Sort();

// Create index
int[] index = Enumerable.Repeat(-1, limit).ToArray();

for(int i=0; i< pairs.Count; i++){
    if(index[pairs[i].Item1] == -1)
        index[pairs[i].Item1] = i;
}

bool[] sums = new bool[limit];

for (int i = 0; i < pairs.Count; i++) {
    int a = pairs[i].Item1;
    int b = pairs[i].Item2;

    List va = new List();
    List vb = new List();

    for (int j = index[a]; j < pairs.Count ; j++) {
        Tuple<int, int> next = pairs[j];
        if (next.Item1 != a) break;
        va.Add(next.Item2);
    }

    for (int j = index[b]; j < pairs.Count; j++) {
        Tuple<int, int> next = pairs[j];
        if (next.Item1 != b) break;
        vb.Add(next.Item2);
    }

    for (int ja = 0; ja < va.Count; ja++) {
        if (vb.IndexOf(va[ja]) != -1 && a + b + va[ja] < limit) {
            sums[a + b + va[ja]] = true;
        }
    }
}

Wrapping up

Once we have found all solutions all we need to do is to sum it up, which I consider a trivial task, which you can see along with the rest of the source code here.

Running the solution on my machine takes around 1300ms, so it is certainly one of the longer running solutions I have produced. I have checked that the sorting is the thing taking the majority of the time. In my case around 900ms. It is quite possible that it can be done faster by using another list type or making a sorting function myself. I haven’t really explored that part. Getting this far was accomplishment enough for me.

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

  1. Jean-Marie Hachey says:

    Table 1
    Parameters of the first three smallest Fermat-Torricelli triangles.
    [Re: Project Euler 143: Investigating the Torricelli point of a triangle]

    http://img820.imageshack.us/img820/2743/pe143tabl1fig1.jpg

    In Table 1, recurrence can be seen for variables between series 1 and 2.
    Variables of series 3 are double of those of series 1.

    ___

    Sources:

    1) Project Euler 143
    Kristian’s algorithm
    http://www.mathblog.dk/files/euler/Problem143.cs
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)
    4) Ultimate Triangle Calculator
    http://www.1728.org/trig4.htm
    5) Triangles: The Fermat-Torricelli Point
    http://mste.illinois.edu/courses/ci336sp04/folders/ckoeppen/5dayunit/home.html
    6) Fermat points and parameterizing the 120 degree integer triangle (Project Euler 143)
    http://luckytoilet.wordpress.com/2010/08/25/fermat-points-and-parameterizing-the-120-degree-integer-triangle-project-euler-143/
    7) Problem 0143
    https://sites.google.com/site/robertharamoto/Home/programming/project-euler-solutions/problems-0101-to-0200/problems-0141—0150/problem-0143

  2. Jean-Marie Hachey says:

    After some unsuccessful trials to open this link : (too much traffic ?)

    http://img820.imageshack.us/img820/2743/pe143tabl1fig1.jpg

    Here is another link to Table 1.

    ___

    Table 1

    Parameters of the first three smallest Fermat-Torricelli triangles.
    [Re: Project Euler 143: Investigating the Torricelli point of a triangle]

    http://img4.hostingpics.net/pics/485555pe143ihtableonefig1.jpg

    In Table 1, recurrence can be seen for variables between series 1 and 2.
    Variables of series 3 are double of those of series 1.

  3. Rob says:

    There is a typo in line 23 of the second code part:
    va.Add(next.Item2);
    It should be va.Add(next.Item1);!?

  4. Antonio Sanchez says:

    The key to speeding this up is to reduce redundant checks. Since you need all of (p,q), (p,r) and (q,r) to appear in your list of pairs, you can safely assume that . This means that you don’t have to add both tuples (ka,kb) and (kb,ka) to your list of pairs, instead just add the one that is in increasing order. That reduces the size of “pairs” by a factor of two.

    Rather than determining indices, I just sort and do a binary search on the list. First sort the set of pairs by increasing first value then second value. Then:
    for every pair (p,q):
    — for each pair (q,r) where
    —– check if (p,r) is also a valid pair

    The starting point for the second loop can be found with a binary search, and the final check of (p,r) can be done with a binary search. In c++, this approach takes 190ms.

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.