12
\$\begingroup\$

For every given degree n it is possible to construct (at least one) an integral polynomial p such that p(k) (p evaluated in k) is the coefficient of the term x^k in the polynomial for all 0 <= k <= n. To make them unique, we require the leading coefficient (the coefficient of x^n) to be positive and minimal.

These polynomials have some interesting properties, you can find some references in the thread that inspired me to do this challenge. You can also find those polynomials in https://oeis.org/A103423

One of the a priori unexpected properties is how the roots behave depending on n:

enter image description here

source (by /u/zorngov and /u/EpicSauceSc2)

Task

Given a nonnegative integer n output the self referential integral polynomial of degree n with minimal positive leading coefficient.

Details

The output can be in any human readable form, as string x^2-x-1, or also as a list of coefficients [1,-1,-1]. (The order of the coefficients can also be the other way around, it just needs to be consistent.)

First few outputs

n=0: 1
n=1: x
n=2: x^2-x-1
n=3: 10*x^3-29*x^2-6*x+19
n=4: 57*x^4-325*x^3+287*x^2+423*x-19
n=5: 12813*x^5-120862*x^4+291323*x^3+44088*x^2-355855*x-227362 
\$\endgroup\$
  • \$\begingroup\$ Congrats on your gold badge! \$\endgroup\$ – Luis Mendo Jun 1 '16 at 8:56
  • \$\begingroup\$ @LuisMendo Thanks, apparently I'm a fanatic. \$\endgroup\$ – flawr Jun 1 '16 at 11:17
2
\$\begingroup\$

Sage, 74 bytes

lambda n:kernel(matrix(n+1,[j^-i-(-i==j)for i in[-n..0]for j in[0..n]])).0

The -i and [-n..0] could be i and [0..n], if not for the positive leading coefficient requirement.

Try it on Sage Cell

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 55 bytes

NullSpace@Table[x^c-Boole[r==c]/.x->r,{r,0,#},{c,0,#}]&

Output is the list coefficients, beginning from the constant term. Example:

In[1084] := Do[Print[%1077[n] // StandardForm], {n, 0, 7}]

{{1}}

{{0,1}}

{{-1,-1,1}}

{{19,-6,-29,10}}

{{-19,423,287,-325,57}}

{{-227362,-355855,44088,291323,-120862,12813}}

{{145991969,64989065,-123338281,-85635661,79841909,-18146731,1286795}}

{{-5958511844199,3384370785404,8437850634901,489428412300,-4499161007143,1776194531596,-258931801371,13131073916}}

This simply finds the vector such that (A - I)v = 0, similar to the MAPLE code in OEIS. The NullSpace method seems to always pick the minimal positive number for the last element, which matches the task description.

The x^c-…/.x->r indirection is to prevent having 0^0 == Indeterminate.

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 64 bytes

n->a=matkerint(Mat([powers(i,n)|i<-[0..n]]~)-1);a*sign(a[n+1,1])

Returns the coefficients as a column vector.

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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