A282163 -id:A282163 - cp's OEIS frontend

A014847 Numbers k such that k-th Catalan number C(2k,k)/(k+1) is divisible by k.

1, 2, 6, 15, 20, 28, 42, 45, 66, 77, 88, 91, 104, 110, 126, 140, 153, 156, 170, 187, 190, 204, 209, 210, 220, 228, 231, 238, 240, 266, 276, 299, 308, 312, 315, 322, 325, 330, 345, 368, 378, 414, 420, 429, 435, 440, 442, 450, 459, 460, 464, 468, 476, 483, 493

Offset: 1

N. J. A. Sloane

nonn

The sequence does not contain any odd primes p (follows by quadratic reciprocity and field structure of Z/pZ). Aside from the first 2 terms, all other terms are composite integers. - Thomas M. Bridge, Nov 03 2013
Equivalently, numbers such that binomial(2n, n) = 0 (mod n). Indices of zeros in A059288. See A260640 (and A260636) for the analogs for 3n. - M. F. Hasler, Nov 11 2015
The 2nd comment is true because gcd(n,n+1) = 1 and n+1 divides C(2n,n). The 1st comment then follows, because prime p does not divide C(2p,p) = 2p*(2p-1)*...*(p+1)/(p*(p-1)*...*1) unless p = 2. - Jonathan Sondow, Jan 07 2018
A number n is in the sequence if and only if, for each prime p dividing n, the number of carries in the addition n+n in base p is at least the p-adic valuation of n. In particular, if n is squarefree, the condition is that at least one base-p digit of n is at least p/2. - Robert Israel, Jan 07 2018
If A is the set of all a(k)'s, Pomerance proved that the upper density of A is at most 1 - log 2 = 0.30685... and conjectured that A has positive lower density. I improved Pomerance's result by showing that the upper density of A is at most 1 - log 2 - 0.05551 = 0.25134... Numerically, this upper density seems to be less than 0.11. - Carlo Sanna, Jan 28 2018
The asymptotic density of this sequence is 0.11424743... (Ford and Konyagin, 2021). - Amiram Eldar, Jan 26 2021

Franklin T. Adams-Watters and Chai Wah Wu, Table of n, a(n) for n = 1..10000 n=1..1069 (a(n) <= 10000) from Franklin T. Adams-Watters
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems, sect. III: Binomial coefficients modulo integers, binomod.gp (V. 1.4, 11/2015).
Christian Ballot, Lucasnomial Fuss-Catalan Numbers and Related Divisibility Questions, J. Int. Seq., Vol. 21 (2018), Article 18.6.5.
Kevin Ford and Sergei Konyagin, Divisibility of the central binomial coefficient binomial(2n, n), Trans. Amer. Math. Soc., Vol. 374, No. 2 (2021), pp. 923-953; arXiv preprint, arXiv:1909.03903 [math.NT], 2019-2020.
Carl Pomerance, Divisors of the middle binomial coefficient, The American Mathematical Monthly, Vol. 122, No. 7 (2015), pp. 636-644; alternative link.
Carlo Sanna, Central binomial coefficients divisible by or coprime to their indices, Int. J. Number Theory, Vol. 14, No. 4 (2018), pp. 1135-1141.
Eric Weisstein's World of Mathematics, Disk Line Picking.

Cf. A000108, A000984, A120622, A120623, A120624, A120625, A120626, A121943, A282163, A282346, A283073, A283074, A282672.

[n: n in [1..500] | IsZero((Binomial(2*n, n) div (n+1)) mod n)]; // Vincenzo Librandi, Jan 29 2016

filter:= proc(n) local F, f, r, c, t,j;
  F:= ifactors(n)[2];
  for f in F do
    r:= convert(n,base,f[1]);
    c:= 0: t:= 0:
    for j from 1 to nops(r) do
      if 2*r[j]+c >= f[1] then
          c:= 1; t:= t+1;
      else c:= 0
      fi;
    od;
    if t < f[2] then return false fi;
  od;
  true
end proc:
select(filter, [$1..1000]); # Robert Israel, Jan 07 2018

fQ[n_] := IntegerQ[Binomial[2n, n]/ n]; Select[ Range@495, fQ@# &] (* Robert G. Wilson v, Jun 19 2006 *)
Select[Table[{CatalanNumber[n],n},{n,500}],Divisible[#[[1]],#[[2]]]&][[All,2]] (* Harvey P. Dale, Nov 07 2022 *)

is_A014847(n)=!binomod(2*n,n,n) \\ Suitable for large n. Using binomod.gp by M. Alekseyev, cf. links. - M. F. Hasler, Nov 11 2015

for(n=1, 1e3, if(binomial(2*n, n)/(n+1) % n==0, print1(n", "))) \\ Altug Alkan, Nov 11 2015

from _future_ import division
A014847_list, b = [], 1
for n in range(1,10**3):
    if not b % n:
        A014847_list.append(n)
    b = b*(4*n+2)//(n+2) # Chai Wah Wu, Jan 27 2016

It seems that a(n)/n is bounded and more precisely that lim_{n -> infinity} a(n)/n = C exists with 9 <= c < 10. - Benoit Cloitre, Aug 13 2002

a(n) = A004782(n) - 1. - Enrique Pérez Herrero, Feb 03 2013

A121943 Numbers k such that the central binomial coefficient C(2k,k) is divisible by k^2.

Original entry on oeis.org

1, 924, 1287, 2002, 2145, 3366, 3640, 3740, 4199, 6006, 6118, 6552, 7480, 7920, 8580, 8855, 10465, 10920, 11385, 11592, 12285, 12325, 12441, 12540, 12597, 12920, 13224, 13398, 13566, 15080, 15834, 18270, 18354, 18837, 18972, 19227, 23562, 23870, 25641, 25740

Offset: 1

Tanya Khovanova, Sep 03 2006

nonn

Equivalently, numbers n such that the n-th Catalan number C(2n,n)/(n+1) is divisible by n^2. - Lucian Craciun, Feb 09 2017

The asymptotic density of this sequence is 0.00322778... (Ford and Konyagin, 2021). - Amiram Eldar, Jan 26 2021

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Kevin Ford and Sergei Konyagin, Divisibility of the central binomial coefficient binomial(2n, n), Trans. Amer. Math. Soc., Vol. 374, No. 2 (2021), pp. 923-953; arXiv preprint, arXiv:1909.03903 [math.NT], 2019-2020.

Cf. A000108, A000984, A014847, A282163, A282346, A283073, A283074, A282672.

Select[Table[n, {n, 20000}], IntegerQ[Binomial[2#, # ]/#^2] &]

lista(nn) = {for(n=1, nn, if(Mod(binomial(2*n, n), n^2) == 0, print1(n, ", ")));} \\ Altug Alkan, Mar 27 2016

from _future_ import division
A121943_list, b = [], 2
for n in range(1,10**5):
    if not b % (n**2):
        A121943_list.append(n)
    b = b*(4*n+2)//(n+1) # Chai Wah Wu, Mar 27 2016

A282672 Numbers k such that the central binomial coefficient C(2*k,k) is divisible by k^6.

Original entry on oeis.org

1, 1138842118714300, 1605078397568386, 1785922862964240, 1878157384495600, 2020105305316098, 2055406015517400, 2071857393746595, 2310442996851990, 2450253379658700, 2513216312053944, 2966830431558840, 2990886595291870, 3228082757486928, 3318987930069240

Offset: 1

Giovanni Resta, Mar 16 2017

nonn

Also numbers k such that the k-th Catalan number C(2*k,k)/(k+1) is divisible by k^6.

The asymptotic density of this sequence is 3.40390904801... *10^(-13) (Ford and Konyagin, 2021). - Amiram Eldar, Jan 26 2021

			Let E(n,p) be the exponent of the prime p in the factorization of n. Note that E(n!,p) can be easily found with Legendre's formula without computing n!. Then, t = 1138842118714300 is in the sequence because for each prime p dividing t we have E(C(2*t,t),p) = E((2*t)!,p) - 2*E(t!,p) >= 6*E(t,p).

Giovanni Resta, Table of n, a(n) for n = 1..97
Kevin Ford and Sergei Konyagin, Divisibility of the central binomial coefficient binomial(2n, n), Trans. Amer. Math. Soc., Vol. 374, No. 2 (2021), pp. 923-953; arXiv preprint, arXiv:1909.03903 [math.NT], 2019-2020.

Cf. A000108, A000984, A014847, A121943, A282163, A282346, A283073, A283074.

A283073 Numbers k such that the central binomial coefficient C(2*k,k) is divisible by k^4.

Original entry on oeis.org

1, 227736432, 338956200, 386160984, 482213160, 544508118, 548823405, 715592220, 726922482, 731987190, 1427877360, 1448431600, 1467104760, 1490842353, 1491241258, 1504640335, 1646570115, 1852712100, 1923506200, 1923927460, 1924947570, 2056580995, 2064409413

Offset: 1

Lucian Craciun, Feb 28 2017

nonn

Equivalently, numbers k such that the k-th Catalan number C(2*k,k)/(k+1) is divisible by k^4.

The asymptotic density of this sequence is 1.330129946... * 10^(-7) (Ford and Konyagin, 2021). - Amiram Eldar, Jan 26 2021

			The central binomial coefficient C(2*227736432,227736432) is divisible by 227736432^4.

Giovanni Resta, Table of n, a(n) for n = 1..1002
Kevin Ford and Sergei Konyagin, Divisibility of the central binomial coefficient binomial(2n, n), Trans. Amer. Math. Soc., Vol. 374, No. 2 (2021), pp. 923-953; arXiv preprint, arXiv:1909.03903 [math.NT], 2019-2020.
Wikipedia Mathematics Reference Desk, n^4 Divides Central Binomial Coefficient.

Cf. A000108, A000984, A014847, A121943, A282163, A282346, A283074, A282672.

A283073:={}; k:=4; For[n:=1, n<=10^9, n++, {f=FactorInteger[n], For[j:=1, j<=Length[f], j++, {b=True, If[Sum[Floor[2n/f[[j, 1]]^i]-2 Floor[n/f[[j, 1]]^i], {i, 1, Length[IntegerDigits[2n, f[[j, 1]]]]}]A283073=Append[A283073, n]]}] (* Legendre's formula for drastic time reduction *)

a(11)-a(22) from Giovanni Resta, Feb 28 2017

A283074 Numbers k such that the central binomial coefficient C(2*k,k) is divisible by k^5.

Original entry on oeis.org

1, 84331608790, 94482127740, 164273806200, 438726722148, 541278246600, 549361342530, 808172086449, 912226745430, 959218287720, 1017676553985, 1017868271175, 1078659050256, 1286556180525, 1418394308100, 1475851476960, 1489765799610, 1535790227400, 1562434592400, 1642639268270

Offset: 1

Lucian Craciun, Feb 28 2017

nonn

Equivalently, numbers k such that the k-th Catalan number C(2*k,k)/(k+1) is divisible by k^5.

The asymptotic density of this sequence is 2.83248121476... * 10^(-10) (Ford and Konyagin, 2021). - Amiram Eldar, Jan 26 2021

			The central binomial coefficient C(2*84331608790,84331608790) is divisible by 84331608790^5.

Giovanni Resta, Table of n, a(n) for n = 1..123 (terms < 10^13).
Kevin Ford and Sergei Konyagin, Divisibility of the central binomial coefficient binomial(2n, n), Trans. Amer. Math. Soc., Vol. 374, No. 2 (2021), pp. 923-953; arXiv preprint, arXiv:1909.03903 [math.NT], 2019-2020.

Cf. A000108, A000984, A014847, A121943, A282163, A282346, A283073, A282672.

a(3)-a(20) from Giovanni Resta, Mar 03 2017

A282346 Least number m > 1 such that the central binomial coefficient C(2m,m) is divisible by m^n.

Original entry on oeis.org

2, 924, 154836, 227736432, 84331608790, 1138842118714300

Offset: 1

Lucian Craciun and Robert G. Wilson v, Feb 12 2017

Equivalently, least number m > 1 such that the m-th Catalan number C(2m,m)/(m+1) is divisible by m^n. - Lucian Craciun, Mar 01 2017
a(6) <= 4380346834858680. - David A. Corneth, Mar 04 2017
a(7) <= 2404760413443713325. - Giovanni Resta, Mar 16 2017

Wikipedia, Kummer's theorem.

Cf. A000108, A000984, A014847, A121943, A282163, A283073, A283074, A282672.

f[n_] := Block[{k = 2}, While[Mod[Binomial[2k, k], k^n] > 0, k++]; k]

a(4)-a(5) from Giovanni Resta, Feb 23 2017

a(6) from Giovanni Resta, Mar 15 2017

cp's OEIS Frontend

A014847 Numbers k such that k-th Catalan number C(2k,k)/(k+1) is divisible by k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A121943 Numbers k such that the central binomial coefficient C(2k,k) is divisible by k^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

A282672 Numbers k such that the central binomial coefficient C(2*k,k) is divisible by k^6.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A283073 Numbers k such that the central binomial coefficient C(2*k,k) is divisible by k^4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A283074 Numbers k such that the central binomial coefficient C(2*k,k) is divisible by k^5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A282346 Least number m > 1 such that the central binomial coefficient C(2m,m) is divisible by m^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions