## April 2009 solution

Consider the following: there is a one-to-one correspondence between integer-sided right-angle triangles with side lengths {a,b,c} and triplets of naturals (k,x,y) with x and y odd and co-prime and y>x, which can be described explicitly by the mapping

a=k(y2-x2)/2
b=kxy
c=k(y2+x2)/2

To demonstrate this, let us show that we can calculate k, x and y uniquely from a, b and c in such a way that they meet the requirements of them.

First, the gcd of a, b and c is simply k. Proof: If it is not, then there must be a prime, p that divides both xy and y2+x2. Because x and y are co-prime, p must divide exactly one of the two. Let us suppose w.l.o.g that it divides x. Then, it divides x2 but not y2, so also not their sum. A contradiction.

Let us therefore divide everything by k and work with {a,b,c} that have a gcd of 1. Consider these values modulo 4 and let c be the hypotenuse length. An even number squared is 0 (mod 4). An odd number squared is 1 (mod 4). It cannot be that both a and b are even, for this would mean that c is also even, and therefore their gcd would not have been 1. However, a and b cannot both be odd, either, for then c2 would be 2 (mod 4), which is impossible. This means that exactly one of a and b is even. This defines a specific order over the triplet (and therefore eliminates ambiguity): c is the largest, and of the remaining two a is chosen to be the even one and b the odd one.

Consider now that b2 = c2-a2 = (c+a)(c-a). b2 is therefore to be represented as the multiplication of two factors, m=c+a and n=c-a (Note: m>n). As b is odd, so must m and n be. Furthermore, consider that a=(m-n)/2 and c=(m+n)/2. If m and n had any common odd factors, these common factors would have also been factors of a, b and c, so the gcd of the sides of the triangle would not have been 1, contrary to the assumption. This means that m and n must be co-prime. As the product of m and n is a perfect square, these two co-prime factors must be squares themselves. We denote m=y2 and n=x2. This solves y and x uniquely as the odd, co-prime values sqrt((c+a)/k) and sqrt((c-a)/k), respectively, proving the correspondence.

Now, let us rephrase the question in terms of (k,x,y) triplets. The perimeter, in these variables, is ky(x+y). Let us define z=x+y. Note that due to the conditions on x, z is constrained to be even, co-prime with y and in the range y<z<2y.

We want to find the number of triplets where kyz=10n. This is equivalent to finding the number of (y,z) pairs where yz is a divisor of 10n.

Because y is odd, it cannot have a factor of 2, therefore it must be a power of 5. Because y<z<2y, we know that y>1, so y divides by 5. z must be co-prime with y, so z cannot divide by 5, so it is a power of 2.

Note that even though any positive power of 5 can be used as y, each choice defines a legal range of z values wherein exactly one value is a power of two. This means that the total number of triangles equals the total number of positive powers of five that yield yz≤10n.

If y=5v and z=2w, it is clear that v<w for z to be within its legal range. This indicates that the limiting factor in determining the largest possible yz is wn.

Putting everything together, we get 51y=5v < z=2w ≤ 2n. This indicates that v is in the range 1≤v<log5 2n. The total number of such values for v is floor(log52n)=floor(log52 n), which is the final answer.

This riddle was inspired by one of the problems on the Project Euler website. Thanks, Project Euler!