If \(p\) is the perimeter of a right angle triangle with integral length sides, \(\{a, b, c\}\), there are exactly three solutions for \(p = 120\).
\(\{20,48,52\}\), \(\{24,45,51\}\), \(\{30,40,50\}\)
For which value of \(p \le 1000\), is the number of solutions maximised?
I talked about one way to generate Pythagorean triples in my solution to problem 9. For the sake of variety, I'm going to cover a different approach. Thanks to the works of Berggren and Barning, it's easy to construct a ternary tree of primitive Pythagorean triples. The root is \((3,4,5)\), and a triple's children are found by representing it as a vector in \(\mathbb Z^3\) and multiplying by one of the three matrices
\[ \begin{array}{lcr} A = \begin{bmatrix} 1 & -2 & 2 \\ 2 & -1 & 2 \\ 2 & -2 & 3 \end{bmatrix}, & B = \begin{bmatrix} 1 & 2 & 2 \\ 2 & 1 & 2 \\ 2 & 2 & 3 \end{bmatrix}, & C = \begin{bmatrix} -1 & 2 & 2 \\ -2 & 1 & 2 \\ -2 & 2 & 3 \end{bmatrix}. \end{array} \]This tree contains all primitive Pythagorean triples exactly once (for proofs, see the linked article).
My code keeps running tallies of how many right triangles have been discovered for each perimeter length up to 1000. For each primitive triple that's small enough, it first adds that triple's descendants which are also small enough into a queue, then notes the perimeter of each of that triple's multiples.
import queue
import numpy as np
def p39(cap=1000):
q = queue.SimpleQueue()
q.put_nowait(np.array([3,4,5]))
A = np.array([[1,-2,2],[2,-1,2],[2,-2,3]])
B = np.array([[1,2,2],[2,1,2],[2,2,3]])
C = np.array([[-1,2,2],[-2,1,2],[-2,2,3]])
perims = [0 for _ in range(cap+1)]
while not q.empty():
v = q.get_nowait()
for child in [A @ v, B @ v, C @ v]:
if sum(child) <= cap:
q.put_nowait(child)
p = sum(v)
for mult in range(p, cap+1, p):
perims[mult] += 1
return perims.index(max(perims))