A067397 -id:A067397 - cp's OEIS frontend

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

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.

A039969 An example of a d-perfect sequence: a(n) = Catalan(n) mod 3.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

nonn

This is A006996 with all its terms repeated three times, except the initial term only twice. A006996 is a fixed point of the morphism 0 -> 000, 1 -> 120, 2 -> 210. [The original comment edited by Antti Karttunen, Aug 14 2017]
Equals Catalan(n) mod 3. (Cf. A000108.) - Paul D. Hanna, Jun 20 2003 [confirmed by Christian G. Bower, Jun 12 2005]
Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).

Antti Karttunen, Table of n, a(n) for n = 0..10000
Rob Burns, Asymptotic density of Catalan numbers modulo 3 and powers of 2, arXiv:1611.03705 [math.NT], 2016.
David Kohel, San Ling and Chaoping Xing, Explicit Sequence Expansions, in: C. Ding, T. Helleseth and H. Niederreiter (eds.), Sequences and their Applications, Proceedings of SETA'98 (Singapore, 1998), Discrete Mathematics and Theoretical Computer Science, 1999, pp. 308-317; alternative link.
Index entries for sequences that are fixed points of mappings

Cf. A000108, A001006, A010872, A039972, A067397.

Cf. A006996 (trisection).

[Catalan(n) mod 3: n in [1..80]]; // Vincenzo Librandi, Jul 14 2015

seq(binomial(2*n, n)/(n+1) mod 3, n = 0 .. 100); # Robert Israel, Sep 20 2015

Take[ Flatten[ Nest[ Flatten[ # /. {1 -> {1, 2, 0}, 2 -> {2, 1, 0}, 0 -> {0, 0, 0}}] &, {1}, 4] /. {1 -> {1, 1, 1}, 2 -> {2, 2, 2}, 0 -> {0, 0, 0}}], {2, 106}] (* or *)
Table[ Mod[ Binomial[ 2n, n]/(n + 1), 3], {n, 0, 104}] (* Robert G. Wilson v, Sep 09 2005 *)
Mod[CatalanNumber[Range[0,110]],3] (* Harvey P. Dale, Oct 23 2017 *)

A039969(n) = ((binomial(2*n, n)/(n+1))%3); \\ Antti Karttunen, Aug 13 2017

a(n) = ((-1)^(n+1)*A001006(n-1)) mod 3, for n>0. - Christian G. Bower, Jun 12 2005
a(n) = a(n-1) if n == 0 or 1 (mod 3). a(n) = 0 if n == 5,6, or 7 (mod 9). - Robert Israel, Sep 20 2015
a(3n) = A006996(n). - Antti Karttunen, Aug 14 2017
Asymptotic mean: lim_{n->oo} (1/n) Sum_{k=1..n} a(k) = 0 (Burns, 2016). - Amiram Eldar, Jan 26 2021

More terms from Christian G. Bower, Jun 12 2005

Offset corrected from 1 to 0 by Antti Karttunen, Aug 13 2017

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

Original entry on oeis.org

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

Offset: 0

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

a(n) = 0 if and only if n is in A005836. - Charles R Greathouse IV, May 19 2013
sign(a(n+1) - a(n)) is repeat [0, 1, -1]. - Filip Zaludek, Oct 29 2016
By Kummer's theorem, number of carries when adding n + n in base 3. - Robert Israel, Oct 30 2016

Vincenzo Librandi, Table of n, a(n) for n = 0..2000
Michael Gilleland, Some Self-Similar Integer Sequences.
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, A005836, A007949, A053735, A067397.

a000989 = a007949 . a000984  -- Reinhard Zumkeller, Nov 19 2015

f:= proc(n) option remember; local k,m,d;
   k:= floor(log[3](n));
   d:= floor(n/3^k);
   m:= n-d*3^k;
   if d = 2 or 2*m > 3^k then procname(m)+1
   else procname(m)
   fi
end proc:
f(0):= 0:
map(f, [$0..100]); # Robert Israel, Oct 30 2016

p=3; Array[ If[ Mod[ bi=Binomial[ 2#, # ], p ]==0, Select[ FactorInteger[ bi ], Function[ q, q[ [ 1 ] ]==p ], 1 ][ [ 1, 2 ] ], 0 ]&, 27*3, 0 ]
Table[ IntegerExponent[ Binomial[2 n, n], 3], {n, 0, 100}] (* Jean-François Alcover, Feb 15 2016 *)

PARI
```
a(n) = valuation(binomial(2*n, n), 3)
```

a(n)=my(N=2*n,s);while(N\=3,s+=N);while(n\=3,s-=2*n);s \\ Charles R Greathouse IV, May 19 2013

a(n) = Sum_{k>=0} floor(2*n/3^k) - 2*Sum_{k>=0} floor(n/3^k). - Benoit Cloitre, Aug 26 2003
a(n) = A007949(A000984(n)). - Reinhard Zumkeller, Nov 19 2015
From Robert Israel, Oct 30 2016: (Start)
If 2*n < 3^k then a(3^k+n) = a(n).
If n < 3^k < 2*n then a(3^k+n) = a(n)+1.
If n < 3^k then a(2*3^k+n) = a(n)+1. (End)
a(n) = A053735(n) - A053735(2*n)/2. - Amiram Eldar, Feb 12 2021
From Miles Wilson, Jul 06 2025: (Start)
a(n) = A007949(n+1) + A067397(n).
G.f.: Sum_{k>=1} (x^(3^k/2+1/2)-x^(3^k))/((x-1)*(x^(3^k)-1)). (End)

cp's OEIS Frontend

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

A039969 An example of a d-perfect sequence: a(n) = Catalan(n) mod 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

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