7
\$\begingroup\$

Introduction

A circle-tangent polynomial is a polynomial of degree \$N\ge3\$ or above that is tangent to the unit circle from inside at all of its N-1 intersection points. The two tails that exits the circle are considered tangent at their intersection points from inside as well. You may consider such polynomials are wrapped inside the unit circle except for the two tails.

The first several circle-tangent polynomials are shown here.

enter image description here enter image description here

The mirror images of a circle-tangent polynomial along x- or y- axis are also circle-tangent polynomials.

Challenge

Write a full program or function that, given a whole number input \$N\ge3\$, outputs a circle-tangent polynomial. You may either output the whole polynomial or only its coefficient in a reasonable order. Since such coefficients can be irrational, floating point inaccuracy within reasonable range is allowed.

The algorithm you used should be theoretically able to calculate with any valid input provided, although in reality the program could timeout.

Since this is a code-golf challenge, the shortest code of each language wins.

Example input/output

Both exact forms and approximate forms are shown for reference. The polynomials here are shown with positive leading terms, but mirrored counterparts around the axes are acceptable. The approximate forms are shown with 6 decimal places, but the calculation should be as accurate as possible.

Input -> Output

3     -> 8√3/9 x^3 - √3 x
         1.539601 x^3 - 1.732051 x

4     -> 27/8 x^4 - 9/2 x^2 + 1
         3.375 x^4 - 4.5 x^2 + 1

5     -> 2048√15/1125 x^5 - 128√15/45 x^3 + √15 x
         7.050551 x^5 - 11.016486 x^3 + 3.872983 x

6     -> 3125/216 x^6 - 625/24 x^4 + 25/2 x^2 - 1
         14.467593 x^6 - 26.041667 x^4 + 12.5 x^2 - 1

7     -> 1492992√35/300125 x^7 - 62208√35/6125 x^5 + 216√35/35 x^3 - √35 x
         29.429937 x^7 - 60.086121 x^5 + 36.510664 x^3 - 5.916080 x

Restrictions

NO HARDCODING POLYNOMIALS. NO USE OF DEFAULT LOOPHOLES.

\$\endgroup\$
5
  • \$\begingroup\$ Does it mean that the two intersections that enters and exits the circle has multiplicity 3, and other intersections has multiplicity 2? \$\endgroup\$
    – alephalpha
    Commented Jun 14, 2022 at 6:21
  • \$\begingroup\$ @alephalpha I'd say, yes. This is how I calculated the degree 7 case \$\endgroup\$ Commented Jun 14, 2022 at 6:41
  • \$\begingroup\$ Is y=0.5*x^2-1 also a circle-tangent polynomial with N=2, and y=x+sqrt(2) a circle-tangent polynomial with N=1? \$\endgroup\$ Commented Jun 14, 2022 at 14:09
  • \$\begingroup\$ @DominicvanEssen It's not defined for N=2 and N=1 \$\endgroup\$ Commented Jun 15, 2022 at 0:02
  • \$\begingroup\$ @Shieru Asakoto Is there any example programme? \$\endgroup\$
    – 138 Aspen
    Commented Sep 5, 2023 at 2:03

2 Answers 2

7
\$\begingroup\$

Wolfram Language (Mathematica), 84 bytes

-18 bytes thanks to @att. Now returns a polynomial in Quantifier`LocalVariable$1.

p/.#&@@Solve@ForAll[x,t#2#####&@@(x-b/@2~Range~#)==x^2+(p=Sum[a@i*x^i,{i,0,#}])p-1]&

Try it online!

This is the first time that I write ##### in a Mathematica program.

The two intersections that enters and exits the circle have multiplicity 3, and other intersections have multiplicity 2.

Let the polynomial be \$p=\sum_{i=0}^{N} a_i x^i\$, and the \$x\$-coordinate of the intersections be \$x_1,\dots,x_{N-1}\$, where \$x_1\$ and \$x_2\$ has multiplicity 3. Then we must have \$x^2+(\sum_{i=0}^{N} a_i x^i)^2-1 = t(x-x_1)(x-x_2)\prod_{i=1}^{N-1}(x-x_i)^2\$ for some \$t\$ and for all \$x\$. Comparing the coefficients of \$x\$, we have \$2N+1\$ equations and \$2N+1\$ unknowns (\$a_0,\dots,a_N,x_1,\dots,x_{N-1},t\$). We can solve this with the built-in function Solve.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ #==0&/@ -> 0== \$\endgroup\$
    – att
    Commented Jun 14, 2022 at 7:10
  • 5
    \$\begingroup\$ At first glance, I thought ##### was some self-censored swear word. :-p \$\endgroup\$
    – Arnauld
    Commented Jun 14, 2022 at 7:19
  • 1
    \$\begingroup\$ 94 using O to get the coefficient list \$\endgroup\$
    – att
    Commented Jun 14, 2022 at 8:05
  • 1
    \$\begingroup\$ 86 bytes \$\endgroup\$
    – att
    Commented Jun 18, 2022 at 0:12
  • 2
    \$\begingroup\$ Just for the sake of posterity, #### is equivalent to Times[##,##], as explained in this post: codegolf.stackexchange.com/questions/12900/… It took me a long time to understand this answer, but I think it's great! \$\endgroup\$
    – dirvine
    Commented Mar 5, 2023 at 4:15
1
\$\begingroup\$

Maxima, 227 bytes

Port of @alephalpha's Mathematica code in Maxima.

This is the first time that I write a Maxima program.


Golfed version. Try it online!

f(n):=block(p:sum(a[i]*x^i,i,0,n),realonly:true,Z:subst(first(solve(makelist(coeff(expand(x^2+(p^2-1)-t*(x-x[1])*(x-x[2])*product((x-x[i])^2,i,1,n-1)),x,i)=0,i,0,2*n),append(makelist(a[i],i,0,n),makelist(x[i],i,1,n),[t]))),p))$

Ungolfed version. Try it online!

kill(all);
f(n):=block(
  p: sum(a[i]*x^i, i, 0, n),
  equationLHS: x^2 + (p^2 - 1),
  equationRHS: 
    t*(x - x[1])*(x - x[2])*
    product((x - x[i])^2, i, 1, n - 1),
  equation: expand(equationLHS - equationRHS),

  /* Get the coefficients of the equation and set them to zero */
  equations: makelist(coeff(equation, x, i) = 0, i, 0, 2*n),

  realonly: true,  /* Setting Maxima to prefer real solutions */
  solution: solve(equations, append(makelist(a[i], i, 0, n), makelist(x[i], i, 1, n), [t])),

  /* Substitute the first solution into p */
  ans: subst(first(solution), p)
)$


print(makelist(f(n), n, 3, 4));
\$\endgroup\$

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.