#Problem:
#How many right triangles with integer edges have given perimeter p?
#or in other words:
#How many triplets (a,b,c) are there such that:
# (*) a*a +b*b == c*c
# (*) a + b + c == p
# (*) a,b,c > 0 are all integers
#In order to avoid counting a triplet twice or more, we require that
# 0 < a < b < c
# Note that:
# (1) a != b and b != c
# (2) The condition b < c is redundant (since we require that a,b,c > 0 and a*a + b*b == c*c)
import time
# trivial solution
# and p as the input size,
# the complexity is O(p**3) (cubic complexity)
def number_of_integer_right_triangles_v1(p):
cnt = 0
for a in range(1,p):
for b in range(1,p):
for c in range(1,p):
if a < b and a+b+c == p and a*a+b*b == c*c:
cnt += 1
return cnt
# defining the content of the innermost loop as a single atomic operation
# (which takes a constant time),
# and p as the input size,
# the complexity is O(p**2) (quadratic complexity)
def number_of_integer_right_triangles_v2(p):
cnt = 0
for a in range(1,p):
for b in range(1,p):
c = p-a-b
if a < b and a*a+b*b == c*c:
cnt += 1
return cnt
# defining the upper limit of the innermost loop with the condition a < b
# (which takes a constant time),
# and p as the input size,
# the complexity is O(p**2) (quadratic complexity)
def number_of_integer_right_triangles_v3(p):
cnt = 0
for a in range(1,p):
for b in range(a+1,p):
c = p-a-b
if a*a+b*b == c*c:
cnt += 1
return cnt
# defining the limits of the loops using algebra
# and p as the input size,
# the complexity is O(p**2) (quadratic complexity)
def number_of_integer_right_triangles_v4(p):
cnt = 0
#a = p-b-c < p-2a --> 3a < p
# Thus: a < p/3, that is, the maximal possible value of a is p//3
for a in range(1,p//3 + 1): #we add 1 in order to include p//3 in the range
#b = p-a-c < p-a-b --> 2b < (p-a)
# Thus: b < (p-a)/2, that is, the maximal possible value of b is (p-a)//2
for b in range(a+1,(p-a)//2 + 1): #we add 1 in order to include (p-a)//2 in the range
c = p-a-b
if a*a+b*b == c*c:
cnt += 1
return cnt
# defining the content of the innermost loop as a single atomic operation
# (which takes a constant time),
# and p as the input size,
# the complexity is O(p)
def number_of_integer_right_triangles_v5(p):
cnt = 0
for a in range(1,p//3 + 1):
b = (p**2-2*p*a)/(2*(p-a)) #substitution of a+b+c=p in a*a+b*b=c*c
if int(b) == b and a < b: #we don't even need to calculate c here!
cnt += 1
return cnt
def elapsed(expression,number=1):
''' computes elapsed time for executing code
number of times (default is 1 time). expression should
be a string representing a Python expression. '''
t1=time.clock()
for i in range(number):
x = eval(expression)
t2=time.clock()
return t2-t1
print("v1, p = 240 took",elapsed("number_of_integer_right_triangles_v1(240)"), "secs")
print("v2, p = 240 took",elapsed("number_of_integer_right_triangles_v2(240)"), "secs")
print("v3, p = 240 took",elapsed("number_of_integer_right_triangles_v3(240)"), "secs")
print("v4, p = 240 took",elapsed("number_of_integer_right_triangles_v4(240)"), "secs")
print("v5, p = 240 took",elapsed("number_of_integer_right_triangles_v5(240)"), "secs")
print("")
print("v1, p = 480 took",elapsed("number_of_integer_right_triangles_v1(480)"), "secs")
print("v2, p = 480 took",elapsed("number_of_integer_right_triangles_v2(480)"), "secs")
print("v3, p = 480 took",elapsed("number_of_integer_right_triangles_v3(480)"), "secs")
print("v4, p = 480 took",elapsed("number_of_integer_right_triangles_v4(480)"), "secs")
print("v5, p = 480 took",elapsed("number_of_integer_right_triangles_v5(480)"), "secs")