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