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
Show commentsProblem Recent Solvers4
Suggested Problems
-
1124 Solvers
-
612 Solvers
-
07 - Common functions and indexing 1
432 Solvers
-
545 Solvers
-
152 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!