A036541 Deficit of central binomial coefficients in terms of number of prime factors: a(n) shows how many fewer prime factors the n-th central binomial coefficient has than n!.

0, 0, 1, 0, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 4, 4, 3, 3, 5, 5, 6, 6, 6, 5, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 8

Offset: 1

Author

Labos Elemer

Keywords

• nonn

Comments

Primes not exceeding n/2 are missing from this kit of prime divisors. Note differences of consecutive deficits change sign like: 0,1,0,-2,0,-1,0,+2,0.

a(2n) = a(2n-1) unless n = 2^k for some k >= 1, in which case a(2n) = a(2n-1)-1. - Robert Israel, May 31 2016

Examples

			a(1000) = PrimePi(1000) - omega(binomial(1000, 500)) = 168 - 116 = 52.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001405, A000720, A034973, A034974.

Programs

Maple

N:= 1000: # to get a(1) .. a(N) G:= proc(p,n) local m,Ln,Lm;
   m:= floor(n/2);
   Ln:= convert(n,base,p);
   Lm:= convert(m,base,p);
   hastype(Ln[1..nops(Lm)]-Lm,negative)
end proc:
S[1]:= {}:
S[2]:= {}:
for n from 3 to N do
  if n::even then
     if n = 2^ilog2(n) then S[n]:= S[n-1] minus {2}
     else S[n]:= S[n-1]
     fi
  else
     S[n]:= (S[n-1] minus select(G,numtheory:-factorset(n),n)) union remove(G,numtheory:-factorset((n+1)/2),n);
  fi;
od:
seq(nops(S[i]),i=1..N); # Robert Israel, May 31 2016

Mathematica

Table[PrimePi@ n - PrimeNu[Binomial[n, Floor[n/2]]], {n, 105}] (* Michael De Vlieger, Jun 01 2016 *)

Formula

a(n) = omega(n!) - omega(binomial(n, floor(n/2))) = PrimePi(n) - omega(binomial(n, floor(n/2))).