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

Comments

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

Links

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.

Formula

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

Maple

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

Mathematica

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

Prog

(PARI) 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
(PARI) for(n=1, 1e3, if(binomial(2*n, n)/(n+1) % n==0, print1(n", "))) \\ Altug Alkan, Nov 11 2015
(Python)
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
(Magma) [n: n in [1..500] | IsZero((Binomial(2*n, n) div (n+1)) mod n)]; // Vincenzo Librandi, Jan 29 2016

Crossrefs

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

Sequence in context: A294942 A227307 A129631 * A013636 A144653 A276782

Adjacent sequences: A014844 A014845 A014846 * A014848 A014849 A014850

Keyword

nonn

Author

N. J. A. Sloane

Status

approved