We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
A cathetus of say 12 appears either in basic triplet(5-12-13) form or in expanded triplet form(4*(3-4-5)). Theory says you always have an even-odd tuple for basic catheti and there is a formula for creating only those basic triplets with using a pair of odd coprime numbers.
We have 12 so it may be the even cathetus of a basic triplet, go try it.
12 may be an integer multiple of an expanded triplet. So factor out 12 and take a number at a time to repeat the step-2. Even and odd numbers go into different processes, be careful.
Factors of 12 are 1,2,3,4,6,12. In the example, 2/4 of the cases was obtained using 12 itself: (5-12-13),(12,35,37). One of them is from 4: (9-12-15). The last one is from 3: (12-16-20). Note that there are no basic triplets including 1,2 or 6.(1-0-1) is not acceptable of course.
So the total number of triplets containing 12 can be calculated as the total number of basic triplets that can be obtained from all of 12's factors included.
I think we should first find an efficient factoring algorithm and then another one for basic triplet generator.
Lastly, when I look at the formulas, I can come up with a final procedure in my head,
a. Take the number N. If it is odd, count how many coprime factor pairs it has.
Else if it is even, divide by two. If the result is odd, discard the number. If the result is even, count how many coprime factor pairs the result has.
b. Take a factor of N, repeat the "step a" with this number.
c. Repeat for all factors and count all them up.
Some examples:
12 --> even --> 12/2 = 6 --> even --> 6 = 2*3 or 1*6. (2)
6 --> even --> 6/2 = 3 --> odd --> discard it. (0)
4 --> even --> 4/2 = 2 --> even --> 2 = 1*2 (1)
3 --> odd --> 3 = 1*3 (1)
2 --> even --> 2/2 = 1 --> odd --> discard it. (0)
Total = 4
Similarly, for 15,
15 = 3*5 or 1*15
5 = 1*5
3 = 1*3
total = 4
for 60,
60 = 2^2*3*5 --> 2*3*5 (4 comb.)
30 = 2*3*5 discard
20 = 2^2*5 --> 2*5 (2 comb.)
15 = 3*5 (2 comb.)
12 = 2^2*3 (4 comb. already solved)
10 = 2*5 discard
6 = 2*3 discard
4 = 2^2 (1 comb.)
3 = 3 (1 comb.)
2 = 2 discard
Total = 14
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #176: Rectangular triangles that share a cathetus.
You are viewing a single comment's thread. Return to all comments →
Here is a crude pseudo-code I am suggesting:
A cathetus of say 12 appears either in basic triplet(5-12-13) form or in expanded triplet form(4*(3-4-5)). Theory says you always have an even-odd tuple for basic catheti and there is a formula for creating only those basic triplets with using a pair of odd coprime numbers.
We have 12 so it may be the even cathetus of a basic triplet, go try it.
12 may be an integer multiple of an expanded triplet. So factor out 12 and take a number at a time to repeat the step-2. Even and odd numbers go into different processes, be careful.
Factors of 12 are 1,2,3,4,6,12. In the example, 2/4 of the cases was obtained using 12 itself: (5-12-13),(12,35,37). One of them is from 4: (9-12-15). The last one is from 3: (12-16-20). Note that there are no basic triplets including 1,2 or 6.(1-0-1) is not acceptable of course.
So the total number of triplets containing 12 can be calculated as the total number of basic triplets that can be obtained from all of 12's factors included.
I think we should first find an efficient factoring algorithm and then another one for basic triplet generator.
Lastly, when I look at the formulas, I can come up with a final procedure in my head,
a. Take the number N. If it is odd, count how many coprime factor pairs it has. Else if it is even, divide by two. If the result is odd, discard the number. If the result is even, count how many coprime factor pairs the result has.
b. Take a factor of N, repeat the "step a" with this number.
c. Repeat for all factors and count all them up.
Some examples:
12 --> even --> 12/2 = 6 --> even --> 6 = 2*3 or 1*6. (2)
6 --> even --> 6/2 = 3 --> odd --> discard it. (0)
4 --> even --> 4/2 = 2 --> even --> 2 = 1*2 (1)
3 --> odd --> 3 = 1*3 (1)
2 --> even --> 2/2 = 1 --> odd --> discard it. (0)
Total = 4
Similarly, for 15,
15 = 3*5 or 1*15
5 = 1*5
3 = 1*3
total = 4
for 60, 60 = 2^2*3*5 --> 2*3*5 (4 comb.)
30 = 2*3*5 discard
20 = 2^2*5 --> 2*5 (2 comb.)
15 = 3*5 (2 comb.)
12 = 2^2*3 (4 comb. already solved)
10 = 2*5 discard
6 = 2*3 discard
4 = 2^2 (1 comb.)
3 = 3 (1 comb.)
2 = 2 discard
Total = 14