Being the last Project Euler problem before the summer break, Problem 299 is quite an interesting problem. Solving it involves both geometry and number theory.

Points , , , are represented on a coordinate plane as , , , and respectively, all of which have integer coordinates.

is a point on with integer coordinates such that triangles , , and are similar.

It can be shown that in order for the triangles to be similar, .

For , how many triples exist such that point exists?

### Initial observations

Before we can start coding, there is some geometry work to be done.

It is given that it must be necessary for . Why is this? Suppose that . Then . Next, . It is obvious that triangles and cannot be similar if .

Since is a right angle and is isosceles, it follows that . So and also .

Working backwards, we know that triangles , , and are all similar, Then and ; lines and are angular bisectors of , thus is the **incenter **of .

So the distance from to the three sides , , and are equal. This also means can be represented as since its and coordinates are equal.

We should note at this point that there is an additional case, where and . Then , so lines and are parallel. However, in this case is no longer the incenter.

We shall consider the two as separate cases, and refer to them as the incenter and parallel case respectively.

### Incenter case

We first consider the incenter case. Note that in this case, is uniquely determined by and . For any pair , there is only one possible passing through the incenter.

We need to find pairs of such that there exists a point where the distance from the point to is (and that is integral).

Line can be expressed by the equation

,

or in standard form,

.

Recall the distance from point to line formula giving the distance between a point to line :

.

By substitution, we have

.

Simplifying:

.

It is necessary and sufficient for to be a perfect square, as then will be uniquely determined and will be an integer.

Thus the incenter case reduces to finding all pairs for where is a perfect square.

### Parallel case

Now we consider the case when .

Let be the circumcenter of :

Notice that here there are actually two possible places for . We can ignore this fact for now.

Let be a point (not shown) such that is cyclic. Then because , therefore .

As a consequence of the parallelism of and , and must be equal. Since is a right angle, it follows that the coordinates of is , and that is a square.

The circle around is centered at and has a radius of , thus its equation is

.

The line has an equation of

.

By substitution into the circle equation:

,

Or,

;

Applying the quadratic formula and dividing by 2 gives

.

Here it is sufficient for to be a perfect square, as then will be an integer.

We prove this by using a parity argument: if is odd, then is odd as well, and the expression inside the radical is odd; Supposing that it is a perfect square, the square root of that is odd, and when added to , makes an even number. A similar argument applies if is even.

We can substitute for giving the perfect square

.

If we let be the perfect square, we get

.

Essentially the problem reduces down to finding integral solutions to the above equation, with the limit set to

.

### Writing the code

We are now ready to write a program to enumerate integer pairs to satisfy our equations.

We will start with the incenter case, which is somewhat more basic and easier to deal with.

Recall that we have derived this equation (replacing the variables with , , ):

,

with the limit being on the sum of . Obviously, this is a pythagorean triple. Enumerating pythagorean triples can be done very efficiently.

If and are coprime integers with an odd sum, and with , then the primitive pythagorean triples can be parameterized by the formulas:

Just by using this formula and little else, primitive pythagorean triples triples can be enumerated very quickly.

It is not very difficult to enumerate the non-primitive triples, either. Suppose we have generated the triple . To count the number of similar triples with , sum the and values of the triple, which is in this case 7. Then divide the limit by 7, which in this case is , so we have 14285 such triangles.

A nearly identical approach can be used to enumerate pairs for the parallel case. Here we have

,

which is nearly identical to the previous equation and can be parameterized as:

This case is slightly different from the previous case, in the sense that we no longer require to be positive, so we do not need the restriction that . Additionally, we need to divide by , instead of as we did before.

This is easy to implement in Java:

public class Main{ final static long L = 100000000; static long gcd(long m, long n) { if (m < n) { long t = m; m = n; n = t; } long r = m % n; if (r == 0) return n; else return gcd(n, r); } static long incenterCase(){ long count = 0; for(long n = 1; n < L/2; n++) for(long m = 1; m < n; m++){ if((m+n) % 2 == 0) continue; if(gcd(m,n)!=1) continue; long b = n*n - m*m; long d = 2*n*m; long sum = b+d; if(sum >= L) break; if(b == d) count += L/sum; else count += 2*(L/sum); } return count; } static long parallelCase(){ long count = 0; for(long n = 1; n < L; n+=2) for(long m = 1; m < L; m++){ if(gcd(m,n)!=1) continue; long g = 2*n*m; long a = n*n + 2*m*m; long b = g+a; if(b > L/2) break; count += (L-1)/(2*b); } return count; } public static void main(String[] args) { System.out.println(incenterCase() + parallelCase()); } }

This code generates the correct answer in about 25 seconds on my machine.

It confused me when you wrote in incenter()

count += 2*(L/sum);

and you wrote in parallel()

count += (L-1)/(2*b);

I realize that L versus L-1 doesn’t make a difference in the incenter case, but it would have been clearer at least for me to write

count += 2*(L-1)/sum

LikeLike