It can be shown that every right angle triangle with integer sides has at least one side of even length. There
are no right angled isosceles triangles with integer side lengths, since the square root of 2 is irrational.
Consider the right angled triangle with sides 3, 4, 5. This is almost isosceles. Let us call a right angled
triangle with side lengths x, x + 1, y an Almost Isosceles Right Angled triangle – AIRA for short. Such
triangles are also called Nearly Isosceles Right Angled triangles. The first two triangles can be computed
easily:
(3, 4, 5), (20, 21, 29)
The hypotenuse an of these triangles maybe computed by the recurrence relation
a0=1,b0=2
an=an1+
2bn1,
bn=2an+bn1
A factor of a positive integer is a positive integer which divides it completely without leaving a remainder.
For example, for the number 12, there are 6 factors 1, 2, 3, 4, 6, 12. Every positive integer k has at least two
factors, 1 and the number k itself.
The objective of the program is to find the number of factors of the even side of the AIRA that is larger than
a given number
Input
The input is a single number N
Output
The number of factors of the even side of the smallest AIRA which has an even side greater than N
Constraints
The even side is less than 5000000
Example 1
Input
15
Output
6
Explanation
The smallest AIRA that has an even side greater than 15 is (20,21,29). The even side is 20, and its factors are
(1,2,4,5,10,20), a total of 6 factors. The output is 6
Example 2
Input
100
Output
16
8/29/2017 Almost Isosceles Right Triangles
http://r.tcscodevita.com/CodevitaReports/questions/zone2/Almost%20isosceles%20Right%20Triangles%20Murali.html 2/2
Explanation
The smallest AIRA which has the even side greater than 100 is (119,120,169). The even side is 120, and it
has (1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120). As there are 16 factors, the output is 16.