A020475 a(n) is the number of k for which binomial(n,k) is divisible by n.

0, 2, 1, 2, 2, 4, 2, 6, 4, 6, 6, 10, 5, 12, 6, 8, 8, 16, 10, 18, 10, 14, 14, 22, 10, 20, 18, 18, 14, 28, 11, 30, 16, 26, 30, 26, 22, 36, 30, 30, 22, 40, 20, 42, 26, 26, 30, 46, 20, 42, 34, 32, 34, 52, 26, 46, 33, 50, 42, 58, 26, 60, 30, 46, 32, 50, 48, 66, 58, 50, 44, 70, 40, 72, 66, 46, 58

Offset: 0

Author

David W. Wilson

Keywords

• nonn

Comments

Note that n is prime iff a(n) = n-1. - T. D. Noe, Feb 23 2006

a(n) >= phi(n) (cf. Robbins). - Michel Marcus, Oct 31 2012

For n > 0: number of zeros in n-th row of A053200. - Reinhard Zumkeller, Jan 01 2013

binomial(n, k) / binomial(n, k-1) = k / (n - k + 1) which eases computation. - David A. Corneth, May 04 2025

Examples

			From _David A. Corneth_, May 04 2025: (Start)
a(6) = 2 as binomial(6, k) = 1, 6, 15, 20, 15, 6, 1 for k = 0 through 6 respectively. Among these, a(6) = 2 numbers are divisible by 6.
a(12) = 5. We start at 1 and know that 12 = 2^2 * 3^1 and so the valuation of 2 and 3 are 2 and 1 respectively.
We compute binomial(n, k) / binomial(n, k-1) = k / (n - k + 1) for k = 1 through floor((n-1)/2) = 3 and keep track the valuation of 2 and 3 of binomial(n, k) via this telescoping product.
We get (2, 1), (1, 1), (2, 0), (0, 2), (3, 2). Of them (2, 1) and (3, 2) indicate divisibility by 12 so that's two numbers and four via symmetry. For binomial(12, 6) we get (2, 1) which as symmetry doesn't give two solutions only counts towards one value of k. This gives a total 4+1 = 5 for a(12). (End)
		

Links

• David A. Corneth, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
• H. Harborth, Divisibility of binomial coefficients by their row number, The American Mathematical Monthly, Vol. 84, No. 1 (Jan., 1977), pp. 35-37.
• N. Robbins, On the number of binomial coefficients which are divisible by their row number, Canad. Math. Bull. 25(1982), 363-365.
• N. Robbins, On the number of binomial coefficients which are divisible by their row number. II, Canad. Math. Bull. 28(1985), 481-486.
• David A. Corneth, PARI program

Crossrefs

Cf. A007012.

Programs

Haskell

a020475 n = a020475_list !! n
a020475_list = 0 : map (sum . map (0 ^)) (tail a053200_tabl)
-- Reinhard Zumkeller, Jan 24 2014

Mathematica

Table[cnt=0; Do[If[Mod[Binomial[n,k],n]==0, cnt++ ], {k,0,n}]; cnt,{n,0,100}] (* T. D. Noe, Feb 23 2006 *)
Join[{0},Table[Count[Table[Binomial[n,k],{k,0,n}],?(Mod[#,n]==0&)],{n,100}]] (* _Harvey P. Dale, Sep 20 2024 *)

PARI

apply( A020475(n)=sum(k=0,n, binomial(n,k)%n==0), [1..30]) \\ M. F. Hasler, May 04 2025

PARI

\\ See Corneth link

Formula

a(n) = n + 1 - A007012(n). - T. D. Noe, Feb 23 2006

Extensions

More terms from T. D. Noe, Feb 23 2006