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

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

Links

Robert Israel, Table of n, a(n) for n = 0..10000

Henry Bottomley, Illustration for A067397.

Formula

Let k=floor(log3(n)), i.e., 3^k<=n<3^(k+1): if (3/2)*3^k<n<(5/2)*3^k then a(n)=a(n-3^k)+1, if n=3*3^k-1 then a(n)=a(n-3^k)-1=0, otherwise a(n)=a(n-3^k) [starting with a(0)=0, so a(3^k)=0].

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

Example

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.

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 *)

Prog

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

Crossrefs

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

Sequence in context: A373820 A102679 A025146 * A080586 A152906 A128522

Adjacent sequences: A067394 A067395 A067396 * A067398 A067399 A067400

Keyword

nonn,easy

Author

Henry Bottomley, Jan 22 2002

Status

approved