math - Would this be a suitable way to find pythagorean triples in haskell? - Stack Overflow

admin管理员组

文章数量:1125772

I came across this question asking me to find all pythagorean triples of natural numbers, such that all 3 numbers are co-primes, in ascending order of c.

I came up with this solution, using a function to filter out the multiples and then a list comprehension.

sieve :: [Int] -> [Int]
sieve (x:xs) = filter (multiple x) xs
    where multiple a b = b `mod` a == 0


pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [(a,b,c) | c <- [1..], b <- sieve (c : [1..c]), a <- sieve (c:[1..c]), a*a + b*b == c*c]

The answer in the model answers was much more complicated, including trying to find the remainder of all 3 numbers with the first. Would this still work as intended?

I came across this question asking me to find all pythagorean triples of natural numbers, such that all 3 numbers are co-primes, in ascending order of c.

I came up with this solution, using a function to filter out the multiples and then a list comprehension.

sieve :: [Int] -> [Int]
sieve (x:xs) = filter (multiple x) xs
    where multiple a b = b `mod` a == 0


pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [(a,b,c) | c <- [1..], b <- sieve (c : [1..c]), a <- sieve (c:[1..c]), a*a + b*b == c*c]

The answer in the model answers was much more complicated, including trying to find the remainder of all 3 numbers with the first. Would this still work as intended?

• haskell
• math
• functional-programming

Share Improve this question Follow asked 2 days ago internationalmysterymaninternationalmysteryman 1111 bronze badge New contributor internationalmysteryman is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. 1

• a and b here are not guaranteed to be coprime, only a and c are. But the sieve also does not check if numbers are co-prime, it does the opposite, and only retains multiples of x . – willeM_ Van Onsem Commented 2 days ago

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

The code never returns a solution, partly because the sieve has been implemented the wrong way. Indeed, if you want two items to be co-prime, the sieve should thus retain all items that do not share another factor except 1. For example:

sieve :: Int -> [Int] -> [Int]
sieve x xs = filter (coprime x) xs
    where coprime x y = gcd x y == 1

then we can work with:

pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [(a,b,c) | c <- [1..], let bs = sieve c [2 .. c], b <- bs, a <- sieve b bs, a*a + b*b == c*c]

But here the sieve probably will only increase the work, why not just use:

pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [
  (a,b,c)
  | c <- [2..]
  , b <- [2..c-1]
  , gcd b c == 1
  , a <- [2..c-1]
  , gcd a b == 1
  , gcd a c == 1
  , a*a + b*b == c*c
  ]

or if we want unique triples (i.e. not swapping the values of a and b), we can use:

pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [
  (a,b,c)
  | c <- [2..]
  , b <- [2..c-1]
  , gcd b c == 1
  , a <- [2..b-1]
  , gcd a b == 1
  , gcd a c == 1
  , a*a + b*b == c*c
  ]

本文标签： mathWould this be a suitable way to find pythagorean triples in haskellStack Overflow