An Almost Pythagorean Triple (abbreviated as "APT'), is a set of 3 integers in which square of the largest element, which we will call as its 'hypotenuse', is 1 less than the sum of square of the smaller elements (shorter sides). This means that if c is the hypotenuse and a and b are the shorter sides, 
, satisfies the following equation:
, satisfies the following equation: 
where: 
The smallest is the triple 
, with 
and perimeter (the sum of the 3 elements) of 
. Some researchers consider 
as the smallest , but here, we will only look at 's where the hypotenuse is "strictly" greater than the other shorter sides. Other examples of 's are 
, and 
.
is the triple , with and perimeter (the sum of the 3 elements) of . Some researchers consider as the smallest , but here, we will only look at 's where the hypotenuse is "strictly" greater than the other shorter sides. Other examples of 's are , and . Unfortunately, unlike Pythagorean Triples, a 'closed formula' for generating all possible 's, has not yet been discovered, at the time of this writing. For this exercise, we will be dealing with 's with a known ratio between the hypotenuse and the shortest side: 
.
's, has not yet been discovered, at the time of this writing. For this exercise, we will be dealing with 's with a known ratio between the hypotenuse and the shortest side: . Given the value of r, find the perimeter of the with the r-th smallest perimeter. For example for 
, that is 
, the smallest perimeter is 
for 
, while the second (r-th) smallest perimeter is 
, for the with dimensions 
. For 
, the third smallest perimeter is 
for 
.
with the r-th smallest perimeter. For example for , that is , the smallest perimeter is for , while the second (r-th) smallest perimeter is , for the with dimensions . For , the third smallest perimeter is for . The output can be very large, so please present only the last 12 digits if the number of digits of the perimeter exceeds 12.
Solution Stats
Problem Comments
12 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers5
Suggested Problems
-
Find all elements less than 0 or greater than 10 and replace them with NaN
15777 Solvers
-
2550 Solvers
-
Put two time series onto the same time basis
349 Solvers
-
Find last zero for each column
689 Solvers
-
639 Solvers
More from this Author116
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
I think the inequalities at the top of the problem must be backwards. In the example, c = 2*a, so c > a.
Hi William, Your right. I'd already changed. This should not affect the solution, though.
Hi Ramon,
Many of your "Easy" sequence problems have been challenging and fun. But here I am confused. I get the correct solutions for Tests 1 through 3. For Test 4 (and higher) I have problems. My result for Test 4 is p = 209737287485879. When I try to calculate a, b and c from r and the given value of p_correct (using Python3 and math.isqrt to handle large integers) I fail to find integer values.
Have I missed some important point here?
The p_correct values contain only the last 12 digits.
It seems I stopped reading (or absorbing what I read) before the last line of the problem description. Thanks to Tim for the clarification.
Hi, Are,
Sorry, I haven't look at the comments lately. I thought no one's gonna answer this one. Thanks Tim, for the clarification...
Like David Hill, my answer matches the test cases where n<=10, but not for larger ones. I've been driving myself batty the last couple of days trying to figure out where I went wrong. Then I realized that the test cases have it wrong. I can't prove I'm right, but I can prove them wrong:
Consider the defining condition: c² = a² + b² - 1.
Rearrange: c² - a² - b² = -1.
Modulo 2: c² - a² - b² ≡ 1 (mod2).
As squaring and negation preserve parity (value mod 2),
c + a + b ≡ 1 (mod2)
And all of the answers in the test cases are even for n>10.
My "double" solution matches my int64 solution up through 1000 but not 10,000, which is what I expected as flintmax is ~9e15.. My double solution (generates even perimeters for 10k+) is size 59, my int64 is 63.
I didn't run calculateSize() before trying to figure out what was up, but what I learned through that definitely shaved some points. The largest single value test case(~12e5) runs on my laptop in just under 200ms, and should run in O(n) time and constant memory. It will start overflowing when n hits about 45e5. uint64 will take it to about 9e6.
@Ramon Villamangca, there's definitely an issue with the larger test cases in this problem. From the definition and tracking parity, the perimeter of an APT MUST be odd.
the test suite is correct. You are losing precision due to the sqrt operation. Hint: try using Pells equation, instead of brute force
The test suite is clearly INCORRECT; proof follows.
* The defining equation of an APT is c^2 = a^2 + b^2 - 1.
* Rearrange to a^2 + b^2 - c^2 = 1.
* This means that of a^2, b^2, and c^2, either exactly one is odd, or all three are odd.
* Either way, either exactly one or all three of a, b, and c are odd.
* Therefore the perimeter a + b + c is odd.
* Yet test cases s 5, 7, 8, and 9 10 ask for the perimeter of a single triangle, and report that it is even. Whatever triangle you came up with, it is NOT an APT.
* Test cases 5, 7, 8, and 9 are incorrect.
I suspect #6 is incorrect, but don't have a simple proof.
I dug a little deeper. I have converted to a Pell Equation, and I am not using anything but addition, subtraction, and multiplication..
* Using double, at r=97, the calculation of b (x in Pell) produces pre-modulo results exceeding flintmax('double')
* By using uint64, I can get to r=4296 before hitting an integer overflow.
But, I just noticed a solution that should work.
If you don't believe me, try your solution keeping only six digits of precision and see if you get a compatible answer.