123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 |
- #!/usr/bin/ruby
- # Expansion of cyclotomic polynomials.
- # See also:
- # https://rosettacode.org/wiki/Cyclotomic_Polynomial
- # https://en.wikipedia.org/wiki/Cyclotomic_polynomial
- # https://metacpan.org/pod/Math::Polynomial
- func cyclotomic(n) is cached {
- var x = Poly(n, 1)-1
- return x if (n == 1)
- var y = n.divisors.grep { _ < n }.prod {|d| __FUNC__(d) }
- x / y
- }
- say "First 30 cyclotomic polynomials:"
- for k in (1..30) {
- say ("Φ(#{k}) = ", cyclotomic(k))
- }
- __END__
- First 30 cyclotomic polynomials:
- Φ(1) = x - 1
- Φ(2) = x + 1
- Φ(3) = x^2 + x + 1
- Φ(4) = x^2 + 1
- Φ(5) = x^4 + x^3 + x^2 + x + 1
- Φ(6) = x^2 - x + 1
- Φ(7) = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
- Φ(8) = x^4 + 1
- Φ(9) = x^6 + x^3 + 1
- Φ(10) = x^4 - x^3 + x^2 - x + 1
- Φ(11) = x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
- Φ(12) = x^4 - x^2 + 1
- Φ(13) = x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
- Φ(14) = x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
- Φ(15) = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1
- Φ(16) = x^8 + 1
- Φ(17) = x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
- Φ(18) = x^6 - x^3 + 1
- Φ(19) = x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
- Φ(20) = x^8 - x^6 + x^4 - x^2 + 1
- Φ(21) = x^12 - x^11 + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1
- Φ(22) = x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
- Φ(23) = x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
- Φ(24) = x^8 - x^4 + 1
- Φ(25) = x^20 + x^15 + x^10 + x^5 + 1
- Φ(26) = x^12 - x^11 + x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
- Φ(27) = x^18 + x^9 + 1
- Φ(28) = x^12 - x^10 + x^8 - x^6 + x^4 - x^2 + 1
- Φ(29) = x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
- Φ(30) = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1
|