A020475 -id:A020475 - cp's OEIS frontend

A053200 Binomial coefficients C(n,k) reduced modulo n, read by rows; T(0,0)=0 by convention.

0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 2, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 3, 2, 3, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 4, 0, 6, 0, 4, 0, 1, 1, 0, 0, 3, 0, 0, 3, 0, 0, 1, 1, 0, 5, 0, 0, 2, 0, 0, 5, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 6, 4, 3, 0, 0, 0, 3, 4, 6, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Asher Auel, Dec 12 1999

Pascal's triangle read by rows, where row n is read mod n.
A number n is a prime if and only if (1+x)^n == 1+x^n (mod n), i.e., if and only if the n-th row is 1,0,0,...,0,1. This result underlies the proof of Agrawal, Kayal and Saxena that there is a polynomial-time algorithm for primality testing. - N. J. A. Sloane, Feb 20 2004
A020475(n) = number of zeros in n-th row, for n > 0. - Reinhard Zumkeller, Jan 01 2013

			Row 4 = 1 mod 4, 4 mod 4, 6 mod 4, 4 mod 4, 1 mod 4 = 1, 0, 2, 0, 1.
Triangle begins:
  0;
  0,0;
  1,0,1;
  1,0,0,1;
  1,0,2,0,1;
  1,0,0,0,0,1;
  1,0,3,2,3,0,1;
  1,0,0,0,0,0,0,1;
  1,0,4,0,6,0,4,0,1;
  1,0,0,3,0,0,3,0,0,1;
  1,0,5,0,0,2,0,0,5,0,1;
  1,0,0,0,0,0,0,0,0,0,0,1;
  1,0,6,4,3,0,0,0,3,4,6,0,1;
  1,0,0,0,0,0,0,0,0,0,0,0,0,1;

T. D. Noe, Rows n = 0..100 of triangle, flattened
M. Agrawal, N. Kayal & N. Saxena, PRIMES is in P, Annals of Maths., 160:2 (2004), pp. 781-793. [alternate link]
Index entries for triangles and arrays related to Pascal's triangle

Row sums give A053204. Cf. A053201, A053202, A053203, A007318 (Pascal's triangle).
Cf. also A092241.
Cf. A053214 (central terms, apart from initial 1).

a053200 n k = a053200_tabl !! n !! k
a053200_row n = a053200_tabl !! n
a053200_tabl = [0] : zipWith (map . flip mod) [1..] (tail a007318_tabl)
-- Reinhard Zumkeller, Jul 10 2015, Jan 01 2013

f := n -> seriestolist( series( expand( (1+x)^n ) mod n, x, n+1)); # N. J. A. Sloane

Flatten[Join[{0},Table[Mod[Binomial[n,Range[0,n]],n],{n,20}]]] (* Harvey P. Dale, Apr 29 2013 *)

T(n,k)=if(n, binomial(n,k)%n, 0) \\ Charles R Greathouse IV, Feb 07 2017

Corrected by T. D. Noe, Feb 08 2008

Edited by N. J. A. Sloane, Aug 29 2008 at the suggestion of R. J. Mathar

A080383 Number of j (0 <= j <= n) such that the central binomial coefficient C(n,floor(n/2)) = A001405(n) is divisible by C(n,j).

Original entry on oeis.org

1, 2, 3, 4, 3, 6, 3, 6, 3, 6, 3, 6, 7, 10, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 8, 3, 6, 3, 6, 7, 10, 3, 6, 3, 6, 3, 8, 3, 6, 5, 10, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 7, 10, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6, 7, 10, 3, 6, 3, 6, 7, 10, 3, 6, 3, 6, 3, 6, 3, 6, 3, 6

Offset: 0

Labos Elemer, Mar 12 2003

nonn

			For n <= 500 only a few values of a(n) arise: {1,2,3,4,5,6,7,8,10,11,14}.
From _Jon E. Schoenfield_, Sep 15 2019: (Start)
a(n)=1 occurs only at n=0.
a(n)=2 occurs only at n=1.
a(n)=3 occurs for all even n > 0 such that C(n,j) divides C(n,n/2) only at j = 0, n/2, and n. (This is the case for about 4/9 of the first 100000 terms, and there appear to be nearly as many terms for which a(n)=6.)
a(n)=4 occurs only at n=3.
For n <= 100000, the only values of a(n) that occur are 1..16, 18, 19, 22, 23, and 26.
   k | Indices n (up to 100000) at which a(n)=k
  ---+-------------------------------------------------------
   1 | 0
   2 | 1
   3 | 2, 4, 6, 8, 10, 14, 16, 18, 20, 22, 24, ...
   4 | 3
   5 | 40, 176, 208, 480, 736, 928, 1248, 1440, ... (A327430)
   6 | 5, 7, 9, 11, 15, 17, 19, 21, 23, 27, 29, ... (A080384)
   7 | 12, 30, 56, 84, 90, 132, 154, 182, 220, ...  (A080385)
   8 | 25, 37, 169, 199, 201, 241, 397, 433, ...    (A080386)
   9 | 1122, 1218, 5762, 11330, 12322, 15132, ...   (A327431)
  10 | 13, 31, 41, 57, 85, 91, 133, 155, 177, ...   (A080387)
  11 | 420, 920, 1892, 1978, 2444, 2914, 3198, ...
  12 | 1103, 1703, 2863, 7773, 10603, 15133, ...
  13 | 12324, 37444
  14 | 421, 921, 1123, 1893, 1979, 1981, 2445, ...
  15 | 4960, 6956, 13160, 16354, 18542, 24388, ...
  16 | 11289, 16483, 36657, 62653, 89183
  17 |
  18 | 4961, 6957, 12325, 13161, 16355, 18543, ...
  19 | 16356, 88510, 92004
  20 |
  21 |
  22 | 16357, 88511, 90305, 92005
  23 | 90306
  24 |
  25 |
  26 | 90307
(End)

Vaclav Kotesovec, Table of n, a(n) for n = 0..100000 (first 1000 terms from Vincenzo Librandi, terms 1001..9999 from David A. Corneth)

Cf. A001405, A000225, A057977, A022292, A020475, A067348, A042996.
Cf. A327430, A080384, A080385, A080386, A327431, A080387.
Cf. A080393.

[#[j:j in [0..n]| Binomial(n,Floor(n/2)) mod Binomial(n,j) eq 0]:n in [0..100]]; // Marius A. Burtea, Sep 15 2019

Table[Count[Table[IntegerQ[Binomial[n, Floor[n/2]]/Binomial[n, j]], {j, 0, n}], True], {n, 0, 500}] (* adapted by Vincenzo Librandi, Jul 29 2017 *)

a(n) = my(b=binomial(n, n\2)); sum(i=0, n, (b % binomial(n, i)) == 0); \\ Michel Marcus, Jul 29 2017

a(n) = {if(n==0, return(1)); my(bb = binomial(n, n\2), b = n); res = 2 + !(n%2) + 2 * (n>2 && n%2 == 1); for(i = 2, (n-1)\2, res += 2*(bb%b==0); b *= (n + 1 - i) / i); res} \\ David A. Corneth, Jul 29 2017

Edited by Dean Hickerson, Mar 14 2003

Offset corrected by David A. Corneth, Jul 29 2017

A042996 Numbers k such that binomial(k, floor(k/2)) is divisible by k.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 11, 12, 13, 15, 17, 19, 21, 23, 25, 27, 29, 30, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 56, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 84, 85, 87, 89, 90, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121

Offset: 1

Labos Elemer

nonn

All the odd numbers are terms. - Amiram Eldar, Aug 24 2024

			For n = 12, binomial(12,6) = 924 = 12*77 is divisible by 12, so 12 is in the sequence.
For n = 13, binomial(13,6) = 1716 = 13*132 is divisible by 13, so 13 is in the sequence.
From _David A. Corneth_, Apr 22 2018: (Start)
For n = 20, we wonder if 20 = 2^2 * 5 divides binomial(20, 10) = 20! / (10!)^2.
The exponent of 2 in the prime factorization of 20! is 10 + 5 + 2 + 1 = 18.
The exponent of 2 in the prime factorization of 10! is 5 + 2 + 1 = 8.
Therefore, the exponent of 2 in binomial(20, 10) is 18 - 2*8 = 2.
The exponent of 5 in the prime factorization of 20! is 4.
The exponent of 5 in the prime factorization of 10! is 2.
Therefore, exponent of 5 in binomial(20, 10) is 4 - 2*2 = 0.
So binomial(20, 10) is not divisible by 20, and 20 is not in the sequence. (End)

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A001405, A020475, A067315 (complement).

Select[Range[150],Divisible[Binomial[#,Floor[#/2]],#]&] (* Harvey P. Dale, Sep 15 2011 *)

isok(n) = (binomial(n, n\2) % n) == 0; \\ Michel Marcus, Apr 22 2018

A007012 a(n) is number of k for which C(n,k) is not divisible by n.

Original entry on oeis.org

1, 0, 2, 2, 3, 2, 5, 2, 5, 4, 5, 2, 8, 2, 9, 8, 9, 2, 9, 2, 11, 8, 9, 2, 15, 6, 9, 10, 15, 2, 20, 2, 17, 8, 5, 10, 15, 2, 9, 10, 19, 2, 23, 2, 19, 20, 17, 2, 29, 8, 17, 20, 19, 2, 29, 10, 24, 8, 17, 2, 35, 2, 33, 18, 33, 16, 19, 2, 11, 20, 27, 2, 33, 2, 9, 30, 19, 16, 41, 2, 31, 28, 9, 2, 32, 16

Offset: 0

N. J. A. Sloane

nonn

The number of nonzero terms in the polynomial (1+x)^n (mod n). Note that n is prime iff a(n)=2. - T. D. Noe, Feb 23 2006

For n > 0: a(n) = number of terms > 0 in n-th row of triangle A053200. - Reinhard Zumkeller, Jan 24 2014

J. H. Conway, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000

Cf. A020475, A053200.

a007012 n = a007012_list !! n
a007012_list = 1 : map (sum . map signum) (tail a053200_tabl)
-- Reinhard Zumkeller, Jan 24 2014

Prepend[ Array[ Length[ Select[ Table[ Binomial[ #, k ]/#, {k, 0, #} ], !IntegerQ[ # ]& ] ]&, 100 ], 1 ]

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

A042970 a(n) = binomial(n, floor(n/2)) mod n.

Original entry on oeis.org

0, 0, 0, 2, 0, 2, 0, 6, 0, 2, 0, 0, 0, 2, 0, 6, 0, 2, 0, 16, 0, 2, 0, 4, 0, 2, 0, 20, 0, 0, 0, 6, 0, 2, 0, 24, 0, 2, 0, 20, 0, 6, 0, 28, 0, 2, 0, 12, 0, 2, 0, 32, 0, 20, 0, 0, 0, 2, 0, 4, 0, 2, 0, 6, 0, 42, 0, 40, 0, 42, 0, 52, 0, 2, 0, 44, 0, 20, 0, 20, 0, 2, 0, 0, 0, 2, 0, 48, 0, 0, 0, 52, 0, 2, 0

Offset: 1

Labos Elemer

Value 924 occurs for 248 times among the first 20000 terms (see the horizontal stripe near y=1000 in the scatter plot). Where does it originate from? - Antti Karttunen, Feb 13 2019

			a(10) = binomial(10,5) mod 10 = 252 mod 10 = 2.

Antti Karttunen, Table of n, a(n) for n = 1..20000

Cf. A001405, A020475.

[Binomial(n, Floor(n/2)) mod n: n in [1..110]]; // G. C. Greubel, Feb 17 2019

a:=n->modp(binomial(n,floor(n/2)),n): seq(a(n),n=1..110); # Muniru A Asiru, Feb 17 2019

Table[Mod[Binomial[n, Floor[n/2]], n], {n,1,110}] (* G. C. Greubel, Feb 17 2019 *)

a(n) = binomial(n, n\2) % n; \\ Michel Marcus, May 14 2018

[mod(binomial(n,floor(n/2)), n) for n in (1..110)] # G. C. Greubel, Feb 17 2019

Name corrected by Jon E. Schoenfield, May 13 2018

A048618 Even numbers n such that binomial(n,n/2) is divisible by n/2.

Original entry on oeis.org

2, 4, 12, 30, 40, 56, 84, 90, 132, 154, 176, 182, 208, 220, 252, 280, 306, 312, 340, 374, 380, 408, 418, 420, 440, 456, 462, 476, 480, 532, 552, 598, 616, 624, 630, 644, 650, 660, 690, 736, 756, 828, 840, 858, 870, 880, 884, 900, 918, 920, 928, 936, 952, 966

Offset: 1

Labos Elemer

nonn

			For n=30, binomial(30,15) = 155117520 = 15^10341168, so 30 is a term.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
M. Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems, sect. III: Binomial coefficients modulo integers, binomod.gp (V. 1.4, 11/2015).

Cf. A001405, A020475, A014847, A067348 (binomial(2*n,n) is divisible by 2*n).

a:=[];
for n from 1 to 1000 do if ( binomial(2*n,n) mod n ) = 0 then a:=[op(a),2*n]; fi; od;
a;   # N. J. A. Sloane, Aug 03 2017

Select[Range[2,1000,2],Mod[Binomial[#,#/2],#/2]==0&] (* Harvey P. Dale, Jan 23 2025 *)

a(n) = 2 * A014847(n). - Rémy Sigrist, Aug 27 2017

Definition corrected by N. J. A. Sloane, Aug 03 2017

A159335 Triangle read by rows: numerator of n/binomial(n,m).

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 3, 1, 1, 3, 4, 1, 2, 1, 4, 5, 1, 1, 1, 1, 5, 6, 1, 2, 3, 2, 1, 6, 7, 1, 1, 1, 1, 1, 1, 7, 8, 1, 2, 1, 4, 1, 2, 1, 8, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 10, 1, 2, 1, 1, 5, 1, 1, 2, 1, 10, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 12, 1, 2, 3, 4, 1, 1, 1, 4, 3, 2, 1, 12, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13

Offset: 0

Leroy Quet, Apr 10 2009

This triangle first differs from A109004 (read as a triangle) at T(10, 4) and T(10,6).

T(n,m) is the smallest positive integer such that binomial(n,m)*T(n,m) is a multiple of n.

			Row 10 of Pascal's triangle is: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1. {a(10,m)} of this sequence (A159335) is: 10, 1, 2, 1, 1, 5, 1, 1, 2, 1,10. Multiplying the corresponding integers, we get multiples of 10: 1*10=10,10*1=10, 45*2=90, 120*1=120, 210*1=210, 252*5=1260, 210*1=210, 120*1=120, 45*2=90, 10*1=10, 1*10=10.

G. C. Greubel, Rows n=0..100 of triangle, flattened

Cf. A165661 (denominators), A007318, A020475, A109004.

/* As triangle */ [[n/GCD(n,Binomial(n, k)): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Jun 25 2018

Table[n/GCD[n, Binomial[n, k]], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, Jun 25 2018 *)

for(n=0, 10, for(k=0,n, print1(n/gcd(n, binomial(n,k)), ", "))) \\ G. C. Greubel, Jun 25 2018

T(n,m) = n/gcd(n,binomial(n,m)).

Extended by Ray Chandler, Jun 19 2009

Edited by Franklin T. Adams-Watters, Sep 24 2009

A158871 Those positive integers m where (the number of integers k, 0 <= k <= m, where the binomial coefficient C(m,k) is divisible by m) > (the number of positive integers <= m and coprime to m).

Original entry on oeis.org

1, 10, 12, 18, 20, 21, 22, 24, 26, 28, 30, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 52, 54, 55, 56, 57, 58, 60, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 84, 85, 86, 87, 88, 90, 92, 93, 94, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114

Offset: 1

Leroy Quet, Mar 28 2009

nonn

Also numbers m such that A020475(m) > A000010(m).
A020475(n) = the number of integers k, 0 <= k <= n, where the binomial coefficient C(n,k) is divisible by n.
A000010(n) = the number of positive integers <= n and coprime to n.
A020475(n) >= A000010(n) for all positive integers n.

			From _David A. Corneth_, May 04 2025: (Start)
12 is in the sequence since 12 | binomial(12, k) for k in {1, 5, 6, 7, 11}. Those are five numbers. A000010(12) = 4 and 5 > 4.
16 is not in the sequence as 16 | binomial(16, k) for k in {1, 3, 5, 7, 9, 11, 13, 15}. Those are 8 numbers. A000010(16) = 8. Those are the same numbers. (End)

David A. Corneth, Table of n, a(n) for n = 1..10000

Cf. A000010, A020475.

Extended by R. J. Mathar, May 21 2009

cp's OEIS Frontend

A053200 Binomial coefficients C(n,k) reduced modulo n, read by rows; T(0,0)=0 by convention.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Extensions

A080383 Number of j (0 <= j <= n) such that the central binomial coefficient C(n,floor(n/2)) = A001405(n) is divisible by C(n,j).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Extensions

A042996 Numbers k such that binomial(k, floor(k/2)) is divisible by k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A007012 a(n) is number of k for which C(n,k) is not divisible by n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A042970 a(n) = binomial(n, floor(n/2)) mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Extensions

A048618 Even numbers n such that binomial(n,n/2) is divisible by n/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A159335 Triangle read by rows: numerator of n/binomial(n,m).

Views