Project Euler #9: Special Pythagorean triplet Discussions |

3 months ago+ 1 comment

We know that c = n - a - b

But also we know that a^2 + b^2 = c^2

So after substutions we can calculate relation between a and b given that n=const.

So we can substitute everything into a*b*c and get some complicated function. After some more math magic on paper I've came up with neat solution. It's guaranteed that the first solution is already the best one.

def bound(n):
    return int(n*(1-math.sqrt(2)/2))

def calc_b(n, a):
    return n*(2*a-n)/(2*a-2*n)

def pit(n):
    for a in range(bound(n), 0, -1):
        if (f_b := calc_b(n, a)) == (b := int(f_b)):
            return a*b*(n-a-b)
    return -1

3 months ago+ 0 comments

I'm not gonna explain a long math magic behind this, but here is much faster version, that can give correct anstwer for every 8-digit n under 7s

` def bound(n): return int(n*(1-math.sqrt(2)/2))

def calc_b(nn, n, a): if nn % (n-a) == 0: return (nn-a*n)//(n-a)

def pit(n): if n % 2 == 1: return -1

nn = n*(n >> 1)  # nn = (n^2)/2
for a in range(bound(n), 0, -1):
    if b := calc_b(nn, n, a):
        return a*b*(n-a-b)
return -1

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge