Фон (пропустите к определениям)

Эйлер доказал красивую теорему о комплексных числах: e ^ix = cos (x) + i sin (x).

Это позволяет легко доказать теорему де Мойвра:

(e ^ix ) ⁿ = e ^{i (nx)}

(cos (x) + i sin (x)) ⁿ = cos (nx) + i sin (nx)

Мы можем построить комплексные числа, используя двумерную евклидову плоскость, где горизонтальная ось представляет действительную часть, а вертикальная ось представляет мнимую часть. Таким образом, (3,4) будет соответствовать комплексному числу 3 + 4i.

Если вы знакомы с полярными координатами, (3,4) будет (5, arctan (4/3)) в полярных координатах. Первое число r - это расстояние точки от начала координат; второе число θ - это угол, измеренный от положительной оси x к точке против часовой стрелки. В результате 3 = r cosθ и 4 = r sinθ. Поэтому мы можем записать 3 + 4i как r cosθ + ri sinθ = r (cosθ + i sinθ) = re ^iθ .

Решим комплексное уравнение z ⁿ = 1, где n - натуральное число.

Пусть z = re ^iθ . Тогда z ⁿ = r ⁿ e ^inθ . Расстояние z ⁿ от начала координат равно r ⁿ , а угол равен nθ. Однако мы знаем, что расстояние 1 от начала координат равно 1, а угол равен 0. Следовательно, r ⁿ = 1 и nθ = 0. Однако, если вы повернете на 2π больше, вы все равно окажетесь в той же точке, потому что 2π - это просто полный круг. Следовательно, r = 1 и nθ = 2kπ, что дает нам z = e ^{2ikπ / n} .

Мы повторяем наше открытие: решения для z ⁿ = 1 являются z = e ^{2ikπ / n} .

Многочлен можно выразить через его корни. Например, корни x ² -3x + 2 равны 1 и 2, поэтому x ² -3x + 2 = (x-1) (x-2). Точно так же из нашего открытия выше:

Однако этот продукт, безусловно, содержал корни других русских. Например, возьмите n = 8. Корни z ⁴ = 1 также будут включены в корни z ⁸ = 1, поскольку z ⁴ = 1 подразумевает z ⁸ = (z ⁴ ) ² = 1 ² = 1. Возьмем n = 6 в качестве примера. Если z ² = 1, то мы также имели бы z ⁶ = 1. Аналогично, если z ³ = 1, то z ⁶ = 1.

Если мы хотим извлечь корни, уникальные для z ⁿ = 1, нам нужно, чтобы k и n не разделяли общий делитель, кроме 1. Или же, если они разделяют общий делитель d, где d> 1, то z будет (k / г) -ый корень из z ^{n / d} = 1. Используя вышеописанную технику, чтобы написать многочлен в терминах его корней, мы получим многочлен:

Обратите внимание, что этот многочлен выполняется путем удаления корней из z ^{n / d} = 1, где d является делителем n. Мы утверждаем, что полином выше имеет целочисленные коэффициенты. Рассмотрим LCM многочленов в виде z ^{n / d} -1, где d> 1 и d делит n. Корни LCM - это именно те корни, которые мы хотим удалить. Поскольку каждый компонент имеет целочисленные коэффициенты, LCM также имеет целочисленные коэффициенты. Поскольку LCM делит z ⁿ -1, частное должно быть многочленом с целочисленным коэффициентом, а частное является многочленом выше.

Корни z ⁿ = 1 имеют радиус 1, поэтому они образуют круг. Полином представляет точки окружности, уникальные для n, поэтому в некотором смысле полиномы образуют разбиение окружности. Следовательно, приведенный выше многочлен является n-м циклическим многочленом. (Цикло- = круг; том- = разрезать)

Определение 1

Обозначенный n-й циклотомический многочлен является единственным многочленом с целочисленными коэффициентами, которые делят x ⁿ -1, но не x ^k -1 при k <n.

Определение 2

Циклотомные полиномы - это набор полиномов, по одному на каждое положительное целое число, такой что:

где к | n означает, что k делит n.

Определение 3

N-й циклотомический полином - это полином x ⁿ -1, деленный на LCM полиномов в виде x ^k -1, где k делит n и k <n.

Примеры

1. Φ ₁ (x) = x - 1
2. Ф ₂ (х) = х + 1
3. Ф ₃ (х) = х ² + х + 1
4. Φ ₃₀ (x) = x ⁸ + x ⁷ - x ⁵ - x ⁴ - x ³ + x + 1
5. Φ ₁₀₅ (x) = x ⁴⁸ + x ⁴⁷ + x ⁴⁶ - x ⁴³ - x ⁴² - 2x ⁴¹ - x ⁴⁰ - x ³⁹ + x ³⁶ + x ³⁵ + x ³⁴ + x ³³ + x ³² + x ³¹ - x ²⁸ - x ²⁶ - x ²⁴ - x ²² - x ²⁰ + x ¹⁷ + x ¹⁶ + x ¹⁵ + x ¹⁴ + x ¹³ + x ¹² - x⁹ - х ⁸ - 2х ⁷ - х ⁶ - х ⁵ + х ² + х + 1

задача

Если задано положительное целое число n, верните-й nциклотомический полином, как определено выше, в приемлемом формате (например, допустим список коэффициентов).

правила

Вы можете возвращать числа с плавающей запятой / комплексные числа, пока они округляются до правильного значения.

счет

Это код-гольф . Кратчайший ответ в байтах побеждает.

Ссылки

• Wolfram MathWorld
• Википедия

Haskell , 120 байт

import Data.Complex
p%a=zipWith(\x y->x-a*y)(p++[0])$0:p
f n=foldl(%)[1][cis(2*pi/fromInteger n)^^k|k<-[1..n],gcd n k<2]

Попробуйте онлайн!

Предоставляет список сложных чисел с плавающей точкой, например, 1.0000000000000078 :+ 3.314015728506092e-14из-за неточности. Прямой метод умножения для восстановления полинома из его корней.

Это fromIntegerбольшая уступка системе типов Хаскелла. Должен быть лучший способ. Предложения приветствуются. Работа с корнями единства символически может также сработать.

Haskell , 127 байт

(h:t)%q|all(==0)t=[]|1>0=h:zipWith(\x y->x-h*y)t q%q
f n=foldl(%)(1:(0<$[2..n])++[-1])[tail$f k++[0,0..]|k<-[1..n-1],mod n k<1]

Попробуйте онлайн!

Нет импорта.

Использует формулу

Вычисляет Φ_n (x) путем деления LHS на каждое из других слагаемых в RHS.

Оператор %выполняет деление на полиномы, полагаясь на то, что остаток равен нулю. Делитель считается моническим и задается без начального 1, а также с бесконечными конечными нулями, чтобы избежать усечения при выполненииzipWith .

Mathematica, 43 41 байт

Factor[x^#-1]/Times@@#0/@Most@Divisors@#&

Конечно, мы всегда можем использовать встроенную функцию, но если нет, это делит x ⁿ -1 на Φ _k ( x ) (вычисляется рекурсивно) для каждого правильного делителя k числа n .

Мы используем, Factorчтобы получить полином в конце. Я думаю, что причина этой работы заключается в том, что x^#-1факторы во все циклотомические полиномы делителей делятся n , а затем мы делим те, которые нам не нужны.

-2 байта благодаря Jenny_mathy, переписав его так, чтобы он относился Factorтолько к числителю.

MATL , 32 31 27 25 байтов

Z\"@:@/]XHxvHX~18L*Ze1$Yn

Вывод может быть нецелым из-за неточностей с плавающей точкой (что разрешено). Нижний колонтитул делает округление для ясности.

Попробуйте онлайн!

Haskell , 250 236 233 218 216 байт

Это подробная версия, (@xnor может сделать это почти вдвое меньше ), но она гарантированно для любогоn условии, что у вас достаточно памяти, но она не использует встроенную функцию для генерации n-го циклотомического полинома. Входные данные представляют собой целые числа произвольного размера, а выходные данные представляют собой полиномиальный тип с (точными) рациональными коэффициентами.

Грубая идея здесь состоит в том, чтобы вычислить многочлены рекурсивно. Для n=1илиn премьер это тривиально. Для всех остальных чисел этот подход в основном использует формулу из определения 2

решено для . Спасибо @ H.PWiz за кучу байтов!

import Math.Polynomial
import Data.Ratio
import NumberTheory
p=powPoly x
q=poly LE
c n|n<2=q[-1,1%1]|isPrime n=sumPolys$p<$>[0..n-1]|1>0=fst$quotRemPoly(addPoly(p n)$q[-1])$foldl1 multPoly[c d|d<-[1..n-1],n`mod`d<1]

Для n=105этого получим следующий полином (я убрал все%1 знаменатели):

[1,1,1,0,0,-1,-1,-2,-1,-1,0,0,1,1,1,1,1,1,0,0,-1,0,-1,0,-1,0,-1,0,-1,0,0,1,1,1,1,1,1,0,0,-1,-1,-2,-1,-1,0,0,1,1,1]

Полином для n=15015можно найти здесь (самый большой коэффициент 23).

Попробуйте онлайн!

Желе , 23 байта

R÷
ÆḌÇ€FQœ-@Ç×ı2×ØPÆeÆṛ

Попробуйте онлайн!

Выходы в виде списка коэффициентов.

Имеет плавающую точку и сложные неточности. Нижний колонтитул делает округление, чтобы сделать вывод более красивым.

J , 36 байт

1+//.@(*/)/@(,.~-)_1^2*%*i.#~1=i.+.]

Попробуйте онлайн!

Использует формулу

Есть некоторые неточности с плавающей точкой, но это разрешено.

Mathematica, 81 байт

Round@CoefficientList[Times@@(x-E^(2Pi*I#/k)&/@Select[Range[k=#],#~GCD~k<2&]),x]&

R , 176 171 139 112 байт

function(n){for(r in exp(2i*pi*(x=1:n)[(g=function(x,y)ifelse(o<-x%%y,g(y,o),y))(x,n)<2]/n))T=c(0,T)-r*c(T,0)
T}

Попробуйте онлайн!

Значительно более простая версия; использует forцикл, а не Reduce.

Пари / ГП , 8 байт

Встроенный.

polcyclo

Попробуйте онлайн!

Pari / GP , 39 байт, без встроенного

f(n)=p=x^n-1;fordiv(n,d,d<n&&p/=f(d));p

Используя формулу:

$\Phi_n(x)=\dfrac{x^{n}-1}{\prod\limits_{\stackrel{d|n}{{}_{d<n}}}\Phi_{d}(x)}$,

Попробуйте онлайн!

CJam ( 52 51 байт)

{M{:K,:!W+K,0-{K\%!},{j($,\:Q,-[{(\1$Qf*.-}*;]}/}j}

Демо онлайн . Это анонимный блок (функция), который принимает целое число в стеке и оставляет массив коэффициентов с большим порядком байтов в стеке.

рассечение

{                    e# Define a block
  M{                 e#   Memoised recursion with no base cases.
    :K,:!W+          e#     Store argument in K and build (x^K - 1)
    K,0-{K\%!},      e#     Find proper divisors of K
    {                e#     Foreach proper divisor D...
      j              e#       Recursive call to get Dth cyclotomic poly
      ($,\:Q,-       e#       The cleverest bit. We know that it is monic, and the
                     e#       poly division is simpler without that leading 1, so
                     e#       pop it off and use it for a stack-based lookup in
                     e#       calculating the number of terms in the quotient.
                     e#       Ungolfed this was (;:Q1$,\,-
                     e#       Store the headless divisor in Q.
      [              e#       Gather terms into an array...
        {            e#         Repeat the calculated number of times...
          (\         e#           Pop leading term, which goes into the quotient.
          1$Qf*.-    e#           Multiply Q by that term and subtract from tail.
        }*;          e#         Discard the array of Q,( zeroes. 
      ]
    }/
  }j
}

JavaScript (ES6), 337 333 284 ... 252 250 245 242 байта

(v,z=[e=[1,u=0]],g=(x,y)=>y?g(y,x%y):x,h=Math,m=(l,x,p=h.cos(l),q=h.sin(l),i=0)=>x.map(()=>[(i&&(n=x[i-1])[0])-(w=x[i])[0]*p+w[1]*q,(i++&&n[1])-w[1]*p-w[0]*q]))=>{for(;++u<v;z=g(v,u)-1?z:[...m(h.PI*2*u/v,z),e]);return z.map(r=>h.round(r[0]))}

Объяснение (выбрано):

z=[e=[1,u=0]]

Инициализировать z = (1 + 0i) * x ^ 0

g=(x,y)=>y?g(y,x%y):x

Расчет ГКД.

h=Math

Поскольку мне нужно довольно часто использовать математические функции, я использовал здесь другую переменную.

m=(l,x,p=h.cos(l),q=h.sin(l),i=-1)=>blah blah blah

Полиномиальное умножение.

for(;++u<v;z=g(v,u)-1?z:[...m(h.PI*2*u/v,z),e]);

Используемая формула

return z.map(r=>h.round(r[0]))

Сжать вывод обратно в целочисленный массив.

Выходы:

Массив целых чисел, с элементом в позиции i, представляющим коэффициент x ^ i.

Одна из проблем, с которой сталкивается JS, состоит в том, что, поскольку JS не предоставляет собственную библиотеку для вычислений по полиномам и комплексным числам, их необходимо реализовывать в виде массива.

console.log (phi (105)) дает

Array(49)
 0:  1    1:  1    2:  1    3: -0    4: -0    5: -1    6: -1 
 7: -2    8: -1    9: -1   10:  0   11: -0   12:  1   13:  1 
14:  1   15:  1   16:  1   17:  1   18:  0   19: -0   20: -1 
21:  0   22: -1   23: -0   24: -1   25:  0   26: -1   27: -0 
28: -1   29:  0   30:  0   31:  1   32:  1   33:  1   34:  1 
35:  1   36:  1   37: -0   38: -0   39: -1   40: -1   41: -2 
42: -1   43: -1   44: -0   45: -0   46:  1   47:  1   48:  1 
length: 49
__proto__: Array(0)

337> 333 (-4): изменен код для проверки неопределенного значения

333> 284 (-49): изменена функция умножения полиномов, поскольку ее можно упростить

284> 277 (-7): удален некоторый избыточный код

277> 265 (-12): используйте 2 переменные вместо 2-элементного массива, чтобы уменьшить использование байтов в массиве

265> 264 (-1): используйте Array.push () вместо Array.concat () для уменьшения 4 байтов, но добавьте 3 для фигурных скобок цикла и переменную z

264> 263 (-1): далее игра в гольф по последней поправке

263> 262 (-1): играли в петлю

262> 260 (-2): игра в гольф

260> 258 (-2): далее объединили декларации

258> 252 (-6): игра в гольф при повторном использовании ссылок на массивы

252> 250 (-2): заменить некоторые унарные операторы как бинарные операторы

250> 245 (-5): переместить инкремент в Array.map () к последней ссылке на счетчик, чтобы удалить байты

245> 242 (-3): используйте расширенный синтаксис вместо Array.push ()