Project Euler Problem 142 - Solved

Solution to ProjectEuler's problem 142 in Python by expression manipulation and brute-force.

The statement of the problem can be found here.

In order to solve this problem, first, we have to express the different equations and then start working with them.

Let's begin expressing the equations:

\[ x + y = A \\ x - y = B \\ x + z = C \\ x - z = D \\ y + z = E \\ y - z = F \]

Now let's begin working with them, we can express:

\[ x - z = (x + y) - (y + z) \Rightarrow D = A - E \\ x + z = (x + y) - (y - z) \Rightarrow C = A - F \\ x - y = (x + z) - (y + z) \Rightarrow B = C - E \]

So, bruteforcing only the values we can obtain possible solutions, but in order to get the values of x, y z we need to solve the linear equation:

\[ x - z = D \\ x + z = C \\ x - y = B \]

From this solution we can see that \( D+C \) must be even, so D and C must have the same parity, thus E and F must have the same parity.

With all this in mind we can easily write an algorithm in Python to solve the problem (problem142.py):

from itertools import count, takewhile

is_square = lambda x: int(x ** 0.5) ** 2 == x

if __name__ == '__main__':
    for a in count(6):
        a_2 = a ** 2
        for f in (f for f in takewhile(lambda f: f < a, count(4)) if is_square(a_2 - f ** 2)):
            f_2 = f ** 2
            c_2 = a_2 - f_2
            setoff = 3 if (f & 1) else 2
            for e in (e for e in takewhile(lambda e: e ** 2 < c_2, count(setoff, 2)) if is_square(c_2 - e ** 2) and is_square(a_2 - e ** 2)):
                e_2 = e ** 2
                b_2 = c_2 - e_2
                d_2 = a_2 - e_2
                z = -(d_2 - c_2) // 2
                y = -(-d_2 - c_2 + 2 * b_2) // 2
                x = (d_2 + c_2) // 2
                print('The result is: (x){0} + (y){1} + (z){2} = {3}'.format(x, y, z, x + y + z))
                exit(0)

Comments powered by Talkyard.