cp's OEIS Frontend

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

%I A014847 #113 Feb 16 2025 08:32:33
%S A014847 1,2,6,15,20,28,42,45,66,77,88,91,104,110,126,140,153,156,170,187,190,
%T A014847 204,209,210,220,228,231,238,240,266,276,299,308,312,315,322,325,330,
%U A014847 345,368,378,414,420,429,435,440,442,450,459,460,464,468,476,483,493
%N A014847 Numbers k such that k-th Catalan number C(2k,k)/(k+1) is divisible by k.
%C A014847 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 A014847 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 A014847 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 A014847 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 A014847 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 A014847 The asymptotic density of this sequence is 0.11424743... (Ford and Konyagin, 2021). - _Amiram Eldar_, Jan 26 2021
%H A014847 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 A014847 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 A014847 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 A014847 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 A014847 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 A014847 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 A014847 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DiskLinePicking.html">Disk Line Picking</a>.
%F A014847 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 A014847 a(n) = A004782(n) - 1. - _Enrique Pérez Herrero_, Feb 03 2013
%p A014847 filter:= proc(n) local F, f, r, c, t,j;
%p A014847   F:= ifactors(n)[2];
%p A014847   for f in F do
%p A014847     r:= convert(n,base,f[1]);
%p A014847     c:= 0: t:= 0:
%p A014847     for j from 1 to nops(r) do
%p A014847       if 2*r[j]+c >= f[1] then
%p A014847           c:= 1; t:= t+1;
%p A014847       else c:= 0
%p A014847       fi;
%p A014847     od;
%p A014847     if t < f[2] then return false fi;
%p A014847   od;
%p A014847   true
%p A014847 end proc:
%p A014847 select(filter, [$1..1000]); # _Robert Israel_, Jan 07 2018
%t A014847 fQ[n_] := IntegerQ[Binomial[2n, n]/ n]; Select[ Range@495, fQ@# &] (* _Robert G. Wilson v_, Jun 19 2006 *)
%t A014847 Select[Table[{CatalanNumber[n],n},{n,500}],Divisible[#[[1]],#[[2]]]&][[All,2]] (* _Harvey P. Dale_, Nov 07 2022 *)
%o A014847 (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 A014847 (PARI) for(n=1, 1e3, if(binomial(2*n, n)/(n+1) % n==0, print1(n", "))) \\ _Altug Alkan_, Nov 11 2015
%o A014847 (Python)
%o A014847 from __future__ import division
%o A014847 A014847_list, b = [], 1
%o A014847 for n in range(1,10**3):
%o A014847     if not b % n:
%o A014847         A014847_list.append(n)
%o A014847     b = b*(4*n+2)//(n+2) # _Chai Wah Wu_, Jan 27 2016
%o A014847 (Magma) [n: n in [1..500] | IsZero((Binomial(2*n, n) div (n+1)) mod n)]; // _Vincenzo Librandi_, Jan 29 2016
%Y A014847 Cf. A000108, A000984, A120622, A120623, A120624, A120625, A120626, A121943, A282163, A282346, A283073, A283074, A282672.
%K A014847 nonn
%O A014847 1,2
%A A014847 _N. J. A. Sloane_