Finding tribonacci pseudoprimes

trib.hs

-- A semi-fast isPrime algorithm

noDivs factors n = foldr (\f r -> f*f > n || (rem n f /= 0 && r))
                         True factors

primesTD = 2 : 3 : filter (noDivs $ tail primesTD) [5,7..]

isPrime n = n > 1 && noDivs primesTD n

divides a b = b `mod` a == 0

-- Computes the nth tribonacci-like number in O(n) time

trib n =
    let iter a b c count = if count == n
        then a
        else iter (a+b+c) a b (count+1)
     in case n of
        0 -> 3
        1 -> 1
        2 -> 3
        otherwise -> iter 3 1 3 2

-- Definition of what it means to be a tribonacci pseudoprime

pseudo n = (n `divides` (trib n - 1)) && (not (isPrime n))

-- Dirty hackery: for n = 2,3,... print n if n is a tribonacci pseudoprime or n is a multiple of 1000 (to keep track of how much processing we've done)

findPseudos = map fst $ filter (\x -> (snd x == True) || 1000 `divides` fst x) $ zip [2..] (map pseudo [2..])