On 15/05/2013, at 2:57 AM, John wrote:
Hi,
I have to write a function which returns a list of all pairs (x,y) where x, y ∈ N AND: – x is the product of two natural numbers (x = a · b, where a, b ∈ N) AND – x is really bigger than 5 but really smaller than 500, AND – y is a squer number (y = c² where c ∈ N) NOT greater than 1000, AND – x is a divisor of y.
Step 1. If a >= 0 and b >= 0 & x = a*b & x < 500 & x > 5 then a > 0 and a < 500 and b > 0 and b < 500. This suggests something like xs = [x | a <- [1..499], b <- [1..499], let x = a*b, 5 < x, x < 500 ] Step 2. However, that will generate duplicates. If a*b = x then b*a = x, and non-square values of x will be generated twice. Let's just filter [6..499]. If x is in that range, and a is a number in the range [1..x-1], and x `mod` a is zero, then x = a*b for some integer b, and b will _have_ to be in the range you are looking for. xs = [x | x <- [6..499], or [x `mod` a == 0 | a <- [1..x-1]] ] xs has 494 elements. At first I was surprised to see that 7 was in the list. However, if x = 7, a = 7, b = 1, then indeed a and b are natural numbers and x is there product, so _every_ number in the range 6..499 qualifies. Step 3. If c >= 0 and y = c*c and y <= 1000 then c >= 0 and c <= 31 This gives us ys = [c*c | c <- [0..31]] or even ys = map (^2) [0..31] which of course has 32 elements. Step 4. Now all that's left to test is whether x divides some y: [(x,y) | x <- xs, y <- ys, y `mod` x == 0 pairs :: [(Int,Int)] pairs = [(x,y) | x <- xs, y <- ys, y `div` x == 0] where xs = [x | x <- [6..499], or [x `mod` a == 0 | a <- [1..x-1]]] ys = [c*c | c <- [0..31]] This has 641 elements. If the definition was supposed to be that x is a *composite* number with factors a, b, then we need to search for "a" in the range [2..x1]. Using pairs = [(x,y) | x <- xs, y <- ys, y `div` x == 0] where xs = [x | x <- [6..499], or [x `mod` a == 0 | a <- [2..x-1]]] ys = [c*c | c <- [0..31]] -- ^ xs has 402 elements and pairs has 546 elements.
listPairs :: [(Int, Int)] listPairs = [(x,y) | x<-[0..], y<-[0..], x<-[0..]*[0..], x > 5, x < 500, (y*y) < 1001, mod y x == 0]
However it doesn't work unfortunatly
Could anyone tell me where my mistake is?
One mistake is that [0..]*[0..] is a type error. * wants a pair of numbers, and [0..] is not a number. (There are modules that make lists "numbers", but then as*bs is usually the same as zipWith (*) as bs, which is not what you want anyway.) The main mistake is that [x | x <- [0..], x > 5, x < 500] is equivalent to for (x = 0; true; x++) if (x > 5 && x < 500) yield x That is, the [0..] part is happy to keep on generating increasing integers, it neither knows, nor does it care, that there is an x < 500 test downstream. If you really want an infinite set searched, by all means use [0..]. But if you only want a finite range, put BOTH bounds in the interval so that it will stop.