0

how can I calculate how many Pythagorean triangles share the same hypotenuse?

I don't need the parameters of the triangles, just how many are there, with the fastest time possible.

from math import sqrt
def hypotenuse(n):
    count = 0
    hypotenuse = n
    for x in range(1, int(n / (sqrt(2))) + 1):
        y = (((hypotenuse * hypotenuse) - (x * x)) ** 0.5)
        if y % 1 == 0:
            count += 1
                 
    return count

this is the code I have written but it turns out to be too slow.

UPDATE

I have changed the duplication method to sets instead of lists (even removed it completely) and changed the range from (1, n) to (1, int(n / sqrt(2))) still not fast enough

pouya_ghahari
  • 38
  • 8
  • 1
    How fast do you need it to be? – Thomas Jul 08 '22 at 08:04
  • 2
    You get duplicates because you try every `x` up to `n` - just don't go that far, you'll spare the time of generating the duplicates and the time to remove them, and you'll also know faster if there is no solution. – Thierry Lathuille Jul 08 '22 at 08:05
  • @Thomas it should take less than 1 sec with n <= 10 ^ 9 – pouya_ghahari Jul 08 '22 at 08:06
  • I think `if x in tr` makes it O(n^2), if you would use a set it would be O(n). But I'm not sure because I don't know how python handles arrays or lists. – maraca Jul 08 '22 at 08:07
  • 4
    note that `if x in tr:` gets slower and slower as the list expands (not sure how big this can get, though). You can skip the "no duplicate" check, though, by limiting the check to `x < y` (as things in `y>x` will be just a repeat of it, and `x==y` is impossible for integer hypotenuse). So, just checking from `1` to `hypotenuse / sqrt(2)` should be enough. – qrsngky Jul 08 '22 at 08:11
  • 1
    Note that using `hypotenuse / 2` will miss `3` when `n=5` – qrsngky Jul 08 '22 at 08:19
  • 3
    Python is too slow to do an exhaustive search of 1e9 possibilities in 1 second. It might be possible in a compiled language. But if you must use Python, you might investigate [a faster algorithm](https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple). – Thomas Jul 08 '22 at 08:25
  • 1
    But note that even after optimizing this method (limiting `x` to `sqrt(n)`, calculating `hypothenuse ** 2` only once and storing it, and using the `y.is_integer` method of floats which is faster than `y % 1 == 0`, this method still takes about 4 seconds for n = 1e7. You would need a completely different approach to reach your goal. – Thierry Lathuille Jul 08 '22 at 08:25
  • @qrsngky still not fast enough, I have come up with a formula with n(1) but only works when you have the perimeter of the triangle. – pouya_ghahari Jul 08 '22 at 08:26
  • I’m voting to close this question because it appears to be purely a question about number theory. Please try [math.se], and/or starting research with https://en.wikipedia.org/wiki/Pythagorean_triple. – Karl Knechtel Jul 08 '22 at 08:32
  • That said, trying to do a computation like `y = (((hypotenuse * hypotenuse) - (x * x)) ** 0.5)` and then checking if the result "is an integer" with `% 1` cannot reliably work; please see https://stackoverflow.com/questions/588004/. – Karl Knechtel Jul 08 '22 at 08:34
  • I tried various things, and got 1.75 seconds for `1e7` and 17.75 seconds for `1e8`, and 166.7 seconds for `1e9`. Definitely not fast. And probably won't be that much faster even if you use another language. – qrsngky Jul 08 '22 at 08:42
  • @Thomas. Few languages are interpreted or compiled per se. Python can be compiled even though most implementations of the language maybe are not. –  Jul 08 '22 at 21:57
  • True. Using e.g. Cython or PyPy might also do the trick. But I got the impression that OP is doing this for learning purposes, so switching out the tech to achieve a performance goal would probably not be helpful. – Thomas Jul 10 '22 at 08:25

0 Answers0