Problem 52834. Easy Sequences 32: Almost Pythagorean Triples
Solution Stats
Problem Comments

9 Comments
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.
Solution Comments

2 Comments
I know I can't use symbolics, but I was just checking to see if my algorithm was correct. It matches the test suite for r <=10 (before needing to mod for the last 12 digits), but not for larger r's. It seems like it should be correct. I must be missing something. Not sure if you want to provide me with a hint.
HINT: An optimized solution can be obtained via Pell's equation.

1 Comment
Hi William, the output should be the perimeter, not the triangle sides…
Problem Recent Solvers4
Suggested Problems

3237 Solvers

Return a list sorted by number of occurrences
2076 Solvers

Longest run of consecutive numbers
4105 Solvers

Convert from Base 10 to base 5
245 Solvers

4268 Solvers
More from this Author90
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!