# Self Referential Polynomials

For every given degree $$\n\$$ it is possible to construct (at least one) an integral polynomial $$\p \in \mathbb Z[X]\$$ such that $$\p(k)\$$ ($$\p\$$ evaluated in $$\k\$$) is the coefficient of the term $$\x^k\$$ in the polynomial for all $$\0 \leqslant k \leqslant 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\$$:

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

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

• @LuisMendo Thanks, apparently I'm a fanatic. Jun 1, 2016 at 11:17

# 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.

# 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

# Pari/GP, 57 bytes

n->(a=matkerint(matrix(n++,,i,j,i--^j--)-1))*sign(a[n,1])


Try it online!

Returns the coefficients as a column vector.