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