Consider some arbitrary polynomial with integer coefficients,
$$a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 = 0$$
We'll assume that \$a_n \ne 0\$ and \$a_0 \ne 0\$. The solutions to this polynomial are algebraic numbers. For example, take the polynomial $$x^4 - 10x^2 + 1 = 0$$
We have that \$x = \sqrt 2 + \sqrt 3\$ is a solution to this polynomial, and so \$\sqrt 2 + \sqrt 3\$ must be an algebraic number. However, most real numbers, such as \$\pi\$ or \$e\$ are not algebraic.
Given any algebraic number \$x\$, it is possible to construct a polynomial \$p\$ such that \$p(x) = 0\$. However, this is not unique. For example, $$x^6 - 99x^2 + 10 = 0$$ also has a root \$x = \sqrt 2 + \sqrt 3\$. We define the minimal polynomial of an algebraic number \$x\$ to the be polynomial \$p\$ such that \$p(x) = 0\$ and the order of \$p\$ is minimal. With our example \$x = \sqrt 2 + \sqrt 3\$, there exists no such quadratic or cubic polynomial with \$x\$ as a root, as \$x^4 - 10x^2 + 1\$ is the minimal polynomial of \$x = \sqrt 2 + \sqrt 3\$. If the order of \$p\$ is \$n\$, we say that \$x\$ is an "algebraic number of order \$n\$". For example, \$\sqrt 2 + \sqrt 3\$ is of order \$4\$.
For the purposes of this challenge, we'll only consider real algebraic numbers termed "closed form algebraic numbers". These are algebraic numbers that can be expressed as some combination of addition, subtraction, multiplication, division and \$n\$th order radicals (for integer \$n\$).
For example, this includes \$\varphi = \frac {1 + \sqrt 5} 2\$, and \$7\sqrt[3] 2 - \sqrt[10] 3\$, but not e.g. roots of \$x^5 - x - 1 = 0\$, or \$\sqrt[\sqrt 2] 3\$ (\$n\$th roots are only allowed with integer \$n\$).
You are to take a real algebraic number as input, with the guarantee that it can be constructed with our 5 operations, and output the order of the input. The order will always be a positive integer.
You may take input in any form that exactly represents any closed form algebraic numbers. This could be as an exact symbolic number (if your language has these), a string unambiguously representing the composition of the 5 operations (e.g. 7*root(2,3)-root(3,10)
, 7*(2r3)-(3r10)
or even sub(times(7, root(2, 3)), root(3, 10))
), and so on. You may not input as floating point values. Note that the format you choose should be unambiguous, so is likely to use e.g. parentheses for grouping/precedence. For example, 7*2r3-3r10
does not meet this requirement, as it can be interpreted in a number of ways, depending on the precedence of each command.
In short, you may choose any input format - not limited to strings - so long as that input format can represent any closed form algebraic number exactly and unambiguously. Additionally, be mindful of this standard loophole about encoding extra information into the input format - this is fairly loose, but try not to use formats that contain more information than just the 5 standard operations.
If your answer uses a builtin that takes an algebraic number as input and returns either the order of the number, or the minimal polynomial, please edit it into this list of trivial answers.
This is code-golf, so the shortest code in bytes wins.
Test cases
I'm expressing the inputs here using Mathematica's Surd[n, k]
function to represent \$\sqrt[k] n\$, along with +
, -
, *
and /
to represent \$+\$, \$-\$, \$\times\$ and \$\div\$ respectively.
input -> output
5/6 -> 1
Surd[4, 2] -> 1
Surd[2, 2] * Surd[2, 2] -> 1
(Surd[5, 2] + 1)*(Surd[5, 2] - 1) -> 1
(Surd[5, 2] + 1)/2 -> 2
(Surd[5, 2] + 1)*(Surd[5, 2] + 1) -> 2
Surd[2, 2] + Surd[3, 2] -> 4
Surd[(Surd[5, 2] + 1)/2, 2] -> 4
Surd[5, 5] - 2 -> 5
Surd[5, 5] + Surd[3, 7] - 2*Surd[2, 2] -> 70
The polynomials for these cases are given by Try it online!
Surt[4, 2] -> 1
,Surd[2, 2] * Surd[2, 2] -> 1
. \$\endgroup\$(Surd[5, 2] + 1) (Surd[5, 2] - 1) -> 1
,(Surd[5, 2] + 1) (Surd[5, 2] + 1) -> 2
(thanks to @tsh ). My answer using resultants cannot tell the difference between these two. \$\endgroup\$