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

%I #112 Nov 07 2022 13:55:24

%S 1,2,6,15,20,28,42,45,66,77,88,91,104,110,126,140,153,156,170,187,190,

%T 204,209,210,220,228,231,238,240,266,276,299,308,312,315,322,325,330,

%U 345,368,378,414,420,429,435,440,442,450,459,460,464,468,476,483,493

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

%C 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

%C 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

%C 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

%C 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

%C 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

%C The asymptotic density of this sequence is 0.11424743... (Ford and Konyagin, 2021). - _Amiram Eldar_, Jan 26 2021

%H Franklin T. Adams-Watters and Chai Wah Wu, <a href="/A014847/b014847.txt">Table of n, a(n) for n = 1..10000</a> n=1..1069 (a(n) <= 10000) from Franklin T. Adams-Watters

%H Max Alekseyev, <a href="http://home.gwu.edu/~maxal/gpscripts/">PARI/GP Scripts for Miscellaneous Math Problems</a>, sect. III: Binomial coefficients modulo integers, binomod.gp (V. 1.4, 11/2015).

%H Christian Ballot, <a href="https://www.emis.de/journals/JIS/VOL21/Ballot/ballot30.html">Lucasnomial Fuss-Catalan Numbers and Related Divisibility Questions</a>, J. Int. Seq., Vol. 21 (2018), Article 18.6.5.

%H Kevin Ford and Sergei Konyagin, <a href="https://doi.org/10.1090/tran/8183">Divisibility of the central binomial coefficient binomial(2n, n)</a>, Trans. Amer. Math. Soc., Vol. 374, No. 2 (2021), pp. 923-953; <a href="https://arxiv.org/abs/1909.03903">arXiv preprint</a>, arXiv:1909.03903 [math.NT], 2019-2020.

%H Carl Pomerance, <a href="https://www.jstor.org/stable/10.4169/amer.math.monthly.122.7.636">Divisors of the middle binomial coefficient</a>, The American Mathematical Monthly, Vol. 122, No. 7 (2015), pp. 636-644; <a href="https://math.dartmouth.edu/~carlp/catalan5.pdf">alternative link</a>.

%H Carlo Sanna, <a href="http://dx.doi.org/10.1142/S1793042118500707">Central binomial coefficients divisible by or coprime to their indices</a>, Int. J. Number Theory, Vol. 14, No. 4 (2018), pp. 1135-1141.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DiskLinePicking.html">Disk Line Picking</a>.

%F 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

%F a(n) = A004782(n) - 1. - _Enrique PĂ©rez Herrero_, Feb 03 2013

%p filter:= proc(n) local F, f, r, c, t,j;

%p F:= ifactors(n)[2];

%p for f in F do

%p r:= convert(n,base,f[1]);

%p c:= 0: t:= 0:

%p for j from 1 to nops(r) do

%p if 2*r[j]+c >= f[1] then

%p c:= 1; t:= t+1;

%p else c:= 0

%p fi;

%p od;

%p if t < f[2] then return false fi;

%p od;

%p true

%p end proc:

%p select(filter, [$1..1000]); # _Robert Israel_, Jan 07 2018

%t fQ[n_] := IntegerQ[Binomial[2n, n]/ n]; Select[ Range@495, fQ@# &] (* _Robert G. Wilson v_, Jun 19 2006 *)

%t Select[Table[{CatalanNumber[n],n},{n,500}],Divisible[#[[1]],#[[2]]]&][[All,2]] (* _Harvey P. Dale_, Nov 07 2022 *)

%o (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

%o (PARI) for(n=1, 1e3, if(binomial(2*n, n)/(n+1) % n==0, print1(n", "))) \\ _Altug Alkan_, Nov 11 2015

%o (Python)

%o from __future__ import division

%o A014847_list, b = [], 1

%o for n in range(1,10**3):

%o if not b % n:

%o A014847_list.append(n)

%o b = b*(4*n+2)//(n+2) # _Chai Wah Wu_, Jan 27 2016

%o (Magma) [n: n in [1..500] | IsZero((Binomial(2*n, n) div (n+1)) mod n)]; // _Vincenzo Librandi_, Jan 29 2016

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

%K nonn

%O 1,2

%A _N. J. A. Sloane_