Project Euler 299: Three similar triangles

July 29, 2010

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 A, B, C, D are represented on a coordinate plane as (a,0), (b,0), (0,c), and (0,d) respectively, all of which have integer coordinates.

P is a point on AC with integer coordinates such that triangles DCP, DBP, and PAB are similar.

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

For b+d < 100,000,000, how many triples (a,b,d) exist such that point P 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 a=c. Why is this? Suppose that a \neq c. Then \angle OAC \neq \angle OCA. Next, \angle DCP \neq \angle PAB. It is obvious that triangles DCP and PAB cannot be similar if \angle DCP \neq \angle PAB.

Since \angle COA is a right angle and \triangle COA is isosceles, it follows that \angle OCA = \angle OAC = 45^\circ. So \angle DCP = \angle PAB = 135^\circ and also \angle DPB = 135^\circ.

Working backwards, we know that triangles DCP, DPB, and PAB are all similar, Then \angle CDP = \angle PDB and \angle DBP = \angle PBA; lines DP and PB are angular bisectors of \triangle DOB, thus P is the incenter of \triangle DOB.

So the distance from P to the three sides OB, OD, and DB are equal. This also means P can be represented as (i,i) since its x and y coordinates are equal.

We should note at this point that there is an additional case, where \angle CDP = \angle DBP and \angle ABP = \angle BDP. Then \angle DPC = \angle BDP, so lines AC and BD are parallel. However, in this case P 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, a is uniquely determined by b and d. For any pair (b,d), there is only one possible AC passing through the incenter.

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

Line BD can be expressed by the equation

y = -\frac{d}{b}x + d ,

or in standard form,

dx + by - bd = 0 .

Recall the distance from point to line formula giving the distance between a point (m,n) to line Ax + By + C = 0:

d = \frac{|Am+Bn+C|}{\sqrt{A^2 + B^2}} .

By substitution, we have

i = \frac{|di+bi-bd|}{\sqrt{b^2 + d^2}} .

Simplifying:

i^2 (b^2 + d^2) = (di+bi-bd)^2 .

It is necessary and sufficient for b^2+d^2 to be a perfect square, as then i will be uniquely determined and will be an integer.

Thus the incenter case reduces to finding all pairs (b,d) for b+d < 100,000,000 where b^2 + d^2 is a perfect square.

Parallel case

Now we consider the case when AC || BD.

Let X be the circumcenter of \triangle DPB:

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

Let T be a point (not shown) such that DPBC is cyclic. Then \angle DTB = 45^\circ because \angle DPB = 135^\circ, therefore \angle DXB = 90^\circ.

As a consequence of the parallelism of AC and BD, b and d must be equal. Since \angle X is a right angle, it follows that the coordinates of X is (b,b), and that DOBX is a square.

The circle around X is centered at (b,b) and has a radius of b, thus its equation is

(x-b)^2 + (y-b)^2 = b^2 .

The line AC has an equation of

y=c-x .

By substitution into the circle equation:

(x-b)^2 + (c-x-b)^2 = b^2 ,

Or,

2x^2 + (-2c)x + (b^2+c^2-2bc)=0 ;

Applying the quadratic formula and dividing by 2 gives

x = \frac{c \pm \sqrt{c^2 - 2(b-c)^2}}{2} .

Here it is sufficient for c^2 - 2(b-c)^2 to be a perfect square, as then x will be an integer.

We prove this by using a parity argument: if c is odd, then c^2 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 c, makes an even number. A similar argument applies if c is even.

We can substitute f for b-c giving the perfect square

c^2 - 2f^2.

If we let q^2 be the perfect square, we get

q^2 + 2f^2 = c^2.

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

2(c+f) < 100,000,000.

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 x, y, z):

x^2 + y^2 = z^2 ,

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

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

x = n^2 - m^2

y = 2mn

z = n^2 + m^2

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 (3,4,5). To count the number of similar triples with x+y < 100000, sum the x and y values of the triple, which is in this case 7. Then divide the limit by 7, which in this case is \frac{100,000}{7}, so we have 14285 such triangles.

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

x^2 + 2y^2 = z^2 ,

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

x = n^2 - 2m^2

y = 2mn

z = n^2 + 2m^2

This case is slightly different from the previous case, in the sense that we no longer require x to be positive, so we do not need the restriction that m<n. Additionally, we need to divide by y+z, instead of x+y 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.


On some number-theoretic properties of right triangles (Project Euler 218)

June 20, 2010

The two hundred and eighteenth problem of Project Euler is quite interesting, but different. It resembles more closely a mathematics olympiad problem than a programming challenge. Its answer is somewhat surprising, too.

Original problem

The problem can be stated as follows:

A right triangle is considered perfect if (1): it is primitive (GCD of the three sides is 1) and (2): its hypotenuse is a perfect square.

A perfect triangle is considered superperfect if its area is divisible by the perfect numbers 6 and 28.

How many perfect triangles are there with hypotenuse below 10^{16} that are not also superperfect?

Answer

It turns out that every perfect triangle is also superperfect, meaning that for any limit there are no perfect triangles that are not superperfect.

Looking on the forums, it seems that a large group of solvers counted the triangles for a smaller limit, like 10^{9} or 10^{12} , and getting 0, assumed the answer applied for 10^{16} .

In this article I will attempt to prove, mathematically, that it is indeed impossible for a perfect triangle not to be superperfect.

Proof

Let’s rephrase this problem a bit: Prove that if a primitive right triangle has a hypotenuse that is a perfect square then its area must be a multiple of 6 and 28.

If the area is a multiple of 6 and 28, then it is a multiple of \mathrm{LCM}(6,28) = 84 . If we let p, q, and c be the sides of the right triangle (with c as the hypotenuse), then the area is \frac{pq}{2} .

Since 84 | \frac{pq}{2} , it follows that 168 | pq . As c is a perfect square, we write c as r^2 and since \mathrm{GCD}(p,q,c)=1 , it also follows that \mathrm{GCD}(p,q,r)=1 . This is what we shall now prove.

Lemma 1

For positive integers p, q, r where p^2 + q^2 = r^4 and \mathrm{GCD}(p,q,r)=1 , then 168|pq .

From the Euclid theorem of Pythagorean triples, the sides of a primitive right triangle with sides a, b, and c can be represented as:

a = u^2 - v^2

b = 2uv

c = u^2 + v^2

.. where u>v and u and v are of opposite parity.

Thus by applying the theorem to our triple:

p = u^2 - v^2

q = 2uv

r^2 = u^2 + v^2

Notice here that the third equation here itself represents a pythagorean triple. We then apply the same formula again, this time using m and n for the integers:

u = m^2 - n^2

v = 2mn

r = m^2 + n^2

Substituting for p, q, r:

\begin{array}{rcl} p &=& u^2 - v^2 \\ &=& (m^2-n^2) - (2mn)^2 \\ &=& m^4 - 2m^2n^2 + n^4 - 4m^2n^2 \\&=& m^4 + n^4 - 6m^2 n^2 \\ \\ q &=& 2uv \\ &=& 2(m^2-n^2)(2mn) \\ &=& 4mn(m^2-n^2) \\ \\ r &=& m^2 + n^2 \end{array}

Then,

pq = 4mn(m^2-n^2)(m^4+n^4-6m^2n^2)

.. which we will prove to be divisible by 168. Since 168=8*3*7, the expression must be proved to be divisible by 8, by 3, and by 7.

Lemma 2

8 | 4mn(m^2-n^2)(m^4+n^4-6m^2n^2)

Proof of Lemma 2

The proof is almost trivial. In order for the triple to primitive, m and n must be of opposite parity, meaning mn is even.

Because 2|mn and 4 is already a factor of the expression, it follows that 8|pq .

Lemma 3

3 | mn(m^2-n^2)

Proof of Lemma 3

Rewrite the expression as

mn(m+n)(m-n) .

If 3|m or 3|n , then 3|mn .

If m \equiv n \mod 3 , then m-n \equiv 0 \mod 3 .

The only other scenario is when m \not \equiv n \mod 3 , then either m \equiv 1 \mod 3 and n \equiv 2 \mod 3 or vice versa. Either way, m+n \equiv 0 \mod 3 .

Lemma 4

If 7 \nmid m , then m^2 \equiv 1,2,4 \mod 7 .

Proof of Lemma 4

We construct a table. The first column of this table is m \mod 7 while the second column is m^2 \mod 7:

1 1
2 4
3 2
4 2
5 4
6 1

The only possible values are 1, 2, and 4.

Lemma 5

If 7 \nmid m^2 - n^2 , then either m^2 \equiv 2n^2 \mod 7 or n^2 \equiv 2m^2 \mod 7 .

Proof of Lemma 5

Because 7 \nmid m^2 - n^2 , m^2 \not\equiv n^2 \mod 7 . Then, not counting reflective cases, there are three cases we need to consider:

Case 1: m^2 \equiv 1, n^2 \equiv 2 . Then n^2 \equiv 2m^2 \mod 7 .

Case 2: m^2 \equiv 1, n^2 \equiv 4 . Then m^2 \equiv 2n^2 \mod 7 .

Case 3: m^2 \equiv 2, n^2 \equiv 4 . Then n^2 \equiv 2m^2 \mod 7 .

One of these (or their reflection) apply for whatever value of m and n.

Lemma 6

7 | m^4 + n^4 - 6m^2n^2

Proof of Lemma 6

Without loss of generality, rewrite the expression as a congruence mod 7, in terms of m. Since m^2 \equiv 2n^2 \mod 7,

\begin{array}{rcl} m^4 + n^4 - 6m^2n^2 &=& m^4 + (2m^2)^2 - 6m^2(2m^2) \\ &=& m^4 + 4m^4 - 12m^4 \\ &=& -7m^4 \end{array}

The result follows.

Q.E.D.


Follow

Get every new post delivered to your Inbox.

Join 71 other followers