6
\$\begingroup\$

Earlier, we talked about exponential generating functions (e.g.f.).

Task

You will take a few terms of a sequence.

Your task is to find another sequence with that many terms, whose e.g.f., when multiplied to the original e.g.f., would be exactly the constant function 1 accurate to that many terms.

That is, given a0=1, a1, a2, ..., an, find b0=1, b1, b2, ..., bn such that a0 + a1x + a2x^2/2! + a3x^3/3! + ... + anx^n/n! multiplied by b0 + b1x + b2x^2/2! + b3x^3/3! + ... + bnx^n/n! equals 1 + O(x^(n+1)).

Specs

  • They will start at the zeroth power and will be consecutive.
  • The first term is guaranteed to be 1.
  • All the terms are guaranteed to be integers.
  • There will not be negative powers.

Testcases

Input : 1,0,-1,0,1,0,-1,0 (this is actually cos x)
Output: 1,0, 1,0,5,0,61,0 (this is actually sec x)

Input : 1, 2, 4, 8, 16, 32 (e^(2x))
Output: 1,-2, 4,-8, 16,-32 (e^(-2x))

Input : 1,-1,0,0, 0,  0,  0 (1-x)
Output: 1, 1,2,6,24,120,720 (1/(1-x) = 1+x+x^2+...)
\$\endgroup\$
  • 1
    \$\begingroup\$ When titling your next challenge, you may want to think about this meta.codegolf.stackexchange.com/a/8090/15599 \$\endgroup\$ – Level River St Jun 15 '16 at 23:24
  • \$\begingroup\$ Thank you! I have edited it away! I will bear that in mind next time! \$\endgroup\$ – Leaky Nun Jun 15 '16 at 23:29
  • \$\begingroup\$ Does the guarantee about integer coefficients apply only to the input, or to both input and output? \$\endgroup\$ – feersum Jun 16 '16 at 4:56
  • \$\begingroup\$ @feersum If the input has integer coefficients, then the output will also have integer coefficients. \$\endgroup\$ – Leaky Nun Jun 16 '16 at 5:22
  • 1
    \$\begingroup\$ Borderline duplicate \$\endgroup\$ – Peter Taylor Jun 16 '16 at 10:05
3
\$\begingroup\$

Julia, 91 81 77 bytes

!v=(b=[1;0v[r=2:end]];for i=r,j=0:i-2 b[i]-=binomial(i-1,j)v[i-j]b[j+1]end;b)

Usage: ![1 0 -1 0 1 0 -1 0]

Saved 4 bytes thanks to Dennis!

This is a fairly straightforward implementation - it uses the fact that the "exponential" part causes a binomial to appear in the solution. Otherwise, it's just solving for the relevant coefficients.

\$\endgroup\$
  • \$\begingroup\$ !v=(b=[1;0v[r=2:end]];for i=r,j=0:i-2 b[i]-=binomial(i-1,j)v[i-j]b[j+1]end;b) saves 4 bytes. \$\endgroup\$ – Dennis Jun 16 '16 at 16:20
  • \$\begingroup\$ Thanks, Dennis. I was using v[n=end] earlier to grab the length, but didn't think to use a full range like that. \$\endgroup\$ – Glen O Jun 16 '16 at 16:26
  • \$\begingroup\$ I think that this answer contradicts your comment that "the processes are completely different". \$\endgroup\$ – Peter Taylor Jun 16 '16 at 18:46

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.