Self Referential Polynomials

Question

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)

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 

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

Julia, 172 bytes

Similar to the Mathematica code in OEIS.

---

Try it online!

using LinearAlgebra
function f(n)
n=n+1
V=nullspace([ifelse(k == 1, 1, (j - 1)^(k - 1)) for j in 1:n, k in 1:n] - I)[:,1]
if(V[end]<0) V=-V;end
(V/maximum(V))[end:-1:1]
end

---

Here, these coefficients are normalized by dividing by the maximum value of the coefficients.

How to adjust the code?

using LinearAlgebra

function VM(n)
    return [ifelse(k == 1, 1, (j - 1)^(k - 1)) for j in 1:n, k in 1:n]
end

function f(n)
    V = nullspace(VM(n + 1) - I)
    V = V[:, 1] # Get the first column
    if V[end] < 0
        V = -V
    end
    return (V / maximum(V))[end:-1:1] # Normalize and reverse
end

for n in 0:10
    print(f(n), "\n")
end