Cyclotomic polynomial: Difference between revisions
→{{header|jq}}: task2(10)
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(→{{header|jq}}: task2(10)) |
||
| (9 intermediate revisions by 4 users not shown) | |||
Line 2,749:
CP[6545] has coefficient with magnitude = 9
CP[10465] has coefficient with magnitude = 10
</pre>
===Alternative Version===
An alternative example using the algorithm from "Matters Computational" by Jorg Arndt, pages 704 - 705.
It completes the task in less than 2 seconds.
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CyclotomicPolynomials {
public static void main(String[] args) {
System.out.println("Task 1: Cyclotomic polynomials for n <= 30:");
for ( int cpIndex = 1; cpIndex <= 30; cpIndex++ ) {
System.out.println("CP[" + cpIndex + "] = " + toString(cyclotomicPolynomial(cpIndex)));
}
System.out.println();
System.out.println("Task 2: Smallest cyclotomic polynomial with n or -n as a coefficient:");
System.out.println("CP[1] has a coefficient with magnitude 1");
int cpIndex = 2;
for ( int coefficient = 2; coefficient <= 10; coefficient++ ) {
while ( BigInteger.valueOf(cpIndex).isProbablePrime(PRIME_CERTAINTY)
|| ! hasHeight(cyclotomicPolynomial(cpIndex), coefficient) ) {
cpIndex += 1;
}
System.out.println("CP[" + cpIndex + "] has a coefficient with magnitude " + coefficient);
}
}
// Return the Cyclotomic Polynomial of order 'cpIndex' as an array of coefficients,
// where, for example, the polynomial 3x^2 - 1 is represented by the array [3, 0, -1].
private static int[] cyclotomicPolynomial(int cpIndex) {
int[] polynomial = new int[] { 1, -1 };
if ( cpIndex == 1 ) {
return polynomial;
}
if ( BigInteger.valueOf(cpIndex).isProbablePrime(PRIME_CERTAINTY) ) {
int[] result = new int[cpIndex];
Arrays.fill(result, 1);
return result;
}
List<Integer> primes = distinctPrimeFactors(cpIndex);
int product = 1;
for ( int prime : primes ) {
int[] numerator = substituteExponent(polynomial, prime);
polynomial = exactDivision(numerator, polynomial);
product *= prime;
}
polynomial = substituteExponent(polynomial, cpIndex / product);
return polynomial;
}
// Return the Cyclotomic Polynomial obtained from 'polynomial' by replacing x with x^'exponent'.
private static int[] substituteExponent(int[] polynomial, int exponent) {
int[] result = new int[exponent * ( polynomial.length - 1 ) + 1];
for ( int i = polynomial.length - 1; i >= 0; i-- ) {
result[i * exponent] = polynomial[i];
}
return result;
}
// Return the Cyclotomic Polynomial equal to 'dividend' / 'divisor'. The division is always exact.
private static int[] exactDivision(int[] dividend, int[] divisor) {
int[] result = Arrays.copyOf(dividend, dividend.length);
for ( int i = 0; i < dividend.length - divisor.length + 1; i++ ) {
if ( result[i] != 0 ) {
for ( int j = 1; j < divisor.length; j ++ ) {
result[i + j] += -divisor[j] * result[i];
}
}
}
result = Arrays.copyOf(result, result.length - divisor.length + 1);
return result;
}
// Return whether 'polynomial' has a coefficient of equal magnitude to 'coefficient'.
private static boolean hasHeight(int[] polynomial, int coefficient) {
for ( int i = 0; i <= ( polynomial.length + 1 ) / 2; i++ ) {
if ( Math.abs(polynomial[i]) == coefficient ) {
return true;
}
}
return false;
}
// Return a string representation of 'polynomial'.
private static String toString(int[] polynomial) {
StringBuilder text = new StringBuilder();
for ( int i = 0; i < polynomial.length; i++ ) {
if ( polynomial[i] == 0 ) {
continue;
}
text.append(( polynomial[i] < 0 ) ? ( ( i == 0 ) ? "-" : " - " ) : ( ( i == 0 ) ? "" : " + " ));
final int exponent = polynomial.length - 1 - i;
if ( exponent > 0 && Math.abs(polynomial[i]) > 1 ) {
text.append(Math.abs(polynomial[i]));
}
text.append(( exponent > 1 ) ?
( "x^" + String.valueOf(exponent) ) : ( ( exponent == 1 ) ? "x" : Math.abs(polynomial[i]) ));
}
return text.toString();
}
// Return a list of the distinct prime factors of 'number'.
private static List<Integer> distinctPrimeFactors(int number) {
List<Integer> primeFactors = new ArrayList<Integer>();
for ( int divisor = 2; divisor * divisor <= number; divisor++ ) {
if ( number % divisor == 0 ) {
primeFactors.add(divisor);
}
while ( number % divisor == 0 ) {
number = number / divisor;
}
}
if ( number > 1 ) {
primeFactors.add(number);
}
return primeFactors;
}
private static final int PRIME_CERTAINTY = 15;
}
</syntaxhighlight>
<pre>
Task 1: Cyclotomic polynomials for n <= 30:
CP[1] = x - 1
CP[2] = x + 1
CP[3] = x^2 + x + 1
CP[4] = x^2 + 1
CP[5] = x^4 + x^3 + x^2 + x + 1
CP[6] = x^2 - x + 1
CP[7] = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
CP[8] = x^4 + 1
CP[9] = x^6 + x^3 + 1
CP[10] = x^4 - x^3 + x^2 - x + 1
CP[11] = x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
CP[12] = x^4 - x^2 + 1
CP[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
CP[14] = x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
CP[15] = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1
CP[16] = x^8 + 1
CP[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
CP[18] = x^6 - x^3 + 1
CP[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
CP[20] = x^8 - x^6 + x^4 - x^2 + 1
CP[21] = x^12 - x^11 + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1
CP[22] = x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
CP[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
CP[24] = x^8 - x^4 + 1
CP[25] = x^20 + x^15 + x^10 + x^5 + 1
CP[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
CP[27] = x^18 + x^9 + 1
CP[28] = x^12 - x^10 + x^8 - x^6 + x^4 - x^2 + 1
CP[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
CP[30] = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1
Task 2: Smallest cyclotomic polynomial with n or -n as a coefficient:
CP[1] has a coefficient with magnitude 1
CP[105] has a coefficient with magnitude 2
CP[385] has a coefficient with magnitude 3
CP[1365] has a coefficient with magnitude 4
CP[1785] has a coefficient with magnitude 5
CP[2805] has a coefficient with magnitude 6
CP[3135] has a coefficient with magnitude 7
CP[6545] has a coefficient with magnitude 8
CP[6545] has a coefficient with magnitude 9
CP[10465] has a coefficient with magnitude 10
</pre>
=={{header|jq}}==
'''Adapted from the [[#Wren|Wren]] implementation of the Arndt algorithm'''
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
'''Works with jaq, the Rust implementation of jq'''
In this entry, a polynomial of degree n is represented by a JSON
array of length n+1 beginning with the leading coefficient.
For the second task, besides exploiting the fact that
CP[1] has height 1, the following program only assumes that the
cyclotomic polynomials are palindromic, but avoids recomputing them.
<syntaxhighlight lang="jq">
### Generic utilities
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
# Return the maximum item in the stream assuming it is not empty:
def max(s): reduce s as $s (null; if . == null then $s elif $s > . then $s else . end);
# Truncated integer division (consistent with % operator).
# `round` is used for the sake of jaq.
def quo($x; $y): ($x - ($x%$y)) / $y | round;
### Primes
def is_prime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
else sqrt as $s
| 23
| until( . > $s or ($n % . == 0); . + 2)
| . > $s
end;
# Emit an array of the distinct prime factors of 'n' in order using a wheel
# with basis [2, 3, 5], e.g. 44 | distinctPrimeFactors #=> [2,11]
def distinctPrimeFactors:
def augment($x): if .[-1] == $x then . else . + [$x] end;
def out($i):
if (.n % $i) == 0
then .factors += [$i]
| until (.n % $i != 0; .n = ((.n/$i)|floor) )
else .
end;
if . < 2 then []
else [4, 2, 4, 2, 4, 6, 2, 6] as $inc
| { n: .,
factors: [] }
| out(2)
| out(3)
| out(5)
| .k = 7
| .i = 0
| until(.k * .k > .n;
if .n % .k == 0
then .k as $k | .factors |= augment($k)
| .n = ((.n/.k)|floor)
else .k += $inc[.i]
| .i = ((.i + 1) % 8)
end)
| if .n > 1 then .n as $n | .factors |= augment($n) else . end
| .factors
end;
### Polynomials
def canonical:
if length == 0 then .
elif .[-1] == 0 then .[:-1]|canonical
else .
end;
# For pretty-printing the input array as the polynomial it represents
# e.g. [1,-1] => x-1
def pp:
def digits: tostring | explode[] | [.] | implode | tonumber;
def superscript:
if . <= 1 then ""
else ["\u2070", "\u00b9", "\u00b2", "\u00b3", "\u2074", "\u2075", "\u2076", "\u2077", "\u2078", "\u2079"] as $ss
| reduce digits as $d (""; . + $ss[$d] )
end;
if length == 1 then .[0] | tostring
else reverse as $p
| reduce range(length-1; -1; -1) as $i ([];
if $p[$i] != 0
then (if $i > 0 then "x" else "" end) as $x
| ( if $i > 0 and ($p[$i]|length) == 1
then (if $p[$i] == 1 then "" else "-" end)
else ($p[$i]|tostring)
end ) as $c
| . + ["\($c)\($x)\($i|superscript)"]
else . end )
| join("+")
| gsub("\\+-"; "-")
end ;
def polynomialDivide($divisor):
. as $in
| ($divisor|canonical) as $divisor
| { curr: canonical}
| .base = ((.curr|length) - ($divisor|length))
| until( .base < 0;
(.curr[-1] / $divisor[-1]) as $res
| .result += [$res]
| .curr |= .[:-1]
| reduce range (0;$divisor|length-1) as $i (.;
.curr[.base + $i] += (- $res * $divisor[$i]) )
| .base += -1 )
| (.result | reverse) as $quot
| (.curr | canonical) as $rem
| [$quot, $rem];
# Call `round` for the sake of jaq
def exactDivision($numerator; $denominator):
($numerator | polynomialDivide($denominator))
| .[0]
| map(round);
def init($n; $value): [range(0;$n)|$value];
### Cyclotomic Polynomials
# The Cyclotomic Polynomial obtained from $polynomial
# by replacing x with x^$exponent
def substituteExponent($polynomial; $exponent):
init( ($polynomial|length - 1) * $exponent + 1; 0)
| reduce range(0; $polynomial|length) as $i (.; .[$i*$exponent] = $polynomial[$i]);
# Return the Cyclotomic Polynomial of order 'cpIndex' as a JSON array of coefficients,
# where, for example, the polynomial 3x^2 - 1 is represented by [3, 0, -1].
def cycloPoly($cpIndex):
{ polynomial: [1, -1] }
| if $cpIndex == 1 then .polynomial
elif ($cpIndex|is_prime) then [range(0; $cpIndex) | 1 ]
else .product = 1
| reduce ($cpIndex | distinctPrimeFactors[]) as $prime (.;
substituteExponent(.polynomial; $prime) as $numerator
| .polynomial = exactDivision($numerator; .polynomial)
| .product *= $prime )
| substituteExponent(.polynomial; quo($cpIndex; .product) )
end;
# The Cyclotomic Polynomial equal to $dividend / $divisor
def exactDivision($dividend; $divisor):
reduce range(0; 1 + ($dividend|length) - ($divisor|length)) as $i ($dividend;
if .[$i] != 0
then reduce range(1; $divisor|length) as $j (.;
.[$i+$j] = .[$i+$j] - $divisor[$j] * .[$i] )
else .
end)
| .[0: 1 + length - ($divisor|length)];
### The tasks
def task1($n):
"Task 1: Cyclotomic polynomials for n <= \($n):",
( range(1;$n+1) | "CP[\(lpad(2))]: \(cycloPoly(.)|pp)" );
# For range(1;$n+1) as $c, report the first cpIndex which has a coefficient
# equal in magnitude to $c, possibly reporting others as well.
def task2($n):
def height: max(.[]|length); # i.e. abs
# update .summary and .todo
def register($cpIndex):
cycloPoly($cpIndex) as $poly
| if ($poly|height) < .todo[0] then .
else # it is a palindrome so we can halve the checks
reduce ($poly | .[0: quo(length + 1; 2)][]|length|select(.>1)) as $c (.;
if .summary[$c|tostring] then .
else .summary[$c|tostring] = $cpIndex
| .todo -= [$c]
| debug
end)
end;
{cpIndex:1, summary: {"1": 1}, todo: [range(2; $n + 1)]}
| until(.todo|length == 0;
if .cpIndex|is_prime then . else register(.cpIndex) end
| .cpIndex += 1)
| .summary
| (keys | sort_by(tonumber)[]) as $key
| "CP[\(.[$key]|lpad(5))] has a coefficient with magnitude \($key)"
;
task1(30),
"",
task2(10)
</syntaxhighlight>
{{output}}
<pre>
Task 1: Cyclotomic polynomials for n <= 30:
CP[ 1]: x-1
CP[ 2]: x+1
CP[ 3]: x²+x+1
CP[ 4]: x²+1
CP[ 5]: x⁴+x³+x²+x+1
CP[ 6]: x²-x+1
CP[ 7]: x⁶+x⁵+x⁴+x³+x²+x+1
CP[ 8]: x⁴+1
CP[ 9]: x⁶+x³+1
CP[10]: x⁴-x³+x²-x+1
CP[11]: x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
CP[12]: x⁴-x²+1
CP[13]: x¹²+x¹¹+x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
CP[14]: x⁶-x⁵+x⁴-x³+x²-x+1
CP[15]: x⁸-x⁷+x⁵-x⁴+x³-x+1
CP[16]: x⁸+1
CP[17]: x¹⁶+x¹⁵+x¹⁴+x¹³+x¹²+x¹¹+x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
CP[18]: x⁶-x³+1
CP[19]: x¹⁸+x¹⁷+x¹⁶+x¹⁵+x¹⁴+x¹³+x¹²+x¹¹+x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
CP[20]: x⁸-x⁶+x⁴-x²+1
CP[21]: x¹²-x¹¹+x⁹-x⁸+x⁶-x⁴+x³-x+1
CP[22]: x¹⁰-x⁹+x⁸-x⁷+x⁶-x⁵+x⁴-x³+x²-x+1
CP[23]: x²²+x²¹+x²⁰+x¹⁹+x¹⁸+x¹⁷+x¹⁶+x¹⁵+x¹⁴+x¹³+x¹²+x¹¹+x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
CP[24]: x⁸-x⁴+1
CP[25]: x²⁰+x¹⁵+x¹⁰+x⁵+1
CP[26]: x¹²-x¹¹+x¹⁰-x⁹+x⁸-x⁷+x⁶-x⁵+x⁴-x³+x²-x+1
CP[27]: x¹⁸+x⁹+1
CP[28]: x¹²-x¹⁰+x⁸-x⁶+x⁴-x²+1
CP[29]: x²⁸+x²⁷+x²⁶+x²⁵+x²⁴+x²³+x²²+x²¹+x²⁰+x¹⁹+x¹⁸+x¹⁷+x¹⁶+x¹⁵+x¹⁴+x¹³+x¹²+x¹¹+x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1
CP[30]: x⁸+x⁷-x⁵-x⁴-x³+x+1
Task 2: Smallest cyclotomic polynomial with n or -n as a coefficient:
CP[ 1] has a coefficient with magnitude 1
CP[ 105] has a coefficient with magnitude 2
CP[ 385] has a coefficient with magnitude 3
CP[ 1365] has a coefficient with magnitude 4
CP[ 1785] has a coefficient with magnitude 5
CP[ 2805] has a coefficient with magnitude 6
CP[ 3135] has a coefficient with magnitude 7
CP[ 6545] has a coefficient with magnitude 8
CP[ 6545] has a coefficient with magnitude 9
CP[10465] has a coefficient with magnitude 10
CP[10465] has a coefficient with magnitude 11
CP[10465] has a coefficient with magnitude 12
CP[10465] has a coefficient with magnitude 13
CP[10465] has a coefficient with magnitude 14
</pre>
Line 4,371 ⟶ 4,804:
=={{header|Sidef}}==
Built-in:
<syntaxhighlight lang="ruby">
for k in (1..30) {
}
say "\nSmallest cyclotomic polynomial with n or -n as a coefficient:"
for n in (1..10) { #
var k = (1..Inf -> first {|k|
})
say "Φ(#{k}) has coefficient with magnitude #{n}"
}</syntaxhighlight>
Line 4,458 ⟶ 4,862:
^C
</pre>
=={{header|Visual Basic .NET}}==
{{trans|C++}}
Line 4,989 ⟶ 5,394:
=={{header|Wren}}==
===Version 1===
{{trans|Go}}
{{libheader|Wren-
{{libheader|Wren-sort}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
Second part is very slow. Limited to first 7 to finish in a reasonable time - 5 minutes on my machine.
<syntaxhighlight lang="
import "./sort" for Sort
import "./math" for Int, Nums
import "./fmt" for Fmt
var algo = 2
Line 5,378 ⟶ 5,784:
CP[2805] has coefficient with magnitude = 6
CP[3135] has coefficient with magnitude = 7
</pre>
===Version 2===
{{trans|Java}}
A translation of the alternative version which completes the second part in about 33 seconds.
<syntaxhighlight lang="wren">import "./math" for Int
import "./fmt" for Fmt
class CP {
// Return the Cyclotomic Polynomial of order 'cpIndex' as a list of coefficients,
// where, for example, the polynomial 3x^2 - 1 is represented by the list [3, 0, -1].
static cycloPoly(cpIndex) {
var polynomial = [1, -1]
if (cpIndex == 1) return polynomial
if (Int.isPrime(cpIndex)) return List.filled(cpIndex, 1)
var primes = Int.distinctPrimeFactors(cpIndex)
var product = 1
for (prime in primes) {
var numerator = substituteExponent(polynomial, prime)
polynomial = exactDivision(numerator, polynomial)
product = product * prime
}
return substituteExponent(polynomial, Int.quo(cpIndex, product))
}
// Return the Cyclotomic Polynomial obtained from 'polynomial'
// by replacing x with x^'exponent'.
static substituteExponent(polynomial, exponent) {
var result = List.filled(exponent * (polynomial.count - 1) + 1, 0)
for (i in polynomial.count-1..0) result[i*exponent] = polynomial[i]
return result
}
// Return the Cyclotomic Polynomial equal to 'dividend' / 'divisor'.
// The division is always exact.
static exactDivision(dividend, divisor) {
var result = dividend.toList
for (i in 0..dividend.count - divisor.count) {
if (result[i] != 0) {
for (j in 1...divisor.count) {
result[i+j] = result[i+j] - divisor[j] * result[i]
}
}
}
return result[0..result.count - divisor.count]
}
// Return whether 'polynomial' has a coefficient of equal magnitude
// to 'coefficient'.
static hasHeight(polynomial, coefficient) {
for (i in 0..Int.quo(polynomial.count + 1, 2)) {
if (polynomial[i].abs == coefficient) return true
}
return false
}
}
System.print("Task 1: Cyclotomic polynomials for n <= 30:")
for (cpIndex in 1..30) {
Fmt.write("CP[$2d] = ", cpIndex)
Fmt.pprint("$d", CP.cycloPoly(cpIndex), "", "x")
}
System.print("\nTask 2: Smallest cyclotomic polynomial with n or -n as a coefficient:")
System.print("CP[ 1] has a coefficient with magnitude 1")
var cpIndex = 2
for (coeff in 2..10) {
while (Int.isPrime(cpIndex) || !CP.hasHeight(CP.cycloPoly(cpIndex), coeff)) {
cpIndex = cpIndex + 1
}
Fmt.print("CP[$5d] has a coefficient with magnitude $d", cpIndex, coeff)
}</syntaxhighlight>
{{out}}
<pre>
Task 1: Cyclotomic polynomials for n <= 30:
CP[ 1] = x - 1
CP[ 2] = x + 1
CP[ 3] = x² + x + 1
CP[ 4] = x² + 1
CP[ 5] = x⁴ + x³ + x² + x + 1
CP[ 6] = x² - x + 1
CP[ 7] = x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[ 8] = x⁴ + 1
CP[ 9] = x⁶ + x³ + 1
CP[10] = x⁴ - x³ + x² - x + 1
CP[11] = x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[12] = x⁴ - x² + 1
CP[13] = x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[14] = x⁶ - x⁵ + x⁴ - x³ + x² - x + 1
CP[15] = x⁸ - x⁷ + x⁵ - x⁴ + x³ - x + 1
CP[16] = x⁸ + 1
CP[17] = x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[18] = x⁶ - x³ + 1
CP[19] = x¹⁸ + x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[20] = x⁸ - x⁶ + x⁴ - x² + 1
CP[21] = x¹² - x¹¹ + x⁹ - x⁸ + x⁶ - x⁴ + x³ - x + 1
CP[22] = x¹⁰ - x⁹ + x⁸ - x⁷ + x⁶ - x⁵ + x⁴ - x³ + x² - x + 1
CP[23] = x²² + x²¹ + x²⁰ + x¹⁹ + x¹⁸ + x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[24] = x⁸ - x⁴ + 1
CP[25] = x²⁰ + x¹⁵ + x¹⁰ + x⁵ + 1
CP[26] = x¹² - x¹¹ + x¹⁰ - x⁹ + x⁸ - x⁷ + x⁶ - x⁵ + x⁴ - x³ + x² - x + 1
CP[27] = x¹⁸ + x⁹ + 1
CP[28] = x¹² - x¹⁰ + x⁸ - x⁶ + x⁴ - x² + 1
CP[29] = x²⁸ + x²⁷ + x²⁶ + x²⁵ + x²⁴ + x²³ + x²² + x²¹ + x²⁰ + x¹⁹ + x¹⁸ + x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
CP[30] = x⁸ + x⁷ - x⁵ - x⁴ - x³ + x + 1
Task 2: Smallest cyclotomic polynomial with n or -n as a coefficient:
CP[ 1] has a coefficient with magnitude 1
CP[ 105] has a coefficient with magnitude 2
CP[ 385] has a coefficient with magnitude 3
CP[ 1365] has a coefficient with magnitude 4
CP[ 1785] has a coefficient with magnitude 5
CP[ 2805] has a coefficient with magnitude 6
CP[ 3135] has a coefficient with magnitude 7
CP[ 6545] has a coefficient with magnitude 8
CP[ 6545] has a coefficient with magnitude 9
CP[10465] has a coefficient with magnitude 10
</pre>
| |||