# Euler Solution 91

### From ProgSoc Wiki

Revision as of 06:34, 16 April 2010 by Tomchristmas (Talk | contribs)

# Solutions for Problem 91

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is, 0 ≤ x1, y1, x2, y2 ≤ 2.

Given that 0 ≤ x1, y1, x2, y2 ≤ 50, how many right triangles can be formed?

## Python by Althalus

Runtime: 18ms

Oh gods. I have drawn so many grids and triangles in the past day trying to find these patterns that I never want to see another triangle again.

*Methinks you are slowly turning into Maximillian Cohen from Pi... - tom (16/4/2010)*.

from time import time start = time() from fractions import gcd # How nice. Python 2.6 provides a GCD implementation for me! max=50 # right angle in bottom left or bottom right, and the first inverted. # (0,0), (0,y), (x,0) (0,0),(x,0),(x,y) (0,0),(0,y),(x,y) count = max*max*3 # triangles where long side flush with vertical/horizontal, and triangles that can be formed therein. c2=0 for i in range(1,max): for j in range(1,i+1): if i+j > max: break c2 += 2 count += c2 c2 = 0 # triangles not flush with a vertical/horizontal for i in range(1,max+1,1): for j in range(i+1,max+1): # We can take advantage of the fact that x.y is equivelant to y.x to halve the number of loops if i == j: continue # covered above. c3 = 0 d = gcd(i,j) i1 = i/d j1 = j/d x,y = i+j1, j-i1 while x <= max and y >= 0: c3 += 2 x += j1 y -= i1 x,y = i-j1, j+i1 while x >= 0 and y <= max: c3 += 2 # See comment above. x -= j1 y += i1 c2 += c3 count += c2 print count print time()-start