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\$:

enter image description here

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.


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 
  • \$\begingroup\$ Congrats on your gold badge! \$\endgroup\$
    – Luis Mendo
    Jun 1, 2016 at 8:56
  • \$\begingroup\$ @LuisMendo Thanks, apparently I'm a fanatic. \$\endgroup\$
    – flawr
    Jun 1, 2016 at 11:17

4 Answers 4


Mathematica, 55 bytes


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

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









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


Try it online!

Returns the coefficients as a column vector.


Julia, 172 bytes

Similar to the Mathematica code in OEIS.

Try it online!

using LinearAlgebra
function f(n)
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

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]

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

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

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.