Prove that a Number is Algebraic

Question

Inspired by this answer (emphasis mine):

We will play a game. Suppose you have some number x. You start with x and then you can add, subtract, multiply, or divide by any integer, except zero. You can also multiply by x. You can do these things as many times as you want. If the total becomes zero, you win.

For example, suppose x is 2/3. Multiply by 3, then subtract 2. The result is zero. You win!

Suppose x is 7^(1/3). Multiply by x , then by x again, then subtract 7. You win!

Suppose x is √2+√3. Here it's not easy to see how to win. But it turns out that if you multiply by x, subtract 10, multiply by x twice, and add 1, then you win. (This is not supposed to be obvious; you can try it with your calculator.)

But if you start with x=π, you cannot win. There is no way to get from π to 0 if you add, subtract, multiply, or divide by integers, or multiply by π, no matter how many steps you take. (This is also not supposed to be obvious. It is a very tricky thing!)

Numbers like √2+√3 from which you can win are called algebraic. Numbers like π with which you can't win are called transcendental.

Why is this interesting? Each algebraic number is related arithmetically to the integers, and the winning moves in the game show you how so. The path to zero might be long and complicated, but each step is simple and there is a path. But transcendental numbers are fundamentally different: they are not arithmetically related to the integers via simple steps.

---

Essentially, you will use the steps used in the question quoted above to "win" the game for given input.

Given a real, algebraic constant x, convert the number to zero by using the following allowed operations:

• Add or Subtract an integer.
• Multiply or Divide by a non-zero integer.
• Multiply by the original constant x.

Input is a string that may contain integers, addition, subtraction, multiplication, division, exponentiation (your choice of ** or ^, exponents are used to represent roots), and parentheses. Spaces in the input are optional, but not in the output. You should output the steps necessary to obtain a result of zero, so multiplying by 7 as one step would be output as *7. A trailing space and/or newline is allowed.

Examples

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

Shortest code wins.

Answer 1

SageMath, 108 bytes

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

Try it on SageMathCell.

Explanation:

Evaluate the string symbolically as an algebraic number (sage_eval()). Every algebraic number is a zero of some polynomial a[0] + a[1] x^1 + a[2] x^2 + ⋯ + a[n] x^n with rational coefficients a[0], …, a[n] (minpoly()). Multiply all the coefficients by their common denominator to turn them into integers (numerator()), then write this polynomial in the desired output format,

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

SageMath, 102 bytes, almost

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

This works for all inputs except 0, because a polynomial for 1/α is a polynomial for α with the coefficients reversed. :-(

Answer 2

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

Here ∞ is the three byte unicode character representing infinity in Mathematica.

Since input is a string, 13 bytes are lost on ToExpression@ which interprets the string input as an algebraic expression.

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

Would return something like

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

The next replacement rule massages this into something that is structurally like

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

This Horner form can be visualized like a tree:

We, by the rules of OP start out with the deepest leaf on the right.

Cases goes through the expression, starting at the deepest level, taking each parent node and its left leaf and assembling this into a table such as

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

""<> concatenates everything with the empty string.