Problem 52834. Easy Sequences 32: Almost Pythagorean Triples
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.
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.
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.
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.
Hi William, the output should be the perimeter, not the triangle sides…
Problem Recent Solvers4
Find common elements in matrix rows
Convert to Binary Coded Decimal
More from this Author102
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!