24
\$\begingroup\$

Given a polynomial p(x) with integral coefficients and a constant term of p(0) = 1 or -1, and a nonnegative integer N, return the N-th coefficient of the power seris (sometimes called "Taylor series") of f(x) = 1/p(x) developed at x0 = 0, i.e., the coefficient of the monomial of degree N.

The given conditions ensure that the power series exist and that the its coefficients are integers.

Details

As always the polynomial can be accepted in any convenient format, e.g. a list of coefficients, for instance p(x) = x^3-2x+5 could be represented as [1,0,-2,5].

The powerseries of a function f developed at 0 is given by

and the N-th coefficient (the coefficient of x^N) is given by

where denotes the n-th derivative of f

Examples

  • The polynomial p(x) = 1-x results in the geometric series f(x) = 1 + x + x^2 + ... so the output should be 1 for all N.

  • p(x) = (1-x)^2 = x^2 - 2x + 1 results in the derivative of the geometric series f(x) = 1 + 2x + 3x^2 + 4x^3 + ..., so the output for N is N+1.

  • p(x) = 1 - x - x^2 results in the generating function of the Fibonacci sequence f(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ...

  • p(x) = 1 - x^2 results in the generating function of 1,0,1,0,... i.e. f(x) = 1 + x^2 + x^4 + x^6 + ...

  • p(x) = (1 - x)^3 = 1 -3x + 3x^2 - x^3 results in the generating function of the triangular numbers f(x) = 1 + 3x + 6x^6 + 10x^3 + 15x^4 + 21x^5 + ... that means the N-th coefficient is the binomial coefficient (N+2, N)

  • p(x) = (x - 3)^2 + (x - 2)^3 = 1 + 6x - 5x^2 + x^3 results in f(x) = 1 - 6x + 41x^2 - 277x^3 + 1873x4 - 12664x^5 + 85626x^6 - 57849x^7 + ...

\$\endgroup\$
  • \$\begingroup\$ Would it be acceptable to take a polynomial as an infinite list of power-series coefficients like [1,-1,0,0,0,0,...]? \$\endgroup\$ – xnor Jan 1 '17 at 21:48
  • \$\begingroup\$ Yes, I think that this is an acceptable format. \$\endgroup\$ – flawr Jan 1 '17 at 21:54
  • \$\begingroup\$ Nice examples chosen! \$\endgroup\$ – Greg Martin Jan 1 '17 at 22:02
  • \$\begingroup\$ I'm glad you appreciate it, thank you=) \$\endgroup\$ – flawr Jan 2 '17 at 12:38
9
\$\begingroup\$

Mathematica, 24 23 bytes

Saved 1 byte thanks to Greg Martin

D[1/#2,{x,#}]/#!/.x->0&

Pure function with two arguments # and #2. Assumes the polynomial #2 satisfies PolynomialQ[#2,x]. Of course there's a built-in for this:

SeriesCoefficient[1/#2,{x,0,#}]&
\$\endgroup\$
  • 1
    \$\begingroup\$ Well done beating the built-in! I guess you can save a byte by assuming that # is the integer N and #2 is the polynomial. \$\endgroup\$ – Greg Martin Jan 1 '17 at 22:04
6
\$\begingroup\$

Matlab, 81 79 75 bytes

Unlike the previous two answers this doesn't make use of symbolic calculations. The idea is that you can iteratively calculate the coefficients:

function C=f(p,N);s=p(end);for k=1:N;q=conv(p,s);s=[-q(end-k),s];end;C=s(1)

Try it online!

Explanation

function C=f(p,N);
s=p(end);            % get the first (constant coefficient)
for k=1:N;           
    q=conv(p,s);     % multiply the known coefficients with the polynomial
    s=[-q(end-k),s]; % determine the new coefficient to make the the product get "closer" 
end;
C=s(1)           % output the N-th coefficient
\$\endgroup\$
4
\$\begingroup\$

GeoGebra, 28 bytes

Derivative[1/A1,B1]/B1!
f(0)

Input is taken from the spreadsheet cells A1 and B1 of a polynomial and an integer respectively, and each line is entered separately into the input bar. Output is via assignment to the variable a.

Here is a gif showing the execution:

Taylor coefficients

Using builtins is much longer, at 48 bytes:

First[Coefficients[TaylorPolynomial[1/A1,0,B1]]]
\$\endgroup\$
4
\$\begingroup\$

Haskell, 44 bytes

p%n=(0^n-sum[p!!i*p%(n-i)|i<-[1..n]])/head p

A direct computation without algebraic built-ins. Takes input as an infinite list of power series coefficients, like p = [1,-2,3,0,0,0,0...] (i.e. p = [1,-2,3] ++ repeat 0) for 1-2*x+x^2. Call it like p%3, which gives -4.0.

The idea is if p is a polynomial and q=1/p is it inverse, then we can express the equality p·q=1 term-by-term. The coefficient of xn in p·q is given by the convolution of the coefficients in p and q:

p0· qn + p1· qn-1 + ... + pn· q0

For p·q=1 to hold, the above must equal zero for all n>0. For here, we can express qn recursively in terms of q0, ..., qn-1 and the coefficients of p.

qn = - 1/p0 · (p1· qn-1 + ... + pn· q0)

This is exactly what's calculated in the expression sum[p!!i*p%(n-i)|i<-[1..n]]/head p, with head p the leading coefficient p0. The initial coefficient q0 = 1/p0 is handled arithmetically in the same expression using 0^n as an indicator for n==0.

\$\endgroup\$
3
\$\begingroup\$

J, 12 bytes

1 :'(1%u)t.'

Uses the adverb t. which takes a polynomial p in the form of a verb on the LHS and a nonnegative integer k on the RHS and computes the kth coefficient of the Taylor series of p at x = 0. In order to get the power series, the reciprocal of p is taken before applying it.

Try it online!

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

Maple, 58 26 bytes

This is an unnamed function that accepts a polynomial in x and an integer N.

EDIT: I just noticed that there is a builtin:

(p,N)->coeftayl(1/p,x=0,N)
\$\endgroup\$
1
\$\begingroup\$

MATL, 19 bytes

0)i:"1GY+@_)_8Mh]1)

Translation of @flawr's great Matlab answer.

Try it online!

How it works

0)      % Implicitly input vector of polynomial coefficients and get last entry
i       % Input N
:"      % For k in [1 2 ... N]
  1G    %   Push vector of polynomial coefficients
  Y+    %   Convolution, full size
  @     %   Push k
  _     %   Negate
  )     %   Index. This produces the end-k coefficient
  _     %   Negate
  8M    %   Push first input of the latest convolution
  h     %   Concatenate horizontally
]       % End
1)      % Get first entry. Implicitly display
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 57 bytes

(a,n)=>a.reduce((s,p,i)=>!i|i>n?s:s-p*f(a,n-i),!n)/a[0]

Port of @xnor's Haskell answer. I originally tried an iterative version but it turned out to be 98 bytes, however it will be much faster for large N, as I'm effectively memoising the recursive calls:

(a,n)=>[...Array(n+1)].fill(0).map((_,i,r)=>r[i]=r.reduce((s,p,j)=>s-p*(a[i-j]||0),!i)/a[0]).pop()

n+1 terms are required, which are saved in the array r. It is initially zeros which allows reducing over the entire array r at once, as the zeros will not affect the result. The last calculated coefficient is the final result.

\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 31 27 bytes

f->n->Pol(Ser(1/f,,n+1))\x^n
\$\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.