哈斯克尔列表理解（数论问题）

与 GCD找到最小的号码B与（A^B MOD 100）= 1，每一个（一，100）= 1

我尝试这样做：

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

但是这产生1^1作为第一个解决方案，这是不正确的，它应该是每;例如3^1不是一个解决方案。我认为正确的解决方案是b = 20，但我希望它在哈斯克尔。

来源

2011-05-23 spore234

你打算如何显示这个适用于*每一个* gcd（a，100）= 1与彻底搜索无限？ – pat 2011-05-23 17:16:44

@pat：由于* a *^* b * mod 100 =（* a * -100）^ * b * mod 100，因此检查所有a <= 0 <100就足够了。 – fuz 2011-05-23 18:22:56

找到最小的数B

find f [1..]

具有：（a^B MOD 100）= 1对于每一个

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

[每一个]与满足gcd（A，100）= 1

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

来源

2011-05-23 19:26:16

谢谢，这正是我正在寻找 – spore234 2011-05-23 20:22:56

@ spore234：请确定这个答案是正确的，如果你知道如何。 – Tom 2011-05-23 21:15:50

@ spore234如果你喜欢答案，你可以通过点击向上箭头来加入它。（我认为这需要15个声望，你现在拥有）。要接受答案，只需用向上/向下箭头点击其复选标记即可。 – 2011-05-23 21:27:27

这似乎是λ（x）的使用Carmichael funktion。它可以计算最小的指数米，使得一个^米≡1模X所有一个使得满足gcd（一个，X）= 1成立。因为λ（100）= 20，b你正在寻找的是20

可以计算所有模块使用下面的未经测试的Haskell表达的溶液（上述式中的X），这是该方法的或多或少的直接翻译维基百科的文章中解释：

import Data.Numbers.Primes 

carmichael 1 = 1 
carmichael 2 = 1 
carmichael 4 = 2 
carmichael n | isPowerOf 2 n = n `div` 4 
      | isPowerOf fac1 n = (n `div` fac1) * (fac1 - 1) 
      | otherwise  = foldr1 lcm $ map (carmichael . product) grp 
    where [email protected](fac1:_) = primeFactors n 
     grp    = group factors 

isPowerOf n k | n == k   = True 
       | k `mod` n == 0 = isPowerOf n (k `div` n) 
       | otherwise  = False

来源

2011-05-23 17:23:02 fuz

+1：Carmichael函数是正确的... – 2011-05-23 17:41:44

@Aryabhatta：刚刚在'mathematics.se'上了解到了它＃ – fuz 2011-05-23 18:38:37

@Fuz：是的，我在那见过你:-) – 2011-05-23 18:43:40

的“为每一个”部分是一个无限集，所以你不应该指望通过直接蛮力解决方案来解决这个问题。你需要更多的数字理论。

总之，假设一个直接的解决方案是可能的，这里的问题是，一个< - [...]，B < - [...] 只是找出所有对a和b价值观，无所畏惧。您需要进行一些订购以获得您想要的内容：

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

其中，函数返回列表中的所有元素是否都为真。（仍然不起作用，因为a <- [1..]是无限的，这意味着and或者永远返回False或循环）。

来源

2011-05-23 17:24:45 hugomg

我会写第二行'（all（== 1）[mod a b | a < - [1 ..]]）''。另外，如果你只想解决这个特殊的问题，你可以将'a'限制为'[1..100]'。 – 2011-05-23 19:16:21

据我所知，列表内涵迭代在外观上的相反顺序每个绑定变量：

[ (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),...]

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

来源

2011-05-23 19:20:32 Tom

哈斯克尔列表理解（数论问题）

回答

相关问题