Cyclotomic polynomial: Difference between revisions

</pre>

=={{header|Julia}}==

<lang julia>using Primes, Polynomials

# memoize cache for recursive calls

const cyclotomics = Dict([1 => Poly([big"-1", big"1"]), 2 => Poly([big"1", big"1"])])

# get all integer divisors of an integer, except itself

function divisors(n::Integer)

f = [one(n)]

for (p,e) in factor(n)

f = reduce(vcat, [f*p^j for j in 1:e], init=f)

end

return resize!(f, length(f) - 1)

end

"""

cyclotomic(n::Integer)

Calculate the n -th cyclotomic polynomial.

See wikipedia article at bottom of section /wiki/Cyclotomic_polynomial#Fundamental_tools

The algorithm is reliable but slow for large n > 1000.

"""

function cyclotomic(n::Integer)

if haskey(cyclotomics, n)

c = cyclotomics[n]

elseif isprime(n)

c = Poly(ones(BigInt, n))

cyclotomics[n] = c

else # recursive formula seen in wikipedia article

c = Poly([big"-1"; zeros(BigInt, n - 1); big"1"])

for d in divisors(n)

x = cyclotomic(d)

c ÷= cyclotomic(d)

end

cyclotomics[n] = c

end

return c

end

println("First 30 cyclotomic polynomials:")

for i in 1:30

println(rpad("$i: ", 5), cyclotomic(BigInt(i)))

end

println("10465 ", filter(x -> 9 < abs(x) < 15, coeffs(cyclotomic(10465))))

const dig = zeros(BigInt, 10)

for i in 1:1000000

if all(x -> x != 0, dig)

break

end

c = cyclotomic(i)

for coef in filter(x -> -10.0001 < x < 10.0001, coeffs(c))

x = Int(round(abs(coef)))

if 0 < x < 11 && dig[x] == 0

dig[x] = coef < 0 ? -i : i

end

end

end

for (i, n) in enumerate(dig)

println("The cyclotomic polynomial Φ(", abs(n), ") has a coefficient that is ", n < 0 ? -i : i)

end

</lang>{{out}}

<pre>

First 30 cyclotomic polynomials:

1: Poly(-1 + x)

2: Poly(1 + x)

3: Poly(1 + x + x^2)

4: Poly(1.0 + 1.0*x^2)

5: Poly(1 + x + x^2 + x^3 + x^4)

6: Poly(1.0 - 1.0*x + 1.0*x^2)

7: Poly(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)

8: Poly(1.0 + 1.0*x^4)

9: Poly(1.0 + 1.0*x^3 + 1.0*x^6)

10: Poly(1.0 - 1.0*x + 1.0*x^2 - 1.0*x^3 + 1.0*x^4)

11: Poly(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10)

12: Poly(1.0 - 1.0*x^2 + 1.0*x^4)

13: Poly(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12)

14: Poly(1.0 - 1.0*x + 1.0*x^2 - 1.0*x^3 + 1.0*x^4 - 1.0*x^5 + 1.0*x^6)

15: Poly(1.0 - 1.0*x + 1.0*x^3 - 1.0*x^4 + 1.0*x^5 - 1.0*x^7 + 1.0*x^8)

16: Poly(1.0 + 1.0*x^8)

17: Poly(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12 + x^13 + x^14 + x^15 + x^16)

18: Poly(1.0 - 1.0*x^3 + 1.0*x^6)

19: Poly(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12 + x^13 + x^14 + x^15 + x^16 + x^17 + x^18)

20: Poly(1.0 - 1.0*x^2 + 1.0*x^4 - 1.0*x^6 + 1.0*x^8)

21: Poly(1.0 - 1.0*x + 1.0*x^3 - 1.0*x^4 + 1.0*x^6 - 1.0*x^8 + 1.0*x^9 - 1.0*x^11 + 1.0*x^12)

22: Poly(1.0 - 1.0*x + 1.0*x^2 - 1.0*x^3 + 1.0*x^4 - 1.0*x^5 + 1.0*x^6 - 1.0*x^7 + 1.0*x^8 - 1.0*x^9 + 1.0*x^10)

23: Poly(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12 + x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + x^20 + x^21 + x^22)

24: Poly(1.0 - 1.0*x^4 + 1.0*x^8)

25: Poly(1.0 + 1.0*x^5 + 1.0*x^10 + 1.0*x^15 + 1.0*x^20)

26: Poly(1.0 - 1.0*x + 1.0*x^2 - 1.0*x^3 + 1.0*x^4 - 1.0*x^5 + 1.0*x^6 - 1.0*x^7 + 1.0*x^8 - 1.0*x^9 + 1.0*x^10 - 1.0*x^11 + 1.0*x^12)

27: Poly(1.0 + 1.0*x^9 + 1.0*x^18)

28: Poly(1.0 - 1.0*x^2 + 1.0*x^4 - 1.0*x^6 + 1.0*x^8 - 1.0*x^10 + 1.0*x^12)

29: Poly(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12 + x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + x^20 + x^21 + x^22 + x^23 + x^24 + x^25 + x^26 + x^27 + x^28)

30: Poly(1.0 + 1.0*x - 1.0*x^3 - 1.0*x^4 - 1.0*x^5 + 1.0*x^7 + 1.0*x^8)

The cyclotomic polynomial Φ(1) has a coefficient that is -1

The cyclotomic polynomial Φ(105) has a coefficient that is -2

The cyclotomic polynomial Φ(385) has a coefficient that is -3

The cyclotomic polynomial Φ(1365) has a coefficient that is -4

The cyclotomic polynomial Φ(1785) has a coefficient that is 5

The cyclotomic polynomial Φ(2805) has a coefficient that is -6

The cyclotomic polynomial Φ(3135) has a coefficient that is 7

The cyclotomic polynomial Φ(6545) has a coefficient that is -8

The cyclotomic polynomial Φ(6545) has a coefficient that is 9

The cyclotomic polynomial Φ(10465) has a coefficient that is 9