Probar que un número es algebraico

10

Inspirado por esta respuesta (énfasis mío):

Nosotros jugaremos un juego. Supongamos que tienes algún número x . Comienza con x y luego puede sumar, restar, multiplicar o dividir por cualquier número entero, excepto cero. También puedes multiplicar por x . Puedes hacer estas cosas tantas veces como quieras. Si el total se convierte en cero, ganas.

Por ejemplo, supongamos que x es 2/3. Multiplica por 3, luego resta 2. El resultado es cero. ¡Tú ganas!

Supongamos que x es 7 ^ (1/3). Multiplique por x , luego por x nuevamente, luego reste 7. ¡Usted gana!

Supongamos que x es √2 + √3. Aquí no es fácil ver cómo ganar. Pero resulta que si multiplicas por x , restas 10, multiplicas por x dos veces y sumas 1, entonces ganas. (No se supone que esto sea obvio; puedes probarlo con tu calculadora).

Pero si comienzas con x = π, no puedes ganar. No hay forma de pasar de π a 0 si sumas, restas, multiplicas o divides por enteros, o multiplicas por π, sin importar cuántos pasos sigas. (Esto tampoco se supone que sea obvio. ¡Es algo muy complicado!)

Los números como √2 + √3 de los cuales puedes ganar se llaman algebraicos . Los números como π con los que no puedes ganar se llaman trascendentales.

¿Por qué es esto interesante? Cada número algebraico está relacionado aritméticamente con los enteros, y los movimientos ganadores en el juego te muestran cómo. El camino a cero puede ser largo y complicado, pero cada paso es simple y hay un camino. Pero los números trascendentales son fundamentalmente diferentes: no están relacionados aritméticamente con los enteros a través de pasos simples.


Esencialmente, utilizará los pasos utilizados en la pregunta citada anteriormente para "ganar" el juego para la entrada dada.

Dada una constante algebraica real, xconvierta el número a cero utilizando las siguientes operaciones permitidas:

  • Sumar o restar un número entero.
  • Multiplicar o dividir por un número entero distinto de cero.
  • Multiplica por la constante original x.

La entrada es una cadena que puede contener enteros, suma, resta, multiplicación, división, exponenciación (su elección de **o ^, los exponentes se usan para representar raíces) y paréntesis. Los espacios en la entrada son opcionales, pero no en la salida. Debe generar los pasos necesarios para obtener un resultado de cero, por lo que multiplicar por 7como un paso se generaría como *7. Se permite un espacio final y / o nueva línea.

Ejemplos

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

El código más corto gana.

mbomb007
fuente
¿Qué tan cerca 0deben estar los resultados? Dados los errores de redondeo y la precisión de flotación, pude ver fácilmente situaciones problemáticas ...
AdmBorkBork
2
@TimmyD La respuesta debe ser exacta, de modo que pueda realizar las operaciones y obtener cero. Ver los ejemplos proporcionados. No hay aritmética de coma flotante.
mbomb007
1
¿Cómo es √2 + √3 algebraico? Si multiplica el número por sí mismo, obtiene 5 + 2√6 ... a menos que me falte algo, nunca puede forzar el radical.
Mario Ishac
@ mbomb007 Vaya, mis disculpas, no entendí eso en el OP.
Mario Ishac
1
Es una solución a la ecuación x^4-10*x^2+1. Ver WolframAlpha
mbomb007

Respuestas:

3

SageMath , 108 bytes

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

Pruébalo en SageMathCell .

Explicación:

Evalúe la cadena simbólicamente como un número algebraico ( sage_eval()). Cada número algebraico es un cero de algún polinomio a [0] + a [1] x ^ 1 + a [2] x ^ 2 + ⋯ + a [n] x ^ n con coeficientes racionales a [0],…, a [ n ] ( minpoly()). Multiplique todos los coeficientes por su denominador común para convertirlos en enteros ( numerator()), luego escriba este polinomio en el formato de salida deseado,

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

SageMath, 102 bytes, casi

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

Esto funciona para todas las entradas excepto 0, porque un polinomio para 1 / α es un polinomio para α con los coeficientes invertidos. :-(

Anders Kaseorg
fuente
1

Mathematica 194 224 192 bytes

""<>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,∞}]&

Aquí está el carácter unicode de tres bytes que representa el infinito en Mathematica.

Como la entrada es una cadena, se pierden 13 bytes, lo ToExpression@que interpreta la entrada de la cadena como una expresión algebraica.

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

Volvería algo como

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

La siguiente regla de reemplazo masajea esto en algo que es estructuralmente similar

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

Esta forma de Horner se puede visualizar como un árbol:

TreeForm

Nosotros, según las reglas de OP, comenzamos con la hoja más profunda a la derecha.

Cases pasa por la expresión, comenzando en el nivel más profundo, tomando cada nodo padre y su hoja izquierda y ensamblando esto en una tabla como

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

""<> concatena todo con la cadena vacía.

LLlAMnYP
fuente
Esto devuelve incorrectamente -299para 5/7 + 42.
Anders Kaseorg
@Y así que omite el * 7 ... lo comprobaré una vez que esté en casa
LLlAMnYP
@AndersKaseorg esto funciona, pero ahora tengo 30 bytes menos.
LLlAMnYP