A067397 Maximal power of 3 that divides n-th Catalan number.

0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2

Offset: 0

Author

Henry Bottomley, Jan 22 2002

Keywords

• nonn
• easy

Comments

Let v(n) = A007949(n) be the 3-adic valuation of n. For n == 0 or 1 (mod 3), we have a(n) = v(binomial(2*n,n)/(n+1)) = v(binomial(2*n,n)) = A000989(n), so a(n) = 0 if and only if n is in A005836. For n == 0 or 2 (mod 3), we have a(n) = v(binomial(2*n+2,n+1)/(4*n+2)) = v(binomial(2*n+2,n+1)) = A000989(n+1), so a(n) = 0 if and only if n+1 is in A005836. In other words, the indices of 0 are precisely numbers of the form 3*k-1 (k>0), 3*k or 3*k+1 for k in A005836. - Jianing Song, Feb 29 2024

Examples

			a(13)=0 since Catalan(13)=742900, which is not divisible by 3; a(14)=2 since Catalan(14)=2674440, which is divisible by 9 but not by 27.
		

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• Henry Bottomley, Illustration for A067397.

Crossrefs

Cf. A000989, A007949, A000108, A048881, A053735.

Programs

Maple

ListTools:-PartialSums([seq(padic:-ordp((2*n-1)/(n+1),3),n=0..100)]); # Robert Israel, Sep 20 2015

Mathematica

f[n_] := Block[{p = FactorInteger@ n}, Take[Last /@ p, Flatten@ Position[First /@ p, 3]]]; Table[f[(2 n)!/n!/(n + 1)!], {n, 104}] /. {} -> 0 // Flatten (* Michael De Vlieger, Sep 21 2015 *)
IntegerExponent[#,3]&/@CatalanNumber[Range[0,110]] (* Harvey P. Dale, Oct 09 2015 *)

PARI

a(n) = (sumdigits(n,3) + sumdigits(n+1,3) - sumdigits(2*n,3) - 1)/2 \\ Jianing Song, Feb 24 2024

Formula

Let k=floor(log3(n)), i.e., 3^k<=n<3^(k+1): if (3/2)*3^k

G.f.: Sum_{k>=1} (x^((3^k+1)/2) - x^(3^k-1))/((1-x^(3^k))*(1-x)). - Robert Israel, Sep 20 2015

a(n) = A000989(n) - A007949(n+1). - Amiram Eldar, Feb 21 2021

a(n) = A007949((2n)!) - A007949(n!) - A007949((n+1)!) = (A053735(n) + A053735(n+1) - A053735(2n) - 1)/2. - Jianing Song, Feb 24 2024

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.