The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle mod 2. 149

%I

%S 1,1,1,1,0,1,1,1,1,1,1,0,0,0,1,1,1,0,0,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,

%T 1,1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,0,1,1,1,

%U 1,1,0,0,0,0,1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1,1,1

%N Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle mod 2.

%C Restored the alternative spelling of Sierpinski to facilitate searching for this triangle using regular-expression matching commands in ASCII. - _N. J. A. Sloane_, Jan 18 2016

%C Also triangle giving successive states of cellular automaton generated by "Rule 60" and "Rule 102". - _Hans Havermann_, May 26 2002

%C Also triangle formed by reading triangle of Eulerian numbers (A008292) mod 2. - _Philippe Deléham_, Oct 02 2003

%C Self-inverse when regarded as an infinite lower triangular matrix over GF(2).

%C Start with [1], repeatedly apply the map 0 -> [00/00], 1 -> [10/11] [Allouche and Berthe]

%C Also triangle formed by reading triangles A011117, A028338, A039757, A059438, A085881, A086646, A086872, A087903, A104219 mod 2. - _Philippe Deléham_, Jun 18 2005

%C J. H. Conway writes (in Math Forum): at least the first 31 rows give odd-sided constructible polygons (sides 1, 3, 5, 15, 17 ... see A001317). The 1's form a Sierpiński sieve. - M. Dauchez (mdzzdm(AT)yahoo.fr), Sep 19 2005

%C When regarded as an infinite lower triangular matrix, its inverse is a (-1,0,1)-matrix with zeros undisturbed and the nonzero entries in every column form the Prouhet-Thue-Morse sequence (1,-1,-1,1,-1,1,1,-1,...) A010060 (up to relabeling). - _David Callan_, Oct 27 2006

%C Triangle read by rows: antidiagonals of an array formed by successive iterates of running sums mod 2, beginning with (1, 1, 1,...). - _Gary W. Adamson_, Jul 10 2008

%C T(n,k) = A057427(A143333(n,k)). - _Reinhard Zumkeller_, Oct 24 2010

%C The triangle sums, see A180662 for their definitions, link Sierpiński’s triangle A047999 with seven sequences, see the crossrefs. The Kn1y(n) and Kn2y(n), y >= 1, triangle sums lead to the Sierpiński-Stern triangle A191372. - _Johannes W. Meijer_, Jun 05 2011

%C Used to compute the total Steifel-Whitney cohomology class of the Real Projective space. This was an essential component of the proof that there are no product operations without zero divisors on R^n for n not equal to 1, 2, 4 or 8 (real numbers, complex numbers, quaternions, Cayley numbers), proved by Bott and Milnor. - _Marcus Jaiclin_, Feb 07 2012

%C T(n,k) = A134636(n,k) mod 2. - _Reinhard Zumkeller_, Nov 23 2012

%C T(n,k) = 1 - A219463(n,k), 0 <= k <= n. - _Reinhard Zumkeller_, Nov 30 2012

%C From _Vladimir Shevelev_, Dec 31 2013: (Start)

%C Also table of coefficients of polynomials s_n(x) of degree n which are defined by formula s_n(x) = Sum_{i=0..n} (binomial(n,i) mod 2)*x^k. These polynomials we naturally call Sierpiński's polynomials. They also are defined by the recursion: s_0(x)=1, s_(2*n+1)(x) = (x+1)*s_n(x^2), n>=0, and s_(2*n)(x) = s_n(x^2), n>=1.

%C Note that: s_n(1) = A001316(n),

%C s_n(2) = A001317(n),

%C s_n(3) = A100307(n),

%C s_n(4) = A001317(2*n),

%C s_n(5) = A100308(n),

%C s_n(6) = A100309(n),

%C s_n(7) = A100310(n),

%C s_n(8) = A100311(n),

%C s_n(9) = A100307(2*n),

%C s_n(10) = A006943(n),

%C s_n(16) = A001317(4*n),

%C s_n(25) = A100308(2*n), etc.

%C The equality s_n(10) = A006943(n) means that sequence A047999 is obtained from A006943 by the separation by commas of the digits of its terms. (End)

%C Comment from _N. J. A. Sloane_, Jan 18 2016: (Start)

%C Take a diamond-shaped region with edge length n from the top of the triangle, and rotate it by 45 degrees to get a square S_n. Here is S_6:

%C [1, 1, 1, 1, 1, 1]

%C [1, 0, 1, 0, 1, 0]

%C [1, 1, 0, 0, 1, 1]

%C [1, 0, 0, 0, 1, 0]

%C [1, 1, 1, 1, 0, 0]

%C [1, 0, 1, 0, 0, 0]

%C Then (i) S_n contains no square (parallel to the axes) with all four corners equal to 1 (cf. A227133); (ii) S_n can be constructed by using the greedy algorithm with the constraint that there is no square with that property; and (iii) S_n contains A064194(n) 1's. Thus A064194(n) is a lower bound on A227133(n). (End)

%C See A123098 for a multiplicative encoding of the rows, i.e., product of the primes selected by nonzero terms; e.g., 1 0 1 => 2^1 * 3^0 * 5^1. - _M. F. Hasler_, Sep 18 2016

%C From _Valentin Bakoev_, Jul 11 2020: (Start)

%C The Sierpinski's triangle with 2^n rows is a part of a lower triangular matrix M_n of dimension 2^n X 2^n. M_n is a block matrix defined recursively: M_1= [1, 0], [1, 1], and for n>1, M_n = [M_(n-1), O_(n-1)], [M_(n-1), M_(n-1)], where M_(n-1) is a block matrix of the same type, but of dimension 2^(n-1) X 2^(n-1), and O_(n-1) is the zero matrix of dimension 2^(n-1) X 2^(n-1). Here is how M_1, M_2 and M_3 look like:

%C 1 0 1 0 0 0 1 0 0 0 0 0 0 0

%C 1 1 1 1 0 0 1 1 0 0 0 0 0 0 - It is seen the self-similarity of the

%C 1 0 1 0 1 0 1 0 0 0 0 0 matrices M_1, M_2, ..., M_n, ...,

%C 1 1 1 1 1 1 1 1 0 0 0 0 analogously to the Sierpinski's fractal.

%C 1 0 0 0 1 0 0 0

%C 1 1 0 0 1 1 0 0

%C 1 0 1 0 1 0 1 0

%C 1 1 1 1 1 1 1 1

%C M_n can also be defined as M_n = M_1 X M_(n-1) where X denotes the Kronecker product. M_n is an important matrix in coding theory, cryptography, Boolean algebra, monotone Boolean functions, etc. It is a transformation matrix used in computing the algebraic normal form of Boolean functions. Some properties and links concerning M_n can be seen in LINKS. (End)

%D Brand, Neal; Das, Sajal; Jacob, Tom. The number of nonzero entries in recursively defined tables modulo primes. Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1990). Congr. Numer. 78 (1990), 47--59. MR1140469 (92h:05004).

%D John W. Milnor and James D. Stasheff, Characteristic Classes, Princeton University Press, 1974, pp. 43-49 (sequence appears on p. 46).

%D H.-O. Peitgen, H. Juergens and D. Saupe: Chaos and Fractals (Springer-Verlag 1992), p. 408.

%D Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

%H N. J. A. Sloane, <a href="/A047999/b047999.txt">Table of n, a(n) for n = 0..10584</a> [First 144 rows, flattened; first 50 rows from T. D. Noe].

%H J.-P. Allouche and V. Berthe, <a href="https://doi.org/10.36045/bbms/1105730620">Triangle de Pascal, complexité et automates</a>, Bulletin of the Belgian Mathematical Society Simon Stevin 4.1 (1997): 1-24.

%H J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen and G. Skordev, <a href="http://dx.doi.org/10.1016/0166-218X(94)00132-W">Linear cellular automata, finite automata and Pascal's triangle</a>, Discrete Appl. Math. 66 (1996), 1-22.

%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.],

%H J. Baer, <a href="http://ccins.camosun.bc.ca/~jbritton/blaise/bigblaise.html">Explore patterns in Pascal's Triangle</a>

%H Valentin Bakoev, <a href="http://serdica-comp.math.bas.bg/index.php/serdicajcomputing/article/view/304">Fast Bitwise Implementation of the Algebraic Normal Form Transform</a>, Serdica J. of Computing 11 (2017), No 1, 45-57.

%H Valentin Bakoev, <a href="/A047999/a047999_1.txt">Properties and links concerning M_n</a>

%H Thomas Baruchel, <a href="https://doi.org/10.1007/s42979-019-0049-1">Flattening Karatsuba's Recursion Tree into a Single Summation</a>, SN Computer Science (2020) Vol. 1, Article No. 48.

%H Thomas Baruchel, <a href="https://arxiv.org/abs/1912.00452">A non-symmetric divide-and-conquer recursive formula for the convolution of polynomials and power series</a>, arXiv:1912.00452 [math.NT], 2019.

%H A. Bogomolny, <a href="http://www.cut-the-knot.org/ctk/Sierpinski.shtml">Dot Patterns and Sierpinski Gasket</a>

%H Paul Bradley and Peter Rowley, <a href="http://eprints.ma.man.ac.uk/2167/01/covered/MIMS_ep2014_42.pdf">Orbits on k-subsets of 2-transitive Simple Lie-type Groups</a>, 2014.

%H E. Burlachenko, <a href="https://arxiv.org/abs/1612.00970">Fractal generalized Pascal matrices</a>, arXiv:1612.00970 [math.NT], 2016. See p. 9.

%H S. Butkevich, <a href="http://www.math.ohio-state.edu/~btk/Pascal">Pascal Triangle Applet</a> [Broken link?]

%H David Callan, <a href="http://arxiv.org/abs/math/0610932">Sierpinski's triangle and the Prouhet-Thue-Morse word</a>, arXiv:math/0610932 [math.CO], 2006.

%H B. Cherowitzo, <a href="http://www-math.cudenver.edu/~wcherowi/jcorn5.html">Pascal's Triangle using Clock Arithmetic, Part I</a>

%H B. Cherowitzo, <a href="http://www-math.cudenver.edu/~wcherowi/jcorn6.html">Pascal's Triangle using Clock Arithmetic, Part II</a>

%H C. Cobeli, A. Zaharescu, <a href="https://arxiv.org/abs/1411.1334">A game with divisors and absolute differences of exponents</a>, arXiv:1411.1334 [math.NT], 2014; Journal of Difference Equations and Applications, Vol. 20, #11, 2014.

%H R. K. Guy, <a href="http://www.jstor.org/stable/2322249">The strong law of small numbers</a>. Amer. Math. Monthly 95 (1988), no. 8, 697-712.

%H Brady Haran, <a href="https://youtu.be/kbKtFN71Lfs">Chaos Game</a>, Numberphile video, YouTube (April 27, 2017).

%H I. Kobayashi et al., <a href="http://www.ies.co.jp/math/java/misc/PascalTriangle/PascalTriangle.html">Pascal's Triangle</a>

%H Dr. Math, <a href="http://www.mathforum.org/dr.math/faq/formulas/faq/regpoly.html">Regular polygon formulas</a> [Broken link?]

%H Y. Moshe, <a href="http://dx.doi.org/10.1016/j.disc.2005.03.022">The distribution of elements in automatic double sequences</a>, Discr. Math., 297 (2005), 91-103.

%H National Curve Bank, <a href="http://curvebank.calstatela.edu/sierpinski/sierpinski.htm">Sierpinski Triangles</a>

%H Hieu D. Nguyen, <a href="http://arxiv.org/abs/1412.3181">A Digital Binomial Theorem</a>, arXiv:1412.3181 [math.NT], 2014.

%H S. Northshield, <a href="http://hdl.handle.net/20.500.12648/1110">Sums across Pascal's triangle modulo 2</a>, Congressus Numerantium, 200, pp. 35-52, 2010.

%H F. Richman, <a href="http://math.fau.edu/richman/jscripts.htm">Javascript for computing Pascal's triangle modulo n</a>. Go to this page, then under "Modern Algebra and Other Things", click "Pascal's triangle modulo n".

%H V. Shevelev, <a href="http://arxiv.org/abs/1011.6083">On Stephan's conjectures concerning Pascal triangle modulo 2 and their polynomial generalization</a>, J. of Algebra Number Theory: Advances and Appl., 7 (2012), no.1, 11-29. Also arXiv:1011.6083, 2010.

%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SierpinskiSieve.html">Sierpiński Sieve</a>, <a href="http://mathworld.wolfram.com/Rule60.html">Rule 60</a>, <a href="http://mathworld.wolfram.com/Rule102.html">Rule 102</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

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

%H <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>

%F Lucas's Theorem is that T(n,k) = 1 if and only if the 1's in the binary expansion of k are a subset of the 1's in the binary expansion of n; or equivalently, k AND NOT n is zero, where AND and NOT are bitwise operators. - _Chai Wah Wu_, Feb 09 2016 and _N. J. A. Sloane_, Feb 10 2016

%F Sum_{k>=0} T(n, k) = A001316(n) = 2^A000120(n).

%F T(n,k) = T(n-1,k-1) XOR T(n-1,k), 0<k<n; T(n,0) = T(n,n) = 1. - _Reinhard Zumkeller_, Dec 13 2009

%F T(n,k) = (T(n-1,k-1) + T(n-1,k)) mod 2 = |T(n-1,k-1) - T(n-1,k)|, 0<k<n; T(n,0) = T(n,n) = 1. - _Rick L. Shepherd_, Feb 23 2018

%F From _Vladimir Shevelev_, Dec 31 2013: (Start)

%F For polynomial {s_n(x)} we have

%F s_0(x)=1; for n>=1, s_n(x) = Product_{i=1..A000120(n)} (x^(2^k_i) + 1),

%F if the binary expansion of n is n = Sum_{i=1..A000120(n)} 2^k_i;

%F G.f. Sum_{n>=0} s_n(x)*z^n = Product_{k>=0} (1 + (x^(2^k)+1)*z^(2^k)) (0<z<1/x).

%F Let x>1, t>0 be real numbers. Then

%F Sum_{n>=0} 1/s_n(x)^t = Product_{k>=0} (1 + 1/(x^(2^k)+1)^t);

%F Sum_{n>=0} (-1)^A000120(n)/s_n(x)^t = Product_{k>=0} (1 - 1/(x^(2^k)+1)^t).

%F In particular, for t=1, x>1, we have

%F Sum_{n>=0} (-1)^A000120(n)/s_n(x) = 1 - 1/x. (End)

%F From _Valentin Bakoev_, Jul 11 2020: (Start)

%F (See my comment about the matrix M_n.) Denote by T(i,j) the number in the i-th row and j-th column of M_n (0 <= i, j < 2^n). When i>=j, T(i,j) is the j-th number in the i-th row of the Sierpinski's triangle. For given i and j, we denote by k the largest integer of the type k=2^m and k<i. Then T(i,j) is defined recursively as:

%F T(i,0) = T(i,i)= 1, or

%F T(i,j) = 0 if i<j, or

%F T(i,j) = T(i-k,j), if j<k, or

%F T(i,j) = T(i-k,j-k), if j>=k.

%F Thus, for given i and j, T(i,j) can be computed in O(log_2(i)) steps. (End)

%e Triangle begins:

%e .1,

%e .1,1,

%e .1,0,1,

%e .1,1,1,1,

%e .1,0,0,0,1,

%e .1,1,0,0,1,1,

%e .1,0,1,0,1,0,1,

%e .1,1,1,1,1,1,1,1,

%e .1,0,0,0,0,0,0,0,1,

%e .1,1,0,0,0,0,0,0,1,1,

%e .1,0,1,0,0,0,0,0,1,0,1,

%e .1,1,1,1,0,0,0,0,1,1,1,1,

%e .1,0,0,0,1,0,0,0,1,0,0,0,1,

%e ....

%p # Maple code for first M rows (here M=10) - _N. J. A. Sloane_, Feb 03 2016

%p ST:=[1,1,1]; a:=1; b:=2; M:=10;

%p for n from 2 to M do ST:=[op(ST),1];

%p for i from a to b-1 do ST:=[op(ST), (ST[i+1]+ST[i+2]) mod 2 ]; od:

%p ST:=[op(ST),1];

%p a:=a+n; b:=a+n; od:

%p ST; # _N. J. A. Sloane_

%p # alternative

%p A047999 := proc(n,k)

%p modp(binomial(n,k),2) ;

%p end proc:

%p seq(seq(A047999(n,k),k=0..n),n=0..12) ; # _R. J. Mathar_, May 06 2016

%t Mod[ Flatten[ NestList[ Prepend[ #, 0] + Append[ #, 0] &, {1}, 13]], 2] (* _Robert G. Wilson v_, May 26 2004 *)

%t rows = 14; ca = CellularAutomaton[60, {{1}, 0}, rows-1]; Flatten[ Table[ca[[k, 1 ;; k]], {k, 1, rows}]] (* _Jean-François Alcover_, May 24 2012 *)

%t Mod[#,2]&/@Flatten[Table[Binomial[n,k],{n,0,20},{k,0,n}]] (* _Harvey P. Dale_, Jun 26 2019 *)

%o (PARI) \\ Recurrence for Pascal's triangle mod p, here p = 2.

%o p = 2; s=13; T=matrix(s,s); T[1,1]=1;

%o for(n=2,s, T[n,1]=1; for(k=2,n, T[n,k] = (T[n-1,k-1] + T[n-1,k])%p ));

%o for(n=1,s,for(k=1,n,print1(T[n,k],", "))) \\ _Gerald McGarvey_, Oct 10 2009

%o (PARI) A011371(n)=my(s);while(n>>=1,s+=n);s

%o T(n,k)=A011371(n)==A011371(k)+A011371(n-k) \\ _Charles R Greathouse IV_, Aug 09 2013

%o (PARI) T(n,k)=bitand(n-k,k)==0 \\ _Charles R Greathouse IV_, Aug 11 2016

%o import Data.Bits (xor)

%o a047999 :: Int -> Int -> Int

%o a047999 n k = a047999_tabl !! n !! k

%o a047999_row n = a047999_tabl !! n

%o a047999_tabl = iterate (\row -> zipWith xor ([0] ++ row) (row ++ [0])) [1]

%o -- _Reinhard Zumkeller_, Dec 11 2011, Oct 24 2010

%o (Python)

%o def A047999_T(n,k):

%o return int(not ~n & k) # _Chai Wah Wu_, Feb 09 2016

%Y Sequences based on the triangles formed by reading Pascal's triangle mod m: A047999 (m = 2), A083093 (m = 3), A034931 (m = 4), A095140 (m = 5), A095141 (m = 6), A095142 (m = 7), A034930(m = 8), A095143 (m = 9), A008975 (m = 10), A095144 (m = 11), A095145 (m = 12), A275198 (m = 14), A034932 (m = 16).

%Y Other versions: A090971, A038183.

%Y Cf. A007318, A054431, A001317, A008292, A083093, A034931, A034930, A008975, A034932, A166360, A249133, A064194, A227133.

%Y From _Johannes W. Meijer_, Jun 05 2011: (Start)

%Y A106344 is a skew version of this triangle.

%Y Triangle sums (see the comments): A001316 (Row1; Related to Row2), A002487 (Related to Kn11, Kn12, Kn13, Kn21, Kn22, Kn23), A007306 (Kn3, Kn4), A060632 (Fi1, Fi2), A120562 (Ca1, Ca2), A112970 (Gi1, Gi2), A127830 (Ze3, Ze4). (End)

%K nonn,tabl,easy,nice

%O 0,1

%A _N. J. A. Sloane_