Euler Solution 75

From ProgSoc Wiki

Jump to: navigation, search

Contents

Euler Problem 75

Given that L is the length of the wire, for how many values of L 1,500,000 can exactly one integer sided right angle triangle be formed?

Solutions for Euler Problem 75

This is it, solutions for the 75th problem of Project Euler

Number 75 in the set of problems posed by the Project Euler team has been solved by ProgSoc members, and some solutions to Problem 75 have been presented here below for your edification

That's 75, people! Not 74 nor 76, seventy-five!

1001011 in binary, 4B in hex, 113 in octal

'Soixante-dix-cinq', if you speak French, 'sedamdeset i pet', if you speak Croatian, 'large mob' if you were an indigenous Australian three-hundred years ago (I'm being PC :P)...

Can I make it any clearer? Solution 75!

Python by Althalus

Runtime: 22.14s

def gcd(a,b):
    while b != 0:
        tmp = a % b 
        a = b 
        b = tmp 
    return a

def get_triple():
    m,n = 1,1 
    while True:
        m += 1
        if m >= n:
            m = 1 
            n += 1
        if (gcd(m,n) == 1) and (m%2 == 0 or n%2 == 0): 
            a,b,c = (n*n)-(m*m),2*m*n,(m*m)+(n*n)
            yield a,b,c 

triples = get_triple()
ls = {}
a,b,c = triples.next()
target=1500000
for x in xrange(1500000):
    if a+b+c <= target:
        i = 1 
        a1,b1,c1 = a*i,b*i,c*i
        while a1+b1+c1 <= target:
            try:
                ls[a1+b1+c1]+=1
            except:
                ls[a1+b1+c1] = 1 
            i+=1
            a1,b1,c1 = a*i,b*i,c*i
    else:
        pass
    a,b,c = triples.next()

print sum ([x for x in ls.values() if x == 1])
Personal tools