The nth Cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial of largest degree with integer coefficients that is a divisor of x^n − 1, and is not a divisor of x^k − 1 for any k < n.



Task

 Find and print the first 30 cyclotomic polynomials.
 Find and print the order of the first 10 cyclotomic polynomials that have n or -n as a coefficient.


See also
 Wikipedia article, Cyclotomic polynomial, showing ways to calculate them.
 The sequence A013594 with the smallest order of cyclotomic polynomial containing n or -n as a coefficient.
import Data.List
import Data.Numbers.Primes (primeFactors)
 
negateVar p = zipWith (*) p $ reverse $ take (length p) $ cycle [1,-1]
 
lift p 1 = p
lift p n = intercalate (replicate (n-1) 0) (pure <$> p)
 
shortDiv :: [Integer] -> [Integer] -> [Integer]
shortDiv p1 (_:p2) = unfoldr go (length p1 - length p2, p1)
  where
    go (0, _) = Nothing
    go (i, h:t) = Just (h, (i-1, zipWith (+) (map (h *) ker) t))
    ker = negate <$> p2 ++ repeat 0
 
primePowerFactors = sortOn fst . map (\x-> (head x, length x)) . group . primeFactors
 
-- simple memoization
cyclotomics :: [[Integer]]
cyclotomics = cyclotomic <$> [0..]
 
cyclotomic :: Int -> [Integer]
cyclotomic 0 = [0]
cyclotomic 1 = [1, -1]
cyclotomic 2 = [1, 1]
cyclotomic n = case primePowerFactors n of
  -- for n = 2^k
  [(2,h)]       -> 1 : replicate (2 ^ (h-1) - 1) 0 ++ [1]
  -- for prime n
  [(p,1)]       -> replicate n 1
  -- for power of prime n
  [(p,m)]       -> lift (cyclotomics !! p) (p^(m-1))
  -- for n = 2*p and prime p
  [(2,1),(p,1)] -> take (n `div` 2) $ cycle [1,-1]
  -- for n = 2*m and odd m
  (2,1):_       -> negateVar $ cyclotomics !! (n `div` 2)
  -- general case
  (p, m):ps     -> let cm = cyclotomics !! (n `div` (p ^ m))
                   in lift (lift cm p `shortDiv` cm) (p^(m-1))