Wykazać, że liczba jest algebraiczna

10

Zainspirowany tą odpowiedzią (moje podkreślenie):

Zagramy w grę. Załóżmy, że masz jakąś liczbę x . Zaczynasz od x, a następnie możesz dodawać, odejmować, mnożyć lub dzielić przez dowolną liczbę całkowitą, z wyjątkiem zera. Możesz także pomnożyć przez x . Możesz robić te rzeczy tyle razy, ile chcesz. Jeśli suma wyniesie zero, wygrywasz.

Załóżmy na przykład, że x wynosi 2/3. Pomnóż przez 3, a następnie odejmij 2. Wynik wynosi zero. Wygrałeś!

Załóżmy, że x wynosi 7 ^ (1/3). Pomnóż przez x , następnie przez x ponownie, a następnie odejmij 7. Wygrywasz!

Załóżmy, że x wynosi √2 + √3. Tutaj nie jest łatwo zobaczyć, jak wygrać. Ale okazuje się, że jeśli pomnożysz przez x , odejmiesz 10, pomnożysz przez x dwa razy i dodasz 1, wtedy wygrasz. (To nie powinno być oczywiste; możesz spróbować za pomocą kalkulatora).

Ale jeśli zaczniesz od x = π, nie możesz wygrać. Nie ma możliwości przejścia od π do 0, jeśli dodasz, odejmiesz, pomnożysz lub podzielisz przez liczby całkowite lub pomnożysz przez π, bez względu na to, ile kroków wykonasz. (To również nie powinno być oczywiste. To bardzo trudna sprawa!)

Liczby takie jak √2 + √3, z których możesz wygrać, nazywane są algebraicznymi . Liczby takie jak π, z którymi nie można wygrać, nazywane są transcendentalnymi.

Dlaczego to jest interesujące? Każda liczba algebraiczna jest powiązana arytmetycznie z liczbami całkowitymi, a zwycięskie ruchy w grze pokazują, jak to zrobić. Ścieżka do zera może być długa i skomplikowana, ale każdy krok jest prosty i istnieje ścieżka. Ale liczby transcendentalne są zasadniczo różne: nie są one arytmetycznie powiązane z liczbami całkowitymi za pomocą prostych kroków.


Zasadniczo wykorzystasz kroki użyte w powyższym pytaniu, aby „wygrać” grę dla danego wkładu.

Biorąc pod uwagę rzeczywistą stałą algebraiczną x, przekonwertuj liczbę na zero, używając następujących dozwolonych operacji:

  • Dodaj lub odejmij liczbę całkowitą.
  • Pomnóż lub podziel przez niezerową liczbę całkowitą.
  • Pomnóż przez pierwotną stałą x.

Dane wejściowe to ciąg znaków, który może zawierać liczby całkowite, dodawanie, odejmowanie, mnożenie, dzielenie, potęgowanie (twój wybór **lub ^potęgi są używane do reprezentowania pierwiastków) i nawiasy. Spacje na wejściu są opcjonalne, ale nie na wyjściu. Powinieneś wypisać kroki niezbędne do uzyskania wyniku równego zero, więc pomnożenie przez 7jeden krok dałoby wynik jako*7 . Końcowe spacje i / lub nowa linia są dozwolone.

Przykłady

0               ->  +0 (or any other valid, or empty)
5/7 + 42        ->  -42 *7 -5 (or shorter: *7 -299)
2^(1/3)         ->  *x *x -2
5*(3**(1/4))    ->  *x *x *x -1875
2^(1/2)+3^(1/2) ->  *x -10 *x *x +1

Najkrótszy kod wygrywa.

mbomb007
źródło
Jak blisko 0muszą być wyniki? Biorąc pod uwagę błędy zaokrąglania i precyzję
liczby
2
@TimmyD Odpowiedź musi być dokładna, aby móc wykonać operacje i uzyskać zero. Zobacz podane przykłady. Nie ma arytmetyki zmiennoprzecinkowej.
mbomb007
1
Jak działa algebraiczna √2 + √3? Jeśli pomnożysz liczbę sam w sobie, otrzymasz 5 + 2√6 ... chyba że czegoś mi brakuje, nigdy nie możesz zmusić radykała.
Mario Ishac,
@ mbomb007 Ups, przepraszam, nie złapałem tego w OP.
Mario Ishac,
1
To rozwiązanie równania x^4-10*x^2+1. Zobacz WolframAlpha
mbomb007

Odpowiedzi:

3

SageMath , 108 bajtów

def f(s):p=map('{:+} '.format,numerator(minpoly(sage_eval(s)/1)));return'*'+p[-1][1:]+'*x '.join(p[-2::-1])

Wypróbuj na SageMathCell .

Wyjaśnienie:

Oceń łańcuch symbolicznie jako liczbę algebraiczną ( sage_eval()). Każda liczba algebraiczna jest zerem jakiegoś wielomianu a [0] + a [1] x ^ 1 + a [2] x ^ 2 + ⋯ + a [n] x ^ n ze współczynnikami wymiernymi a [0],…, a [ n ] ( minpoly()). Pomnóż wszystkie współczynniki przez ich wspólny mianownik, aby zamienić je na liczby całkowite ( numerator()), a następnie zapisz wielomian w żądanym formacie wyjściowym,

*a[n] +a[n-1] *x +a[n-2] *x … *x +a[1] *x +a[0]

SageMath, prawie 102 bajty

lambda s:(lambda a,*p:'*%d'%a+'*x'.join(map(' {:+} '.format,p)))(*numerator(minpoly(1/sage_eval(s))))

Działa to dla wszystkich wejść oprócz 0, ponieważ wielomian dla 1 / α jest wielomianem dla α z odwróconymi współczynnikami. :-(

Anders Kaseorg
źródło
1

Matematyka, 194 224 192 bajty

""<>Cases[HornerForm@MinimalPolynomial[ToExpression@#,x]//.{Times->t,x^a_:>Fold[#2~t~#&,x~Table~a],a_~t~b_~t~c_:>a~t~t[b,c]},a_~b_~_:>{b/.t:>"*"/.Plus:>If[a>0,"+",""],ToString@a," "},{0,∞}]&

Oto trzy bajtowy znak Unicode reprezentujący nieskończoność w Mathematica.

Ponieważ wejście jest łańcuchem, traconych jest 13 bajtów, na ToExpression@których interpretowany jest ciąg znaków jako wyrażenie algebraiczne.

HornerForm@MinimalPolynomial[2^(1/2)+3^(1/2), x]

Zwróciłbym coś takiego

1 + x^2 (-10 + x^2)

Następna reguła zastępująca masuje to w coś, co jest strukturalnie podobne

1 + (x * (x * (-10 + (x * (x)))))

Ta forma Hornera może być wizualizowana jak drzewo:

TreeForm

My, według zasad OP, zaczynamy od najgłębszego liścia po prawej stronie.

Cases przechodzi przez wyrażenie, zaczynając od najgłębszego poziomu, biorąc każdy węzeł nadrzędny i jego lewy liść i składając to w tabelę, taką jak

"*" "x"   " "
""  "-10" " "
"*" "x"   " "
"*" "x"   " "
"+" "1"   " "

""<> łączy wszystko z pustym ciągiem.

LLAMAMYP
źródło
To niepoprawnie zwraca -299dla 5/7 + 42.
Anders Kaseorg,
@I to pomija * 7 ... Sprawdzę dwukrotnie, kiedy będę w domu
LLlAMnYP
@AndersKaseorg to działa, ale teraz mam 30 bajtów mniej.
LLlAMnYP