Problem 52834. Easy Sequences 32: Almost Pythagorean Triples

Created by Ramon Villamangca

Solve Later

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: 
        
        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 . 
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: . 
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  . 
The output can be very large, so please present only the last 12 digits if the number of digits of the perimeter exceeds 12.

Solve

Solution Stats

10 Solutions
4 Solvers

Last Solution submitted on Oct 07, 2022

Last 200 Solutions

Problem Comments

9 Comments

9 Comments

Show 6 older comments

William on 29 Sep 2021

I think the inequalities at the top of the problem must be backwards. In the example, c = 2*a, so c > a.

Ramon Villamangca on 29 Sep 2021

Hi William, Your right. I'd already changed. This should not affect the solution, though.

Are Mjaavatten on 27 Oct 2021

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?

Tim on 27 Oct 2021

The p_correct values contain only the last 12 digits.

Are Mjaavatten on 1 Nov 2021

It seems I stopped reading (or absorbing what I read) before the last line of the problem description. Thanks to Tim for the clarification.

Ramon Villamangca on 2 Nov 2021

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...

GeeTwo on 25 Oct 2022

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.

GeeTwo on 26 Oct 2022

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.

GeeTwo on 12 Jan 2023

@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 comments

Problem Recent Solvers4

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 52834. Easy Sequences 32: Almost Pythagorean Triples

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author116

Problem Tags

Community Treasure Hunt

Problem 52834. Easy Sequences 32: Almost Pythagorean Triples

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author116

Problem Tags

Community Treasure Hunt

Players