7
\$\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\$
9
  • 1
    \$\begingroup\$ When titling your next challenge, you may want to think about this meta.codegolf.stackexchange.com/a/8090/15599 \$\endgroup\$ Jun 15, 2016 at 23:24
  • \$\begingroup\$ Thank you! I have edited it away! I will bear that in mind next time! \$\endgroup\$
    – Leaky Nun
    Jun 15, 2016 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, 2016 at 4:56
  • \$\begingroup\$ @feersum If the input has integer coefficients, then the output will also have integer coefficients. \$\endgroup\$
    – Leaky Nun
    Jun 16, 2016 at 5:22
  • 1
    \$\begingroup\$ Borderline duplicate \$\endgroup\$ Jun 16, 2016 at 10:05

1 Answer 1

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\$
3
  • \$\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, 2016 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, 2016 at 16:26
  • \$\begingroup\$ I think that this answer contradicts your comment that "the processes are completely different". \$\endgroup\$ Jun 16, 2016 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.