5
\$\begingroup\$

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 , 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!

\$\endgroup\$
6
  • \$\begingroup\$ Sandbox \$\endgroup\$ Commented Dec 24, 2021 at 2:22
  • 1
    \$\begingroup\$ To my understanding, the \$n\$th order radicals rule only require \$n\$ be integer. But not the expression in it. So \$ \sqrt{\frac{1+\sqrt{5}}{2}} \$ is a valid expression for input. If so, I would suggest add any of them. \$\endgroup\$
    – tsh
    Commented Dec 24, 2021 at 3:02
  • \$\begingroup\$ Some testcases: Surt[4, 2] -> 1, Surd[2, 2] * Surd[2, 2] -> 1. \$\endgroup\$
    – alephalpha
    Commented Dec 24, 2021 at 3:28
  • \$\begingroup\$ Some more testcases: (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\$
    – alephalpha
    Commented Dec 24, 2021 at 4:20
  • 1
    \$\begingroup\$ @alephalpha For simplicity's sake, I'll say that yes, all subexpressions will be real, and you don't have to worry about complex arithmetic \$\endgroup\$ Commented Mar 27, 2022 at 4:19

3 Answers 3

3
\$\begingroup\$

Trivial builtin answers

Wolfram Language (Mathematica), 33 bytes

#~MinimalPolynomial~x~Exponent~x&

Try it online!

Unsurprisingly, MinimalPolynomial returns the minimal polynomial of its input, and Exponent gets the highest exponent in this polynomial. We use a bit of infix notation (a~f~b is f[a,b]) to save a couple of bytes, and so this translates as

#~MinimalPolynomial~x~Exponent~x&
Exponent[#~MinimalPolynomial~x,x]&
Exponent[MinimalPolynomial[#,x],x]&
\$\endgroup\$
3
\$\begingroup\$

Trivial builtin answers

Python + sympy, 46 bytes

Saved 32 bytes thanks to @Stef


46 bytes version. Attempt This Online!

lambda y:degree(minpoly(y));from sympy import*

78 bytes version. Attempt This Online!

from sympy import*
x=symbols('x')
f=lambda y:degree(minimal_polynomial(y,x),x)
\$\endgroup\$
2
2
\$\begingroup\$

Wolfram Language (Mathematica), 175 bytes

Cases[FactorList@g@#,{y_,_}/;Simplify[y/.x->#/.s->D]==0:>y~Exponent~x]&
g@n_=x-n
g[p_~s@o_~q_]:=Resultant[g@q,g@p/.x-><|Plus->z-x,Times->z/x,Divide->z*x,Surd->z^q|>@o,x]/.z->x

Try it online!

Takes an expression as input, where:

  • \$p+q\$ is represented by s[Plus][p, q].
  • \$p\ q\$ is represented by s[Times][p, q].
  • \$p/q\$ is represented by s[Divide][p, q].
  • \$\sqrt[n]p\$ is represented by s[Surd][p, n].
  • There is no special form for \$p-q\$, because \$p-q\$ is just \$p+(-1)\times q\$.

For example, \$\sqrt[5]5+\sqrt[7]3-2\sqrt[2]2\$ is represented by s[Plus][s[Plus][s[Surd][5, 5], s[Surd][3, 7]], s[Times][-2, s[Surd][2, 2]]].

The idea is constructing a (usually not minimal) polynomial using resultants, factoring it, and choosing the correct factor. The last step requires checking whether a expression is equal to zero. I'm not sure if Simplify is powerful enough for all possible inputs, but at least it works for all the testcases.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Is m[a[r[5,2],1],s[r[5,2],1]] a correct encoding to \$\sqrt{\sqrt{5}+1} \cdot \sqrt{\sqrt{5}-1}\$? \$\endgroup\$
    – tsh
    Commented Dec 24, 2021 at 3:55
  • \$\begingroup\$ @tsh That is \$\sqrt{(\sqrt{5}+1)(\sqrt{5}-1)}\$... Thanks for finding a bug. \$\endgroup\$
    – alephalpha
    Commented Dec 24, 2021 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.