haskell列表理解(数论问题)

Question

我在haskell尝试解决了以下问题：

求最小数b与(a^b mod 100) =1，对于每a与gcd(a,100)=1

我试过这个：

head[ b | a <- [1..], b <- [1..], (a^b `mod` 100) == 1, gcd a 100 == 1]

但这会产生1^1作为第一个解决方案，这是不正确的，它应该是对每一个；例如，3^1不是一个解决方案。我认为正确的解决方案是b=20，但我想在haskell中找到它。

Answer 1

找出最小的b数

find f [1..]

(a^b mod 100) =1(A)

f b = all (\a -> a^b `mod` 100 == 1) xs

A与gcd(a,100)=1

    where xs = [a <- [1..100], gcd a 100 == 1]

Answer 2

“为每个a”部分是一个无限集，所以您不应该期望用直接的蛮力解决这个问题。你需要更多的数论。

无论如何，假设一个直接的解决方案是可能的，这里的问题是a <- .，b <- .就是找到所有的a和b值，willy nilly。你需要下一些订单才能得到你想要的东西：

bs = [b | b <- [1..],
         (and [(a `mod` b)==1 | a <- [1..])
     ]

其中，和函数返回列表中的所有元素是否为true。(仍然不能工作，因为a <- [1..]是无限的，这意味着and要么返回False，要么永远返回循环)。

Answer 3

据我所知，列表理解以相反的外观顺序迭代每个绑定变量：

[ (x,y) | x <- [0,1], y <- [0,1] ] == [(0,0),(0,1),(1,0),(1,1)]
[ (x,y) | x <- [0,1], y <- [0..] ] == [(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),...]
[ (x,y) | x <- [0..], y <- [0,1] ] == [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),...]

在无限列表的情况下，会遇到这样的问题。上面的第二个例子展示了无限列表中的一个变量如何阻止另一个变量的变化，但是第三个例子显示，更改顺序可以解决这个问题。

演示当前列表理解是如何在a和b中迭代的

[ (a,b) | a <- [1..], b <- [1..] ] == [(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),...]

这个问题类似于第二个例子。我不知道足够的数论，以帮助您进一步有效的解决方案，但这是您的实现的根本问题。