A120626 -id:A120626 - 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

A081399 Bigomega of the n-th Catalan number: a(n) = A001222(A000108(n)).

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 4, 3, 4, 4, 5, 5, 6, 7, 9, 7, 8, 8, 10, 9, 10, 10, 11, 11, 11, 12, 12, 11, 13, 13, 14, 11, 13, 14, 14, 13, 14, 14, 16, 15, 16, 18, 19, 19, 19, 19, 21, 19, 20, 19, 21, 20, 21, 21, 21, 19, 20, 20, 22, 22, 24, 25, 25, 23, 23, 23, 24, 24, 27, 26, 27, 25, 27, 28, 29, 28

Offset: 0

Labos Elemer, Mar 28 2003

It is easy to show that a(n) is between n/log(n) and 2n/log(n) (for n>n0), cf. [Campbell 1984]. The sequence A137687, roughly the middle of this interval, is a fair approximation for A081399. See A137686 for the (signed) difference of the two sequences.

M. F. Hasler, Table of n, a(n) for n = 0..3000.
Douglas M. Campbell, The Computation of Catalan Numbers, Mathematics Magazine, Vol. 57, No. 4. (Sep., 1984), pp. 195-208.

Cf. A001222, A000108, A022559, A023816, A048621, A081405, A120626, A137686-A137687.

Cf. A080405.

with(numtheory):a:=proc(n) if n=0 then 0 else bigomega(binomial(2*n,n)/(1+n)) fi end: seq(a(n), n=0..75); # Zerinvary Lajos, Apr 11 2008

a[n_] := PrimeOmega[ CatalanNumber[n]]; Table[a[n], {n, 0, 75}] (* Jean-François Alcover, Jul 02 2013 *)

A081399(n)=bigomega(prod(i=2,n,(n+i)/i)) \\ M. F. Hasler, Feb 06 2008

a(n)=A001222[A000108(n)]

Edited and extended by M. F. Hasler, Feb 06 2008

A137686 a(n) = Bigomega(Catalan(n)) - round( 3 n /(2 log(n+2))) (= A081399 - A137687).

Original entry on oeis.org

0, -1, -1, -2, -1, -1, 0, -2, -1, -2, -1, -1, -1, 0, 1, -1, 0, -1, 1, 0, 0, 0, 1, 0, 0, 1, 0, -1, 1, 0, 1, -2, -1, 0, 0, -2, -1, -1, 1, -1, 0, 2, 2, 2, 2, 1, 3, 1, 2, 0, 2, 1, 1, 1, 1, -1, -1, -1, 1, 0, 2, 3, 3, 0, 0, 0, 1, 0, 3, 2, 2, 0, 2, 3, 3, 2, 2, 3, 4, 1, 0, 1, 1, 1, 1, 1, 3, 1, 4, 2, 2, 1, 2, 2, 3, 2, 3, 1, 2, 0, 1, 0, 2, 1, 2, 2, 3, 1, 3, 2, 3, 1, 2, 3, 3, 2, 3

Offset: 0

M. F. Hasler, Feb 06 2008

It is easy to show that A081399(n) = bigomega(Catalan(n)) is between n/log(n) and 2n/log(n) (for n>n0). The sequence A137687 is roughly the middle of this interval, which turns out to be a fair approximation to A081399. The present sequence lists the (signed) difference.

M. F. Hasler, Table of n, a(n) for n = 0..3000.
Douglas M. Campbell, The Computation of Catalan Numbers, Mathematics Magazine, Vol. 57, No. 4. (Sep., 1984), pp. 195-208.

Cf. A000108, A081399, A120626, A137687.

A137686(n) = bigomega(prod(i=2,n,(n+i)/i)) - round(3*n/log(n+2)/2)

a(n) = A001222(A000108(n)).

A137687 a(n) = round(3 n / (2 log(n+2))), an approximation to A081399.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 25, 25, 25, 25, 26, 26

Offset: 0

M. F. Hasler, Feb 06 2008

It is easy to show that A081399(n) is between n/log(n) and 2n/log(n) (for n>n0), cf. [Campbell 1984]. This sequence A137687 is roughly the middle of this interval (with log(n) replaced by log(n+2) to be well-defined for all n>=0), which turns out to be a fair (and simple, increasing) approximation for A081399.

See A137686 for the (signed) difference of the two sequences.

M. F. Hasler, Table of n, a(n) for n = 0..3000.
Douglas M. Campbell, The Computation of Catalan Numbers, Mathematics Magazine, Vol. 57, No. 4. (Sep., 1984), pp. 195-208.

Cf. A000108, A001222, A081399, A120626, A137686.

A137687(n) = round(3*n/log(n+2)/2) \\ M. F. Hasler, Feb 06 2008

A375077 Smallest k such that Product_{i=0..n} (k-i) divides C(2k,k).

Original entry on oeis.org

2, 2480, 8178, 45153, 3648841, 7979090, 101130029

Offset: 1

Ralf Stephan, Jul 29 2024

Thomas Bloom, Problem 396, Erdős Problems.

Cf. A000984, A120626, A129489.

for(n=1,20,for(k=n+1,100000,if(binomial(2*k,k)%prod(i=0,n,k-i)==0,print(n," ",k);break)))

from math import prod, comb
def A375077(n):
    a, c, k = prod(n+1-i for i in range(n+1)), comb(n+1<<1,n+1), n+1
    while c%a:
        k += 1
        a = a*k//(k-n-1)
        c = c*((k<<1)-1<<1)//k
    return k # Chai Wah Wu, Jul 30 2024

a(5) from Chai Wah Wu, Aug 01 2024

a(6)-a(7) from Max Alekseyev, Feb 25 2025

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

A081399 Bigomega of the n-th Catalan number: a(n) = A001222(A000108(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A137686 a(n) = Bigomega(Catalan(n)) - round( 3 n /(2 log(n+2))) (= A081399 - A137687).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A137687 a(n) = round(3 n / (2 log(n+2))), an approximation to A081399.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A375077 Smallest k such that Product_{i=0..n} (k-i) divides C(2k,k).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Extensions