понимание списка haskell (проблема теории чисел)

Question

Я попытался решить следующую проблему в haskell:

Найдите наименьшее число b с помощью (a ^ b мод 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, но я хочу его в haskell.

Answer 1

Это, кажется, использование функции Carmichael λ (x).Он вычисляет наименьший показатель степени м , такой что a ^m mod 1 мод x для всех a , такой, чтоgcd ( a , x ) = 1 выполняется.Поскольку λ (100) = 20, b , который вы ищете, равен 20.

. Вы можете рассчитать решение для всех модулей ( x в приведенной выше формуле) с использованием следующего непроверенного выражения Haskell, которое является более или менее прямым переводом метода, описанного в статье Википедии:

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 factors@(fac1:_) = primeFactors n
        grp              = group factors

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

Answer 2

Найдите наименьшее число 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 3

Часть «для каждого а» - это бесконечное множество, поэтому не стоит ожидать решения этой проблемы с помощью прямого перебора.Здесь вам нужно больше теории чисел.

---

В любом случае, предполагая, что прямое решение возможно, проблема в том, что a <- [...], b <- [...] простоНаходя все пары значений a и b, Вилли Нилли.Чтобы получить то, что вы хотите, вам нужно ввести в порядок: </p>

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

Где функция и возвращает, все ли элементы в списке истинны.(Все еще не работает, так как a <- [1..] бесконечен, то есть and либо возвращает False, либо циклы навсегда).

Answer 4

Насколько мне известно, списочные выражения повторяют каждую связанную переменную в обратном порядке появления:

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

Эта проблема аналогична проблеме второго примера.Я не знаю достаточно теории чисел, чтобы помочь вам в дальнейшем эффективном решении, но это фундаментальная проблема вашей реализации.