有效地找到Haskell中的除数的数量

Question

试图在Haskell中解决项目Euler上的问题12.

通过添加自然数来生成三角数的序列.

所以第7个三角形数字是1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.前十个术语是:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

让我们列出前七个三角形数字的因子:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
 We can see that 28 is the first triangle number to have over five divisors.

拥有超过500个除数的第一个三角形数的值是多少？

我的解决方案适用于少量除数(例如,给定5,它返回28),但是当输入500时,它似乎无限期地挂起.

-- Lazily generates infinite list of triangle numbers.
triangleNumbers :: [Integer]
triangleNumbers = map (\x -> sum [1..x]) [1..]

-- Given a number, returns the a tuple of how many divisors it has and the number.
numDivisors :: Integer -> (Int, Integer)
numDivisors num = (length [x | x <- [1..num], num `mod` x == 0], num)

p12 :: Integer
p12 = snd $ head $ filter (\x -> fst x > 500) $ map numDivisors triangleNumbers

你知道我可能做错了什么吗？谢谢!

Answer 1

另一个问题是你生成的三角形数字,虽然正确,但效率非常低.例如,要计算你正在求和的第11个数字[1..11],然后计算你正在求和的第12个数字[1..12],它不使用先前计算的结果.

正如我在评论中提到的,您可以直接使用计算第n个三角形数字n*(n+1)/2.但是,即使您不知道这个公式,也可以通过使用这样的递归来利用连续三角数之间的相似性:

triangulars = go 1 2
  where go s n = s : go (s+n) (n+1)

这种递归也被scanl函数捕获:

triangulars = scanl (+) 1 [2..]