Cyclotomic polynomial: Difference between revisions

=={{header|C++}}==

{{trans|Java}}

#include <iostream>

#include <initializer_list>

 

return 0;

{{out}}

<pre>Task 1: cyclotomic polynomials for n <= 30:

{{trans|Java}}

{{works with|C sharp|8}}

using System.Collections;

using System.Collections.Generic;

};

}

{{out}}

<pre>

=={{header|D}}==

{{trans|Kotlin}}

import std.exception;

import std.format;

}

}

{{out}}

<pre>Task 1: cyclotomic polynomials for n <= 30:

=={{header|Fermat}}==

This isn't terribly efficient if you have to calculate many cyclotomics- store them in an array rather than using recursion instead if you need to do that- but it showcases Fermat's strength at polynomial expressions.

&(J=x); {adjoin x as the variable in the polynomials}

 

od;

!!(m,' : ',i);

 

=={{header|Go}}==

{{trans|Java}}

 

import (

}

}

 

{{out}}

Uses synthetic polynomial division and simple memoization.

 

import Data.Numbers.Primes (primeFactors)

 

-- general case

(p, m):ps -> let cm = cyclotomics !! (n `div` (p ^ m))

 

Simple examples

The task solution

 

showPoly p = foldl1 (\r -> (r ++) . term) $

dropWhile null $

 

skipBy n [] = []

 

Result

=={{header|J}}==

 

 

 

cyclotomic=: {{

'x y'=. x,:y

while. j=. j-1 do.

else.

q=. q, r=. x %&{. y

end.

end.q

 

Task examples:

 

c=. ":each j=.cyclotomic y

raw=. rplc&'_-' ;:inv}.,'+';"0|.(*|j)#c('(',[,],')'"_)each '*x^',&":L:0 <"0 i.#c

8 6545

9 6545

 

=={{header|Java}}==

import java.util.ArrayList;

import java.util.Collections;

 

}

{{out}}

<pre>

CP[6545] has coefficient with magnitude = 9

CP[10465] has coefficient with magnitude = 10

</pre>

 

=={{header|Julia}}==

# memoize cache for recursive calls

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

end

<pre>

First 30 cyclotomic polynomials:

=={{header|Kotlin}}==

{{trans|Java}}

import kotlin.math.abs

import kotlin.math.pow

} else coefficient.toString() + "x^" + exponent

}

{{out}}

<pre>Task 1: cyclotomic polynomials for n <= 30:

 

=={{header|Maple}}==

for n to 30 do lprint(Phi(n,x)) od:

 

[seq(ListTools:-SelectFirst(s->member(n,s),PhiSet,output=indices),n=1..20)];

#[1, 105, 385, 1365, 1785, 2805, 3135, 6545, 6545, 10465, 10465,

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

i = 1;

n = 10;

];

i++;

{{out}}

<pre>-1+x

We use Java algorithm with ideas from C#, D, Go and Kotlin. We have kept only algorithm number 2 as other algorithms are much less efficient. We have also done some Nim specific improvements in order to get better performances.

 

 

type

echo &"Φ{'(' & $n & ')':7} has coefficient with magnitude = {i}"

dec n

 

{{out}}

=={{header|PARI/GP}}==

Cyclotomic polynomials are a built-in function.

for(n=1,30,print(n," : ",polcyclo(n)))

 

 

for(d=1,10,i=1; while(contains_coeff(i,d)==0,i=i+1);print(d," : ",i))

 

{{out}}<pre>

=={{header|Perl}}==

Conveniently, the module <code>Math::Polynomial::Cyclotomic</code> exists to do all the work. An <code>exponent too large</code> error prevents reaching the 10th step of the 2nd part of the task.

use List::Util qw(first);

use Math::Polynomial::Cyclotomic qw(cyclo_poly_iterate);

$n++;

}

{{out}}

<pre>First 30 cyclotomic polynomials:

{{trans|Julia}}

Uses several routines from [[Polynomial_long_division#Phix]], tweaked slightly to check remainder is zero and trim the quotient.

<span style="color: #000080;font-style:italic;">-- demo\rosetta\Cyclotomic_Polynomial.exw</span>

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>

{{out}}

If you disable the cheating, and if in a particularly self harming mood replace it with n+=1, you will get exactly the same output, eventually.<br>

 

=={{header|Python}}==

from collections import deque

 

while want in c or -want in c:

print(f'C[{want}]: {n}')

{{out}}

Only showing first 10 polynomials to avoid clutter.

 

Uses the same library as Perl, so comes with the same caveats.

 

say 'First 30 cyclotomic polynomials:';

sub super ($str) {

$str.subst( / '^' (\d+) /, { $0.trans([<0123456789>.comb] => [<⁰¹²³⁴⁵⁶⁷⁸⁹>.comb]) }, :g)

<pre>First 30 cyclotomic polynomials:

Φ(1) = (x - 1)

 

=={{header|Sidef}}==

for k in (1..30) {

}

 

say "\nSmallest cyclotomic polynomial with n or -n as a coefficient:"

var k = (1..Inf -> first {|k|

})

say "Φ(#{k}) has coefficient with magnitude #{n}"

 

{{out}}

^C

</pre>

=={{header|Visual Basic .NET}}==

{{trans|C++}}

 

Module Module1

End Sub

 

{{out}}

<pre>Task 1: cyclotomic polynomials for n <= 30:

 

=={{header|Wren}}==

{{trans|Go}}

{{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.

 

var algo = 2

}

}

 

{{out}}

CP[2805] has coefficient with magnitude = 6

CP[3135] has coefficient with magnitude = 7

</pre>