// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 139 Solution

Project Euler 139 Solution

Project Euler 139: Find how many Pythagorean triangles allow tiling with a perimeter < 108


Project Euler 139 Problem Description

Project Euler 139: Let (a, b, c) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length c.

For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares.

Project Euler 139 Solution: Pythagorean tiles

However, if (5, 12, 13) triangles were used then the hole would measure 7 by 7 and these could not be used to tile the 13 by 13 square.

Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?

Analysis

The paper “Tiling with Pythagorean Triples” offers a journey through the rough streets of brute forcing to the tranquil avenue of Pell’s equation. The following discussion paraphrases this excellent discussion in an effort to summarize my solution.

Using Euclid’s formula, the tiling condition can be expressed as:

 2mn-m^2 + n^2 = \pm 1

We can rearrange and group the terms, and define two new variables, to transform the equation:

 \setlength\arraycolsep{2pt}\begin{array}{rl} m^2-2mn + n^2-2n^2 &= 1 \\[6pt] (m-n)^2-2n &= 1 \\[6pt] x &= m-n \\[6pt] y &= n \\[6pt] x^2-2y^2 &= 1\end{array}

Since m and n are positive integers, with m > n , it follows from the above that x and y will also be positive integers. Given that, the last version of the tiling condition fits the Pell’s equation form of Diophantine equations.

A Diophantine equation is a polynomial equation with the added constraint that only integer solutions are allowed; Pell’s equation is a specific form of Diophantine equation.

Jump over to Dario’s site and solve the Diophantine equation as:

  \setlength\arraycolsep{2pt}\begin{array}{rl} x_0 &= 1 \\[6pt] y_0 &= 1 \\[6pt] X_{n+1} &= 3x_n + 4y_n \\[6pt] Y_{n+1} &= 2x_n + 3y_n\end{array}

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank


Project Euler 139 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 139 Solution Python 2.7 source.

Afterthoughts

    No afterthoughts yet.
Project Euler 139 Solution last updated

Discussion

No comments yet.

Post a comment