I was wondering if there is a way in Python (or any language for that matter), where I can supply a list of numbers and I get back a polynomial of smallest degree that results in that list of numbers.
E.g. If I supply the sequence 1,4,9,16 I should get back n**2 or n^2.
You can code a routine yourself using the sympy module in Python. (This is a popular third-party module for Python.) This code uses the base formula for the Lagrange polynomial, the polynomial of smallest degree that yields a given sequence. This code allow you to define your own x-values in addition to the y-values: if you do not define the x-values, this routine will use 1, 2, .... Note that there are other ways to get this polynomial--I used the formula used in Wikipedia in the link.
import sympy
x = sympy.symbols('x')
zeropoly = x - x
onepoly = zeropoly + 1
def lagrangepoly(yseq, xseq=None):
"""Build a Lagrange polynomial from a sequence of `y` values.
If no sequence of `x`s is given, use x = 1, 2, ..."""
if xseq is None:
xseq = list(range(1, len(yseq) + 1))
assert len(yseq) == len(xseq)
result = zeropoly
for j, (xj, yj) in enumerate(zip(xseq, yseq)):
# Build the j'th base polynomial
polyj = onepoly
for m, xm in enumerate(xseq):
if m != j:
polyj *= (x - xm) / (xj - xm)
# Add in the j'th polynomial
result += yj * polyj
return sympy.expand(result)
With that routine, executing print(lagrangepoly([1, 4, 9, 16])) gets the printout
x**2
which is x^2 in Python notation.