哈斯克尔汉明数字

Question

我需要定义唯一素数因子为2,3和5的汉明数字列表.(即2 ^ i*3 ^ j*5 ^ k形式的数字.序列以1,2,3,4,5,6,8,9,10,12,15 ......开头)

我可以使用该factors功能或其他方式.在factors下面应该返回其参数的因素.我相信我已经正确实施了它.

   factors :: Int -> [Int]
   factors n = [x | x <- [1..(div n 2) ++ n], mod n x == 0]

我试图使用列表推导来制作2 ^ i*3 ^ j*5 ^ k的列表但是仍然坚持写保护:

hamming :: [Int]
hamming = [n | n <- [1..], „where n is a member of helper“]

helper :: [Int]
helper = [2^i * 3^j * 5^k | i <- [0..], j <- [0..], k <- [0..]]

Answer 1

我可以使用该factors功能或其他方式.

我建议不这样做.

一种简单的方法是实现一个函数来获得一个数字的素数因子化,然后就可以了

isHamming :: Integer -> Bool
isHamming n = all (< 7) $ primeFactors n

然后将用于过滤所有正整数的列表:

hammingNumbers :: [Integer]
hammingNumbers = filter isHamming [1 .. ]

另一种方法,更有效的是避免划分和过滤,并创建仅汉明数字的列表.

一种简单的方法是使用一个数字n是汉明数的事实,当且仅当

• n == 1, 要么
• n == 2*k,k汉明数字,或
• n == 3*k,k汉明数字,或
• n == 5*kk汉明数字在哪里.

然后你可以创建所有汉明数字的列表

hammingNumbers :: [Integer]
hammingNumbers = 1 : mergeUnique (map (2*) hammingNumbers)
                                 (mergeUnique (map (3*) hammingNumbers)
                                              (map (5*) hammingNumbers))

其中mergeUnique合并两个排序列表在一起,删除重复.

这已经相当有效,但可以通过避免从一开始就产生重复来改进它.