A000989 -id:A000989 - cp's OEIS frontend

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

Henry Bottomley, Jan 22 2002

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

			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.

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

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

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

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

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

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

A263924 Numbers n such that there is a prime p > 3 and an exponent e such that the central binomial coefficient binomial(2n, n) is divisible by p^e but not by either 2^e or 3^e.

Original entry on oeis.org

64, 256, 272, 324, 513, 514, 516, 544, 1026, 1028, 1032, 1064, 1088, 1089, 1216, 1544, 1552, 1568, 1569, 2052, 2056, 2064, 2188, 2192, 2193, 2194, 2208, 2224, 2244, 2248, 2304, 2313, 2314

Offset: 1

Charles R Greathouse IV, Oct 29 2015

nonn

How quickly does this sequence grow asymptotically?

A263922(a(n)) > max{A000120(a(n)),A000989(an(n))}. - Reinhard Zumkeller, Nov 19 2015

			64 is a member because binomial(128,64) = 2 * 3 * 5^3 * ..., where the exponent 3 of 5 is greater than the exponents 1 and 1 of 2 and 3, respectively.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A263922, A000984, A000120, A000989.

import Math.NumberTheory.Primes.Factorisation (factorise)
a263924 n = a263924_list !! (n-1)
a263924_list = filter f [2..] where
   f x = not (null pe23s) && any ((> e23) . snd) pes' where
         e23 = maximum (map snd pe23s)
         (pe23s, pes') = span ((<= 3) . fst) $ factorise $ a000984 x
-- Reinhard Zumkeller, Nov 01 2015

f(n,p)=my(d=Vecrev(digits(n,p)),c);sum(i=1,#d,c=(2*d[i]+c>=p))
is(n)=my(r=max(hammingweight(n),f(n,3))); forprime(p=5,sqrtnint(n,r+1), if(f(n,p)>r, return(p))); 0

a(n) >> n^1.014. (This is surely not optimal.) - Charles R Greathouse IV, Jan 18 2016

A000999 5-adic valuation of binomial(2n,n): largest k such that 5^k divides binomial(2n, n).

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, R. K. Guy

T. D. Noe, Table of n, a(n) for n = 0..1000
E. E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, Journal für die reine und angewandte Mathematik, Vol. 44 (1852), pp. 93-146; alternative link.
Dorel Miheţ, Legendre's and Kummer's theorems again, Resonance, Vol. 15, No. 12 (2010), pp. 1111-1121; alternative link.
Armin Straub, Victor H. Moll and Tewodros Amdeberhan, The p-adic valuation of k-central binomial coefficients, Acta Arithmetica, Vol. 140, No. 1 (2009), pp. 31-42.
Wikipedia, Kummer's theorem.

Cf. A000984, A000989, A053824, A112765.

Table[IntegerExponent[Binomial[2*n, n], 5], {n, 0, 100}] (* T. D. Noe, Jun 21 2012 *)

a(n)=if(n<0,0,valuation(binomial(2*n,n),5))

a(n) = my(v=digits(n,5),c=0); sum(i=0,#v-1, c=(c+v[#v-i]>=3)); \\ Kevin Ryde, Mar 07 2023

From Amiram Eldar, Feb 12 2021: (Start)
a(n) = A112765(A000984(n)).
a(n) = (2*A053824(n) - A053824(2*n))/4. (End)

More terms from Michael Somos, Jun 27 2002

A082490 Exponent of highest power of 3 dividing sum(0<=k

Original entry on oeis.org

0, 1, 2, 0, 2, 3, 1, 2, 4, 0, 1, 2, 0, 3, 4, 2, 3, 5, 1, 2, 3, 1, 3, 4, 2, 3, 6, 0, 1, 2, 0, 2, 3, 1, 2, 4, 0, 1, 2, 0, 4, 5, 3, 4, 6, 2, 3, 4, 2, 4, 5, 3, 4, 7, 1, 2, 3, 1, 3, 4, 2, 3, 5, 1, 2, 3, 1, 4, 5, 3, 4, 6, 2, 3, 4, 2, 4, 5, 3, 4, 8, 0, 1, 2, 0, 2, 3, 1, 2, 4, 0, 1, 2, 0, 3, 4

Offset: 1

Ralf Stephan, Apr 28 2003

Robert Israel, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
J. Shallit, k-regular Sequences
J. Shallit, Number theory and formal languages, in D. A. Hejhal, J. Friedman, M. C. Gutzwiller and A. M. Odlyzko, eds., Emerging Applications of Number Theory, IMA Volumes in Mathematics and Its Applications, V. 109, Springer-Verlag, 1999, pp. 547-570. (Example 1.)

Cf. A000989, A006134, A007949.

map(t -> padic:-ordp(t,3), ListTools:-PartialSums([seq(binomial(2*n,n),n=0..100)])); # Robert Israel, Mar 27 2018

IntegerExponent[#,3]&/@Accumulate[Table[Binomial[2n,n],{n,0,100}]]

s=0; for(n=1, 150, s=s+binomial(2*n-2, n-1); print1(valuation(s, 3)", "))

a(n) = valuation(n^2 * binomial(2*n, n), 3); \\ Michel Marcus, Mar 27 2018

a(n) = A007949(A006134(n)) = A007949 (n^2 * C(2n, n)) (Allouche, Shallit; Zagier) = 2*A007949(n) + A000989(n).

A324469 Exponent of highest power of 3 that divides multinomial(4*n;n,n,n,n).

Original entry on oeis.org

0, 1, 2, 1, 2, 4, 2, 5, 6, 1, 2, 3, 2, 3, 6, 4, 6, 7, 2, 3, 4, 5, 6, 8, 6, 8, 9, 1, 2, 3, 2, 3, 5, 3, 6, 7, 2, 3, 4, 3, 4, 8, 6, 8, 9, 4, 5, 6, 6, 7, 9, 7, 9, 10, 2, 3, 4, 3, 4, 6, 4, 9, 10, 5, 6, 7, 6, 7, 10, 8, 10, 11, 6, 7, 8, 8, 9, 11, 9, 11, 12, 1, 2

Offset: 0

N. J. A. Sloane, Mar 03 2019

nonn

Amiram Eldar, Table of n, a(n) for n = 0..10000

Analogs for binomial and trinomials: A000989, A053735. See also A324467.

Cf. A007949 (3-adic valuation of n), A008977.

[seq(padic[ordp](combinat[multinomial](4*n, n$4), 3), n=0..128)];

s[n_] := Plus @@ IntegerDigits[n, 3]; a[n_] := 2*s[n] - s[4*n]/2; Array[a, 100, 0] (* Amiram Eldar, Feb 21 2021 *)

a(n) = 2*A000989(n) + A000989(2*n). - Charlie Neder, Mar 09 2019
From Amiram Eldar, Feb 21 2021: (Start)
a(n) = A007949(A008977(n)).
a(n) = 2*A053735(n) - A053735(4*n)/2. (End)

A370662 Numbers m such that 3 does not divide the m-th Catalan number A000108(m); m such that A067397(m) = 0.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 13, 26, 27, 28, 29, 30, 31, 35, 36, 37, 38, 39, 40, 80, 81, 82, 83, 84, 85, 89, 90, 91, 92, 93, 94, 107, 108, 109, 110, 111, 112, 116, 117, 118, 119, 120, 121, 242, 243, 244, 245, 246, 247, 251, 252, 253, 254, 255, 256, 269, 270, 271, 272, 273, 274

Offset: 1

Jianing Song, Feb 24 2024

A number m is a term if and only if m = 3*k-1 (k>0), 3*k or 3*k+1 for k in A005836; see A067397.

Conjecture: the only terms of the form 2^r-1 are 0, 1, 3, 31 and 255. Since 2^r-1 !== 2 (mod 3), this is equivalent to saying that the only numbers of the form 2^r-1 that have no digits 2 in ternary are 0, 1, 3, 31, 255. The conjecture would imply that the n-th Catalan number is divisible by 2 or 3 other than n taking these values.

			11 is a term since that 3 does not divide the 11th Catalan number 58786. Note that 11 = 3*4 - 1, and 4 is in A005836.
31 is a term since that 3 does not divide the 31st Catalan number 14544636039226909. Note that 31 = 3*10 + 1, and 10 is in A005836.

Jianing Song, Table of n, a(n) for n = 1..12287 (all terms < 3^13-1)

Cf. A000108, A067397, A000989, A005836.

a(n) = 3*fromdigits(binary(n\3), 3) + n%3 - 1 \\ adapted from Gheorghe Coserea's program for A005836

def A370662(n):
    a, b = divmod(n,3)
    return 3*int(bin(a)[2:],3)+b-1 # Chai Wah Wu, Feb 29 2024

a(3*k-3) = 3*A005836(k)-1 (k>1), a(3*k-2) = 3*A005836(k), a(3*k-1) = 3*A005836(k)+1.

a(3*2^r-1) = (3^(r+1)-1)/2, a(3*2^r) = 3^(r+1)-1.

Showing 1-6 of 6 results.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A263924 Numbers n such that there is a prime p > 3 and an exponent e such that the central binomial coefficient binomial(2n, n) is divisible by p^e but not by either 2^e or 3^e.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

PARI

Formula

A000999 5-adic valuation of binomial(2*n,n): largest k such that 5^k divides binomial(2*n, n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A082490 Exponent of highest power of 3 dividing sum(0<=k

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A324469 Exponent of highest power of 3 that divides multinomial(4*n;n,n,n,n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A370662 Numbers m such that 3 does not divide the m-th Catalan number A000108(m); m such that A067397(m) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A000999 5-adic valuation of binomial(2n,n): largest k such that 5^k divides binomial(2n, n).