Rozkład wielomianów

12

Biorąc pod uwagę integralny wielomian stopnia ściśle większy niż jeden, całkowicie rozłóż go na skład integralnych wielomianów stopnia ściśle więcej niż jeden.

Detale

  • Integralną wielomian jest wielomianem tylko z liczb całkowitych jak współczynników.
  • Biorąc pod uwagę dwa wielomiany pi kompozycja jest definiowana przez .q(p∘q)(x):=p(q(x))
  • Rozkładu integralnego wielomianu pjest skończoną sekwencja uporządkowane integralnych wielomianów q1,q2,...,qn, gdy deg qi > 1dla wszystkich 1 ≤ i ≤ ni p(x) = q1(q2(...qn(x)...)), i wszystkie qinie będą dalej rozkładowi. Rozkład niekoniecznie jest wyjątkowy.
  • Możesz użyć np. List współczynników lub wbudowanych typów wielomianów jako danych wejściowych i wyjściowych.
  • Zauważ, że wiele wbudowanych funkcji tego zadania rozkłada wielomiany na dane pole i niekoniecznie są liczbami całkowitymi, podczas gdy to wyzwanie wymaga wielomianów rozkładu liczb całkowitych. (Niektóre wielomiany całkowite mogą dopuszczać rozkład na wielomiany całkowite, a także rozkład zawierający racjonalne wielomiany).

Przykłady

x^2 + 1
[x^2 + 1] (all polynomials of degree 2 or less are not decomposable)
x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6 x - 1
[x^3 - 2, x^2 - 2x + 1]
x^4 - 8x^3 + 18x^2 - 8x + 2 
[x^2 + 1, x^2 - 4x + 1]
x^6 + x^2 + 1
[x^3 + x + 1, x^2]
x^6
[x^2, x^3]
x^8 + 4x^6 + 6x^4 + 4x^2 + 4 = (x^2 + 1)^4 + 3
[x^2 + 3, x^2, x^2 + 1]
x^6 + 6x^4 + x^3 + 9x^2 + 3x - 5
[x^2 + x - 5, x^3 + 3*x], [x^2 + 5*x + 1, x^3 + 3*x - 2]

Użyj Maxima do generowania przykładów: Wypróbuj online!

Niektóre algorytmy rozkładu można znaleźć tutaj i tutaj .

code-golf math number abstract-algebra polynomials wada
źródło

Odpowiedzi:

4

Pari / GP , 84 bajtów

f(p)=[if(q'',[f(q),r],p)|r<-x*divisors(p\x),r''&&p==subst(q=substpol(p,r,x),x,r)][1]

Na podstawie opisanego tutaj algorytmu .

Wypróbuj online!

alephalpha
źródło
1
Czy sprawdzasz (lub odfiltrowujesz), czy faktycznie otrzymujesz rozkład na integralne wielomiany? (Pytam, ponieważ algorytmy w powiązanym dokumencie opisują faktoryzację w pewnym polu i nie znam żadnego Pari / GP.)
flawr
1
@flawr Używam drugiego algorytmu w dokumencie, który zawsze zwraca całki wielomiany, gdy dane wejściowe są całkami. W rzeczywistości divisorsfunkcja w Pari / GP zawsze zwraca prymitywne wielomiany, gdy przyjmuje całkę wielomianową. Można udowodnić, że jeśli p=q∘r, gdzie pi rsą integralne, i rsą prymitywne r(0)=0, to qtakże muszą być integralne. Tutaj p, q, rodpowiadają f, g, hna papierze.
alephalpha
2

Wolfram Language (Mathematica) , 29 bajtów

Decompose[#/.x->x+a,x]/.a->0&

Wypróbuj online!

Mam tu ustawiony przykład, aby skomponować losowy wielomian z losowych kwadratów (lub mniej), rozwinąć go, a następnie spróbować go rozłożyć.

Konieczne jest skomplikowanie wielomianu zmienną fikcyjną (a), ponieważ wbudowany nie będzie próbował rozkładać jednomianu.

Zauważam, że odpowiedź często ma znacznie większe współczynniki niż w oryginalnym składzie, ale w rzeczywistości zawsze są liczbami całkowitymi.

Kelly Lowder
źródło
Gdzie znalazłeś informacje, Decompose[]które zawsze zwracają integralne wielomiany (jeśli są zasilane wielomianami całkowitymi)? Podczas niedawnej dyskusji na czacie nie mogliśmy nic na ten temat znaleźć.
flawr
1
Zrób Options@Decomposei to ci powie {Modulus->0}. Teraz spójrz w górę Modulus, a zobaczysz „Ustawienie Modulus-> 0 określa pełny pierścień [DoubleStruckCapitalZ] liczb całkowitych.”
Kelly Lowder
Ach, to miło, dziękuję za opracowanie!
flawr