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

%I #34 Oct 27 2023 22:00:45

%S 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,

%T 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,

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

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

%C Pascal's triangle read by rows, where row n is read mod n.

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

%C A020475(n) = number of zeros in n-th row, for n > 0. - _Reinhard Zumkeller_, Jan 01 2013

%H T. D. Noe, <a href="/A053200/b053200.txt">Rows n = 0..100 of triangle, flattened</a>

%H M. Agrawal, N. Kayal & N. Saxena, <a href="https://doi.org/10.4007/annals.2004.160.781">PRIMES is in P</a>, Annals of Maths., 160:2 (2004), pp. 781-793. [<a href="http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf">alternate link</a>]

%H <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>

%e Row 4 = 1 mod 4, 4 mod 4, 6 mod 4, 4 mod 4, 1 mod 4 = 1, 0, 2, 0, 1.

%e Triangle begins:

%e 0;

%e 0,0;

%e 1,0,1;

%e 1,0,0,1;

%e 1,0,2,0,1;

%e 1,0,0,0,0,1;

%e 1,0,3,2,3,0,1;

%e 1,0,0,0,0,0,0,1;

%e 1,0,4,0,6,0,4,0,1;

%e 1,0,0,3,0,0,3,0,0,1;

%e 1,0,5,0,0,2,0,0,5,0,1;

%e 1,0,0,0,0,0,0,0,0,0,0,1;

%e 1,0,6,4,3,0,0,0,3,4,6,0,1;

%e 1,0,0,0,0,0,0,0,0,0,0,0,0,1;

%p f := n -> seriestolist( series( expand( (1+x)^n ) mod n, x, n+1)); # _N. J. A. Sloane_

%t Flatten[Join[{0},Table[Mod[Binomial[n,Range[0,n]],n],{n,20}]]] (* _Harvey P. Dale_, Apr 29 2013 *)

%o (Haskell)

%o a053200 n k = a053200_tabl !! n !! k

%o a053200_row n = a053200_tabl !! n

%o a053200_tabl = [0] : zipWith (map . flip mod) [1..] (tail a007318_tabl)

%o -- _Reinhard Zumkeller_, Jul 10 2015, Jan 01 2013

%o (PARI) T(n,k)=if(n, binomial(n,k)%n, 0) \\ _Charles R Greathouse IV_, Feb 07 2017

%Y Row sums give A053204. Cf. A053201, A053202, A053203, A007318 (Pascal's triangle).

%Y Cf. also A092241.

%Y Cf. A053214 (central terms, apart from initial 1).

%K nonn,tabl,nice

%O 0,13

%A _Asher Auel_, Dec 12 1999

%E Corrected by _T. D. Noe_, Feb 08 2008

%E Edited by _N. J. A. Sloane_, Aug 29 2008 at the suggestion of _R. J. Mathar_