Create infinite list in Haskell of k-composite numbers

user_8604329 0
Viewed 819

A k-composite number is a composite number with k factors excluding 1 and itself. I'm trying to write code that will take in an integer k and return an infinite list of all k-composites. So using take 5 $ kcomposite 2 will return [6,8,10,14,15]. I wrote two functions to accomplish this:

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

kcomposite ::  Int -> [Int]
kcomposite n = [x | x <- [1..], (length (factors n)) == (x-2)]

I have no trouble compiling, but when I try to run them, the ghci never stops running. This makes sense because of the infinite list, but this happens even when I only try to get the first few elements in the list, like in the above example. I can't understand what I'm doing wrong.

list function haskell
2 Answers

A k-composite number is a composite number with k factors excluding 1 and itself

Since your factors function returns all factors of a number (including 1 and itself), this number will be greater than the provided k. That's why you need to compare with k + 2 instead of k - 2

Also, when k is less than 0 you'll still get the program never stop running, that's why you might want to process this edge case.

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

kcomposite ::  Int -> [Int]
kcomposite k
  | k < 0 = []
  | otherwise = [x | x <- [1..], length (factors x) == (k + 2)]
user_21996000

Here is my slightly different approach for this task which is much more efficient.

The boosting key is to not check all the way to the end but only up to its square root. I mean if we want to find composites of 100 we don't need to control all 100 numbers. We only need to control up to sqrt 100 (like [2..10]) to see (mod 100 x) == 0. We start from 2 since you don't want 1 and the number itself. Once we have the satisfying numbers 100 div x should give us the other one. So if 2 is a composite then 100 div 2 (50) is another one like 4 yields 25 and 5 yields 20. Of course when we come to 10 it will give us another 10 and we will only evaluate one of them. Cool..!

So this is the code

kcomposites :: Int -> [Int]
kcomposites k = 
  let factors n = concat [bool [x, n `div` x] [x] (x^2 == n) 
                          | x <- [2..limit], n `mod` x == 0]
          where limit = truncate . sqrt . realToFrac $ n
  in foldr (\n rs -> bool rs (n:rs) (k == (length . factors $ n))) [] [2..]

Here is this code's performance for k = 19 for first 5 elements;

*Main> take 5 . kcomposites $ 19
[576,1600,2916,3136,7744]
(0.43 secs, 174,826,272 bytes)

and here is your code's performance for k = 19 for first 5 elements;

*Main> take 5 . kcomposite $ 19
[576,1600,2916,3136,7744]
(17.61 secs, 6,246,022,504 bytes)

Note: I wouldn't advice checking for k = 5 for 5 elements. Even this code took like 15 minutes to come up with [64,729,15625,117649,1771561] the above code will probably take a crazy amount of time (like a day or more perhaps).

Lets compare them with take 3.

*Main> take 3 . kcomposites $ 5
[64,729,15625]
(1.14 secs, 472,228,880 bytes)

*Main> take 3 . kcomposite $ 5
[64,729,15625]
(69.84 secs, 25,409,801,688 bytes)
user_45432070
Related