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