haskell list comprehension (number theory problem)

Question

I tried solving the following problem in haskell:

Find the smallest number b with (a^b mod 100) = 1 for every a with gcd(a,100)=1

I tried this:

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

but this yields 1^1 as the first solution, which is not correct, it should be for every ; 3^1 is not a solution for example. I think the correct solution is b=20 but I want it in haskell.

Answer 1

This seems to be a use of the Carmichael funktion λ(x). It calculates the smallest exponent m, such that a^m ≡ 1 mod x for all a such that gcd(a, x) = 1 holds. Because λ(100) = 20, the b you are looking for is 20.

You can calculate the solution for all modules (the x in the above formula) using the following untested Haskell expression, which is a more or less direct translation of the method explained in the Wikipedia article:

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

Find the smallest number b

find f [1..]

with (a^b mod 100) = 1 for every a

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

[every a] with gcd(a,100)=1

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

Answer 3

The "for every a" part is an infinite set, so you shouldn't expect to solve this problem with a direct brute force solution. You need more number theory here.

---

Anyway, assuming a direct solution is possible, the problem here is that the a <- [...], b <- [...] is just finding all pairs of a and b values, willy nilly. You need to put some ordering in to get what you want:

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

Where the and function returns whether all elements in the list are true. (Still doesn't work, since the a <- [1..] is infinite, meaning the and either returns False or loops forever).

Answer 4

To my knowledge, list comprehensions iterate each bound variable in reverse order of appearance:

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

In the case of infinite lists, one can run into problems this way. The second example above shows how one variable in an infinite list will prevent another from ever changing, but the third shows that changing the order fixes this.

To demonstrate how your current list comprehension iterates through a and b:

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

This problem is similar to that of the second example. I don't know enough number theory to help you further with an efficient solution, but this is the fundamental problem with your implementation.