Project Euler Problem #91

Problem #91 concerns right triangles whose vertices lie on lattice points. The question reads:

My solution for this problem involves a bit of brute force. Here’s my solution:

Solution #1: Brute Force Casework Approach

We have several cases to consider. The first is if the right angle is either at the origin or on one of the axes. If the right angle is at the origin, there are clearly n*n triangles where x,y <= n. If the right angle is on the x-axis, there are also n*n triangles, as there are n choices for the location of the right angle, and n choices for the y-coordinate of the 3rd vertex. By symmetry, there are also n*n triangles with a right angle on the y-axis.

The next case is that the hypotenuse is on one of the axes. Note that if the hypotenuse has length c, then the number of right triangles with that hypotenuse on one of the two axes is double the number of values l such that l*(c-l) is a perfect square, because it can be shown by similar triangles that the altitude to the hypotenuse would be the square root of l*(c-l). By checking values of l up to c/2, we can add 4 for each value of l. If c is even, then there are an additional 2 isosceles right triangles.

The final case is when none of the sides of the triangle lies on one of the axes. In this case, it suffices to investigate each vector <a,c> with a,c <= n and then to count vectors <b,d> with a*b+c*d = 0 such that <a+b,c+d> lies in the square. The fact that two vectors are orthogonal if and only if their dot product is 0 is very useful here. After this, we are done. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #91
 '''
 
 import time
 
 def projectEulerProblemNinetyOne(n):
     total = 3*n*n
     squares = []
     for h in range(n+1):
         squares.append(h*h)
     for c in range(1,n+1):
         for l in range(1,(c+1)/2):
             if l*(c-l) in squares:
                 total+=4
         if(c%2==0):
             total+=2
     for a in range(1,n+1):
         firstTerm = 0
         for c in range(a+1,n+1):
             firstTerm += a
             for b in range(1,n+1):
                 secondTerm = squares[b]
                 if((secondTerm-firstTerm)%b==0):
                     d = (secondTerm-firstTerm)/b
                     if 1<=d<=n:
                         total+=2
     return total
 
 start = time.time()
 print projectEulerProblemNinetyOne(50)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 14234
 --- 0.00694298744202 seconds ---
 
 for input of n = 50.
 ''' 

And with that, we’re done. The trickiest optimization I used was using the fact that two vectors are perpendicular iff their dot product is 0. Other than that, this was a pure brute force solution. It ran in under 7 ms, so I am probably satisfied with this solution for now.

Thanks for reading! See you tomorrow.