哈克尔的欧拉26

Question

我正在尝试从Haskell的Project Euler 解决问题#26,但我遇到了一些问题.

我已经设法弄清楚倒数的重复周期只与其主要除数有关,所以我认为我只需要找出具有最长重复周期的素数的倒数.所以我在Haskell中编写了一个算法:

isPrime :: Int -> Bool
isPrime k
    | k <= 1    = error "Seriously?"
    | otherwise = null [ x | x <- [2..floor(sqrt(fromIntegral k))], k `mod` x == 0]

lp = [x | x <- [7..1000], isPrime x]

s = map (\n -> head [x | x <- [ceiling(logBase 10 (fromIntegral n))..], 10^x `mod` n == 1]) lp

main::IO()
main = print $ maximum s

但是,它无法产生答案.我已经尝试使用lamda,它可以产生循环周期的数字,有几个素数,我设法得到正确的数字位数(我希望算法没有问题).我还检查了列表的输出s,它[6,2,6,16,18,45,23,15,3,5,63,没有结束.我不知道为什么会这样,因为如果我手动将函数应用于每个素数,我可以得到正确的输出.

任何人都可以告诉我我的代码有什么问题,或者我解决问题的方式结果是错的？谢谢.

Answer 1

Int在这里不是一个好选择,因为你操作相当大的数字,用10^x.Int是的Bounded,所以绕过它的上限:

> maxBound :: Int
9223372036854775807

> (maxBound :: Int) + 1
-9223372036854775808

isPrime完全省略签名,我们得到

> :t lp
lp :: Integral b => [b]

试

> map (\n -> (n, head [x | x <- [ceiling(logBase 10 (fromIntegral n))..],
                           10^x `mod` n == 1])) 
      (lp :: [Int])
[(7,6),(11,2),(13,6),(17,16),(19,18),(23,45),(29,23),(31,15),(37,3),(41,5),(43,63),
 (47,Interrupted.

我们看到你的计算被卡住了47.但是使用[Integer](或者根本没有,所以它默认为Integer自己),我们成功地获得了完整的结果.你只是误解了它.重新阅读问题陈述,你会看到.

_{(另外,上面代码片段中43的答案是不正确的,而7,11,13的答案是正确的.对于更大的数字得到错误的结果是一个强烈的信号,我们有一些整数环绕算术错误正在进行;这是我是怎么发现的.}