15
\$\begingroup\$

Almost every function can be expressed as a polynomial with infinite terms.

For example, e^x = 1 + x + x^2/2! + x^3/3! + x^4/4! + ...

For example, sin(x) = x - x^3/3! + x^5/5! - x^7/7! + ...

The coefficients of the n-th terms form a sequence, and the corresponding function is called the Generating Function of the sequence.

The coefficients of the n-th terms form a sequence.

Often, the n-th term would have a denominator of n!. Therefore, we multiply the coefficient by n! to obtain another sequence, whose Exponential Generating Function would be the original function.

For example, the sequence whose Exponential Generating Function is e^x would be 1,1,1,1,....

For example, the sequence whose Exponential Generating Function is sin(x) would be 0,1,0,-1,0,1,0,-1,....

Task

Your task is to find the n-th term of the sequence whose Exponential Generating Function is tan(x).

Testcases

n result
0 0
1 1
2 0
3 2
4 0
5 16
6 0
7 272
8 0
9 7936
10 0
11 353792
12 0
13 22368256
14 0
15 1903757312
16 0
17 209865342976
18 0
19 29088885112832
20 0
21 4951498053124096
22 0
23 1015423886506852352
24 0
25 246921480190207983616
26 0

(Copied from here.) (Warning: the 0-th term is different)

Example implementation

# copied from https://github.com/Mego/Seriously/blob/v2.0/SeriouslyCommands.py#L16
def memoized(f):
    memo = {}
    def m_fun(*args):
        if args in memo:
            return memo[args]
        else:
            res = f(*args)
            memo[args] = res
            return res
    return m_fun

# copied from https://github.com/Mego/Seriously/blob/v2.0/SeriouslyCommands.py#L169
@memoized
def binomial(n,r):
    if r > n:
        return 0
    elif r==n:
        return 1
    res = 1
    i = 1
    while i<=r:
        res *= (n+1-i)
        res /= i
        i+=1
    return int(res)

# 2*u(n+1) = Sum_{k=0..n} binomial(n, k)*u(k)*u(n-k)
# from A000111
@memoized
def u(n):
    if n<0: return 0
    if n==0: return 1
    if n==1: return 1
    return sum([binomial(n-1,k)*u(k)*u(n-1-k) for k in range(n)])//2     

def t(n):
    if n%2 == 0: return 0
    return u(n)

print('\n'.join([str(x) + ' ' + str(t(x)) for x in range(26)]))

Ideone it!

References

Improve this question
\$\endgroup\$
5
  • 4
    \$\begingroup\$ If you want to learn more about generating functions and their use in math, especially combinatorics and numbertheory I highly recommend this "famous" textbook generatingfunctionology by H. Wilf. \$\endgroup\$
    – flawr
    Commented Jun 15, 2016 at 18:19
  • 5
    \$\begingroup\$ (Can't resist): taken literally, your first sentence is extremely false! \$\endgroup\$
    – Flounderer
    Commented Jun 16, 2016 at 2:27
  • \$\begingroup\$ You have your meaning of "generating function" and "exponential generating function" backwards. $\sin(x)$ is the exponential generating function of the sequence 0,1,0,-1,0,1,0,-1,0,... - it is not the sequence that is the exponential generating function of $\sin(x)$. What you are asking us to do is to code the sequence exponentially generated by $\tan(x)$. \$\endgroup\$
    – Glen O
    Commented Jun 16, 2016 at 6:08
  • \$\begingroup\$ Looks fine, except "This is also called the Generating Function of that function. The coefficients of the n-th terms form a sequence.", which should probably say something like "The coefficients of the n-th terms form a sequence, and the corresponding function is called the Generating Function of the sequence". \$\endgroup\$
    – Glen O
    Commented Jun 16, 2016 at 6:38
  • \$\begingroup\$ @GlenO Edited . \$\endgroup\$
    – Leaky Nun
    Commented Jun 16, 2016 at 6:40

14 Answers 14

Reset to default
10
\$\begingroup\$

CJam (33 32 27 26 23 20 bytes)

2,{ee::*_(@+.+}ri*0=

Online demo

Dissection

This essentially implements the recurrence described by xnor.

2,        e# [0 1] represents the base case f(0,j) = j==1
{         e# Loop...
  ee::*   e#   Multiply each array element by its index
  _(@+.+  e#   Sum the array shifted left and the array shifted right
}ri*      e# ... n times
0=        e# Evaluate at j=0

Or with a rather different approach, for 23 bytes:

ri_1&a{{1$+}*]W%0+}@*0=

Online demo. Thanks to Dennis for 3 bytes.

Dissection

1a         e# Push [1]
{          e# Repeat...
  {1$+}*]  e#   Compute array of partial sums
  W%0+     e#   Reverse and append 0
}qi:A*     e# ... A times, where A is the input value
0=A1&*     e# Result is first element if A odd, and 0 otherwise

Or with a very different approach, for 29 bytes:

qie!Ma-{W\+W+3ew{_$.=1=},!},,

Online demo

Unfortunately a special case is required for input 0.

Dissection

qi            e# Take an integer n from stdin
e!            e#   Compute all permutations of [0 ... n-1]
Ma-           e#   Special-case n=0
{             e#   Filter...
  W\+W+       e#     Prepend and postpend -1
  3ew         e#     Take slices of 3 consecutive elements
  {           e#     Filter...
    _$.=1=    e#       Test whether the middle element is the second largest
  },!         e#     ... and require no matches
},,           e#   ... and count

You may be thinking "WTF?! He's answering the wrong question." If so, that's understandable, but both approaches do indeed give the correct results.

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ In case ot helps, the nightly build on TIO returns an empty array for [WW]3ew. \$\endgroup\$
    – Dennis
    Commented Jun 15, 2016 at 20:35
  • \$\begingroup\$ @Dennis, thanks. However, it turns out that 0 needs to be a special case anyway, because it evaluates to 1. \$\endgroup\$
    – Peter Taylor
    Commented Jun 15, 2016 at 20:40
  • 1
    \$\begingroup\$ One would only think you are answering the wrong question if one has not even clicked on my links. \$\endgroup\$
    – Leaky Nun
    Commented Jun 15, 2016 at 22:46
  • \$\begingroup\$ ri_1&a{{1$+}*]W%0+}@*0= saves 3 bytes. \$\endgroup\$
    – Dennis
    Commented Jun 16, 2016 at 1:57
  • 2
    \$\begingroup\$ @LeakyNun, so that would be everyone then. I saw that list of links and tl;dr. \$\endgroup\$
    – Peter Taylor
    Commented Jun 16, 2016 at 6:34
7
\$\begingroup\$

Julia, 40 38 32 bytes

!n=2(2*4^n-2^n-0^n)abs(zeta(-n))

Input and output is in form of BigFloats. Try it online!

Background

The Maclaurin series of the tangent function satisfies the identity

whenever x lies in its convergence radius, where Bn is a Bernoulli number.

Since B2(n+1) and (-1)n have the same sign, B2n+1 = 0 if n > 0 and B1 = 1/2, we can rewrite the above as follows.

Furthermore, whenever n is a non-negative integer, we have

where ζ denotes the Riemann zeta function.

From this, with the convention 00 = 1, it follows that

which is the formula the implementation uses.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Python, 57 bytes

f=lambda i,j=0:~-j*f(i-1,j-1)-~j*f(i-1,j+1)if i else j==1

Less golfed:

f=lambda i,j=0:j==1 if i==0 else (j-1)*f(i-1,j-1)+(j+1)*f(i-1,j+1)

We can compute the ith coefficient of the exponential generating function by differentiating the tangent function i times and evaluating at 0. Each derivative is a polynomial in tan(x), and its value at 0 is its constant term.

We recursively express the coefficient of tan(x)**j in the ith derivative of tan with the function f(i,j). The recursive expression comes from the relation tan(x)' = 1 + tan(x)**2.

So, the derivative of tan(x)**j is

j*tan(x)**(j-1)*(tan(x)**2+1), or equivalently
j*tan(x)**(j+1) + j*tan(x)**(j-1)

So, the contributors to tan(x)**j in the ith derivative are tan(x)**(j-1) and tan(x)**(j+1) in the (i-1)st derivative, each with coefficient equal to its power. This gives the recursive expression

f(i,j) = (j-1)*f(i-1,j-1) + (j+1)*f(i-1,j+1)

Note that we don't need to exclude negative exponents j because they evaluate to zero anyway and don't contribute because crossing j=0 gives a multiplier of 0.

The base case of i==0 corresponds to tan(x) itself with j==1, and zero coefficients otherwise. The final evaluation happens at the constant term j=0, which is put in as a default value.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ This ports to 20 bytes in CJam. Do you mind if I make that my primary answer, or do you want to port and post it? \$\endgroup\$
    – Peter Taylor
    Commented Jun 16, 2016 at 7:53
  • \$\begingroup\$ You should post it, I don't know CJam. \$\endgroup\$
    – xnor
    Commented Jun 16, 2016 at 20:36
5
\$\begingroup\$

Mathematica, 20 bytes

Tan@x~D~{x,#}/.x->0&

Straight-forward approach. Calculate the nth derivative of tan(x) and evaluate it at x = 0.

Usage

Example

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Haskell, 48 bytes

0%1=1
0%_=0
i%j=sum[k*(i-1)%k|k<-[j+1,j-1]]
(%0)

We can compute the ith coefficient of the exponential generating function by differentiating the tangent function i times and evaluating at 0. Each derivative is a polynomial in tan(x), and the value at 0 is its constant term.

We recursively express the coefficient of tan(x)^j in the ith derivative of tan with the function i%j. The recursive expression comes from the relation tan(x)' = 1 + tan(x)^2.

So, the derivative of tan(x)^j is

j*tan(x)^(j-1)*(tan(x)^2+1), or equivalently
j*tan(x)^(j+1) + j*tan(x)^(j-1)

So, the contributors to tan(x)^j in the ith derivative are tan(x)^(j-1) and tan(x)^(j+1) in the (i-1)st derivative, each with coefficient equal to its power.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 12 11 bytes

Ṛ+\;S
ḂÇ⁸¡Ḣ

Like Peter Taylor's CJam answer, this computes the nth term of Euler's up/down sequence if n is odd and special-cases even n as 0.

Try it online! or verify all test cases.

How it works

ḂÇ⁸¡Ḣ  Main link. Argument: n

Ḃ       Bit; yield n's parity.
 Ç⁸¡    Apply the helper link (Ç) n (⁸) times.
    Ḣ   Head; retrieve the first element of the resulting list.


Ṛ+\;S   Helper link. Argument: A (list or 1/0)

Ṛ       Cast A to list (if necessary) and reverse the result.
 +\     Take the cumulative sum.
   ;S   Append the sum of A.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Sage, 26 bytes

lambda n:tan(x).diff(n)(0)

Like the other solutions in math-oriented languages, this function computes the nth derivative of tan(x) and evaluates it at x = 0.

Try it online

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

J, 15 13 bytes

There is also the builtin t: which calculates the nth coefficient of the exponential generating function of tan(x).

(1&o.%2&o.)t:

Thanks to @Leaky Nun for reminding me of Taylor series adverbs in J which saved 2 bytes.

Alternative for 15 bytes.

3 :'(3&o.d.y)0'

Another approach is to calculate the nth derivative of tan(x) and evaluate it at x = 0.

Note: In J, the amount of memory used by the derivative function d. grows quickly as n passes 10.

Usage

   f =: (1&o.%2&o.)t:
   f 7
272
   (,.f"0) i. 11  NB. Additional commands are just for formatting the output
 0    0
 1    1
 2    0
 3    2
 4    0
 5   16
 6    0
 7  272
 8    0
 9 7936
10    0

Explanation

(1&o.%2&o.)t:  Input: n
(         )    Define a monad (one argument function), call the input y
 1&o.          Get the trig function sin(x) and call it on y
      2&o.     Get the trig function cos(x) and call it on y
     %         Divide sin(y) by cos(y) to get tan(y)
           t:  Get the nth coefficient of the exponential generating series
               for that function and return

3 :'(3&o.d.y)0'  Input: n
3 :'          '  Define a monad (one argument function) with input y
     3&o.        Get the trig function tan(x)
           y     The input n
         d.      Get the nth derivative of tan(x)
             0   Evaluate the nth derivative at x = 0 and return
Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

Julia, 39 37 bytes

!n=(spdiagm((0:n,1:n+1),(1,-1))^n)[2]

Saved 2 bytes thanks to Dennis.

Not the shortest Julia solution (see Dennis's solution), but this one is done purely using derivative logic... in the form of matrices.

Basically, it uses the fact that the derivative of tan(x) is 1+tan(x)^2. So since the derivative of any power of tan(x), say tan(x)^k, is k tan(x)^(k-1) tan(x)' = k tan(x)^(k-1) + k tan(x)^(k+1), we can use a simple matrix power on a matrix with the appropriate values to generate the expansion, with the second row or column (depending on construction) holding the derivatives of tan(x) itself.

So we just need to find the constant in the resulting expression, and that's the first value in the corresponding row or column.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ !n=(spdiagm((0:n,1:n+1),(1,-1))^n)[2] should work. \$\endgroup\$
    – Dennis
    Commented Jun 16, 2016 at 7:37
  • \$\begingroup\$ @Dennis - nice catch. Didn't realise spdiagm would allow that style of construction - tried it with diagm, but of course it didn't work. \$\endgroup\$
    – Glen O
    Commented Jun 16, 2016 at 7:42
2
\$\begingroup\$

JavaScript (ES6), 127 45 bytes

f=(n,m=0)=>n?++m*f(--n,m--)+--m*f(n,m):m-1?0:1

Port of @xnor's solutions.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Haskell, 95 93 bytes

p=product
f n=sum[(-1)^(n`div`2+j+1)*j^n*p[k-j+1..n+1]`div`p[1..n+1-k+j]|k<-[1..n],j<-[0..k]]

It is basically an implementation of the general formula with some minor optimizations.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

MATLAB with Symbolic Toolbox, 84 bytes

n=input('');syms x;c=coeffs(taylor(tan(x),'Order',n+1))*factorial(n);c(end)*mod(n,2)

Example runs:

>> n=input('');syms x;c=coeffs(taylor(tan(x),'Order',n+1))*factorial(n);c(end)*mod(n,2)
7
ans =
272

>> n=input('');syms x;c=coeffs(taylor(tan(x),'Order',n+1))*factorial(n);c(end)*mod(n,2)
8
ans =
0

>> n=input('');syms x;c=coeffs(taylor(tan(x),'Order',n+1))*factorial(n);c(end)*mod(n,2)
9
ans =
7936
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Haskell (too many bytes)

Using only operations on lists and Raymond Manzoni's result:

c n = last $ map numerator $ zipWith (*) (scanl (*) (1) [2,3..]) (intersperse 0 $ foldr (.) id (replicate n (\xs->(xs ++ [(1%(1+2*length xs)) * (sum (zipWith (*) xs (reverse xs)))]))) [1])

Unfortunately, this overflows for modest values of n, as it uses Int values. I will try to fix the problem using Integervalues. Until then, suggestions are welcome.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Axiom, 46 bytes

f(n:NNI):NNI==(n=0=>0;eval(D(tan(x),x,n),x=0))

code for test and results

(32) -> [[i, f(i)] for i in 0..26]
   (32)
   [[0,0], [1,1], [2,0], [3,2], [4,0], [5,16], [6,0], [7,272], [8,0], [9,7936],
    [10,0], [11,353792], [12,0], [13,22368256], [14,0], [15,1903757312],
    [16,0], [17,209865342976], [18,0], [19,29088885112832], [20,0],
    [21,4951498053124096], [22,0], [23,1015423886506852352], [24,0],
    [25,246921480190207983616], [26,0]]
                                       Type: List List NonNegativeInteger
Improve this answer
\$\endgroup\$

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.