cyclotomic_polynomial.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 27 May 2019
# https://github.com/trizen

# Efficient formula for computing the n-th cyclotomic polynomial.

# Formula:
#   cyclotomic(n, x) = Prod_{d|n} (x^(n/d) - 1)^moebius(d)

# Optimization: by generating only the squarefree divisors of n and keeping track of
# the number of prime factors of each divisor, we do not need the Moebius function.

# See also:
#   https://en.wikipedia.org/wiki/Cyclotomic_polynomial

func cyclotomic_polynomial(n, x) {

    # Generate the squarefree divisors of n, along
    # with the number of prime factors of each divisor
    var d = []
    for p in (n.factor.uniq) {
        d << d.map_2d {|q,e| [p*q, e+1] }...
        d << [p, 1]
    }

    d << [1, 0]

    # Multiply the terms
    d.map_2d {|p,e|
        (x**(n/p) - 1)**((-1)**e)
    }.prod
}

say cyclotomic_polynomial(5040, 4/3)
say 20.of { cyclotomic_polynomial(_, 2) }   #=> [0, 1, 3, 7, 5, 31, 3, 127, 17, 73, 11, 2047, 13, 8191, 43, 151, 257, 131071, 57, 524287]