# Golf the Sequence whose Exponential Generating Function is tangent

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,....

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

• 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. – flawr Jun 15 '16 at 18:19
• (Can't resist): taken literally, your first sentence is extremely false! – Flounderer Jun 16 '16 at 2:27
• 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)$. – Glen O Jun 16 '16 at 6:08
• 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". – Glen O Jun 16 '16 at 6:38
• @GlenO Edited . – Leaky Nun Jun 16 '16 at 6:40

## 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.

• In case ot helps, the nightly build on TIO returns an empty array for [WW]3ew. – Dennis Jun 15 '16 at 20:35
• @Dennis, thanks. However, it turns out that 0 needs to be a special case anyway, because it evaluates to 1. – Peter Taylor Jun 15 '16 at 20:40
• One would only think you are answering the wrong question if one has not even clicked on my links. – Leaky Nun Jun 15 '16 at 22:46
• ri_1&a{{1$+}*]W%0+}@*0= saves 3 bytes. – Dennis Jun 16 '16 at 1:57 • @LeakyNun, so that would be everyone then. I saw that list of links and tl;dr. – Peter Taylor Jun 16 '16 at 6:34 # Julia, 4038 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. ## 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. • 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? – Peter Taylor Jun 16 '16 at 7:53 • You should post it, I don't know CJam. – xnor Jun 16 '16 at 20:36 # 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 ## 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. # 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. ### 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.  ## 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 # 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  # 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. • !n=(spdiagm((0:n,1:n+1),(1,-1))^n)[2] should work. – Dennis Jun 16 '16 at 7:37 • @Dennis - nice catch. Didn't realise spdiagm would allow that style of construction - tried it with diagm, but of course it didn't work. – Glen O Jun 16 '16 at 7:42 ## 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. # Haskell, 95 93 bytes p=product f n=sum[(-1)^(ndiv2+j+1)*j^n*p[k-j+1..n+1]divp[1..n+1-k+j]|k<-[1..n],j<-[0..k]]  It is basically an implementation of the general formula with some minor optimizations. # 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  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.

# 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