Let *T*(*N*) be the number of distinct (non-congruent) triangles with integer sides and perimeter *N*. For example, *T*(12) = 3 because there are three distinct triangles with integer sides and perimeter 12. There’s the equilateral triangle with sides 4 : 4 : 4, and the Pythagorean triangle 3 : 4 : 5. With a little more work we can find 2 : 5 : 5.

The authors in [1] developed an algorithm for finding *T*(*N*). The following Python code is a direct implementation of that algorithm.

def T(N :int): if N < 3: return 0 base_cases = {4:0, 6:1, 8:1, 10:2, 12:3, 14:4} if N in base_cases: return base_cases[N] if N % 2 == 0: R = N % 12 if R < 4: R += 12 return (N**2 - R**2)//48 + T(R) if N % 2 == 1: return T(N+3)

If you’re running a version of Python that doesn’t support type hinting, just delete the `:int`

in the function signature.

Since this is a recursive algorithm, we should convince ourselves that it terminates. In the branch for even `N`

, the number *R* is an even number between 4 and 14 inclusive, and so it’s in the `base_cases`

dictionary.

In the odd branch, we recurse on `N+3`

, which is a little unusual since typically recursive functions decrease their argument. But since `N`

is odd, `N+3`

is even, and we’ve already shown that the even branch terminates.

The code `(N**2 - R**2)//48`

raises a couple questions. Is the numerator divisible by 48? And if so, why specify integer division (`//`

) rather than simply division (`/`

)?

First, the numerator is indeed divisible by 48. *N* is congruent to *R* mod 12 by construction, and so *N* – *M* is divisible by 12. Furthermore,

*N*² – *R*² = (*N* − *R*)(*N* + *R*).

The first term on the right is divisible by 12, so if the second term is divisible by 4, the product is divisible by 48. Since *N* and *R* are congruent mod 12, *N +* *R* is congruent to 2*R* mod 12, and since *R* is even, 2*R* is a multiple of 4 mod 12. That makes it a multiple of 4 since 12 is a multiple of 4.

So if (*N*² – *R*²)/48 is an integer, why did I write Python code that implies that I’m taking the integer *part* of the result? Because otherwise the code would sometimes return a floating point value. For example, `T(13)`

would return 5.0 rather than 5.

Here’s a plot of *T*(*N*).

[1] J. H. Jordan, Ray Walch and R. J. Wisner. Triangles with Integer Sides. The American Mathematical Monthly, Vol. 86, No. 8 (Oct., 1979), pp. 686-689

No need to recurse!

def T(n):

m = n if n % 2 == 0 else n+3

return round(m*m / 48)