#Problem:
#How many right triangles with integer edges have given perimeter p?

#note: in all solutions the condition b<c is redundant:
#the conditions a*a+b*b == c*c and a>=1 cover it


import time

#cubic complexity in p - O(p^3)
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 < c and a+b+c == p and a*a+b*b == c*c:
                    cnt += 1
    return cnt

#quadratic complexity in p - O(p^2)
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 < c  and a*a+b*b == c*c:
                cnt += 1
    return cnt

#quadratic complexity in p - O(p^2)
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 b < c  and a*a+b*b == c*c:
                cnt += 1
    return cnt


#quadratic complexity in p - O(p^2)
def number_of_integer_right_triangles_v4(p):
    cnt = 0
    for a in range(1,p//3+1): #a = p-b-c <= p-2a --> 3a<p
        for b in range(a+1,(p-a)//2+1): #b = p-a-c < p-a-b --> 2b<p-a
            c = p-a-b
            if a*a+b*b == c*c: 
                cnt += 1
    return cnt


#fastest - linear complexity in p - 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):
        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")