This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A047999 #319 Feb 16 2025 08:32:39 %S A047999 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 A047999 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 A047999 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 A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 2. %C A047999 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 A047999 Also triangle giving successive states of cellular automaton generated by "Rule 60" and "Rule 102". - _Hans Havermann_, May 26 2002 %C A047999 Also triangle formed by reading triangle of Eulerian numbers (A008292) mod 2. - _Philippe Deléham_, Oct 02 2003 %C A047999 Self-inverse when regarded as an infinite lower triangular matrix over GF(2). %C A047999 Start with [1], repeatedly apply the map 0 -> [00/00], 1 -> [10/11] [Allouche and Berthe] %C A047999 Also triangle formed by reading triangles A011117, A028338, A039757, A059438, A085881, A086646, A086872, A087903, A104219 mod 2. - _Philippe Deléham_, Jun 18 2005 %C A047999 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 A047999 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 A047999 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 A047999 T(n,k) = A057427(A143333(n,k)). - _Reinhard Zumkeller_, Oct 24 2010 %C A047999 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 A047999 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 A047999 T(n,k) = A134636(n,k) mod 2. - _Reinhard Zumkeller_, Nov 23 2012 %C A047999 T(n,k) = 1 - A219463(n,k), 0 <= k <= n. - _Reinhard Zumkeller_, Nov 30 2012 %C A047999 From _Vladimir Shevelev_, Dec 31 2013: (Start) %C A047999 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 A047999 Note that: s_n(1) = A001316(n), %C A047999 s_n(2) = A001317(n), %C A047999 s_n(3) = A100307(n), %C A047999 s_n(4) = A001317(2*n), %C A047999 s_n(5) = A100308(n), %C A047999 s_n(6) = A100309(n), %C A047999 s_n(7) = A100310(n), %C A047999 s_n(8) = A100311(n), %C A047999 s_n(9) = A100307(2*n), %C A047999 s_n(10) = A006943(n), %C A047999 s_n(16) = A001317(4*n), %C A047999 s_n(25) = A100308(2*n), etc. %C A047999 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 A047999 Comment from _N. J. A. Sloane_, Jan 18 2016: (Start) %C A047999 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 A047999 [1, 1, 1, 1, 1, 1] %C A047999 [1, 0, 1, 0, 1, 0] %C A047999 [1, 1, 0, 0, 1, 1] %C A047999 [1, 0, 0, 0, 1, 0] %C A047999 [1, 1, 1, 1, 0, 0] %C A047999 [1, 0, 1, 0, 0, 0]. %C A047999 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 A047999 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 A047999 From _Valentin Bakoev_, Jul 11 2020: (Start) %C A047999 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 A047999 1 0 1 0 0 0 1 0 0 0 0 0 0 0 %C A047999 1 1 1 1 0 0 1 1 0 0 0 0 0 0 - It is seen the self-similarity of the %C A047999 1 0 1 0 1 0 1 0 0 0 0 0 matrices M_1, M_2, ..., M_n, ..., %C A047999 1 1 1 1 1 1 1 1 0 0 0 0 analogously to the Sierpinski's fractal. %C A047999 1 0 0 0 1 0 0 0 %C A047999 1 1 0 0 1 1 0 0 %C A047999 1 0 1 0 1 0 1 0 %C A047999 1 1 1 1 1 1 1 1 %C A047999 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) %C A047999 Sierpinski's gasket has fractal (Hausdorff) dimension log(A000217(2))/log(2) = log(3)/log(2) = 1.58496... (and cf. A020857). This gasket is the first of a family of gaskets formed by taking the Pascal triangle (A007318) mod j, j >= 2 (see CROSSREFS). For prime j, the dimension of the gasket is log(A000217(j))/log(j) = log(j(j + 1)/2)/log(j) (see Reiter and Bondarenko references). - _Richard L. Ollerton_, Dec 14 2021 %D A047999 Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8. %D A047999 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 A047999 John W. Milnor and James D. Stasheff, Characteristic Classes, Princeton University Press, 1974, pp. 43-49 (sequence appears on p. 46). %D A047999 H.-O. Peitgen, H. Juergens and D. Saupe: Chaos and Fractals (Springer-Verlag 1992), p. 408. %D A047999 Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2. %D A047999 S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3. %H A047999 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 A047999 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 A047999 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 A047999 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 A047999 J. Baer, <a href="http://ccins.camosun.bc.ca/~jbritton/blaise/bigblaise.html">Explore patterns in Pascal's Triangle</a> %H A047999 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 A047999 Valentin Bakoev, <a href="/A047999/a047999_1.txt">Properties and links concerning M_n</a> %H A047999 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 A047999 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 A047999 A. Bogomolny, <a href="http://www.cut-the-knot.org/ctk/Sierpinski.shtml">Dot Patterns and Sierpinski Gasket</a> %H A047999 Boris A. Bondarenko, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/pascal.html">Generalized Pascal Triangles and Pyramids</a>, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see pp. 130-132. %H A047999 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 A047999 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 A047999 S. Butkevich, <a href="https://web.archive.org/web/20050305151737/http://www.math.ohio-state.edu/~btk/Pascal/">Pascal Triangle Applet</a> %H A047999 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 A047999 B. Cherowitzo, <a href="http://www-math.cudenver.edu/~wcherowi/jcorn5.html">Pascal's Triangle using Clock Arithmetic, Part I</a> %H A047999 B. Cherowitzo, <a href="http://www-math.cudenver.edu/~wcherowi/jcorn6.html">Pascal's Triangle using Clock Arithmetic, Part II</a> %H A047999 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 A047999 Ilya Gutkovskiy, <a href="/A275198/a275198.pdf">Illustrations (triangle formed by reading Pascal's triangle mod m)</a> %H A047999 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 A047999 Brady Haran, <a href="https://youtu.be/kbKtFN71Lfs">Chaos Game</a>, Numberphile video, YouTube (April 27, 2017). %H A047999 I. Kobayashi et al., <a href="http://www.ies.co.jp/math/java/misc/PascalTriangle/PascalTriangle.html">Pascal's Triangle</a> %H A047999 Dr. Math, <a href="http://www.mathforum.org/dr.math/faq/formulas/faq/regpoly.html">Regular polygon formulas</a> [Broken link?] %H A047999 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 A047999 National Curve Bank, <a href="http://curvebank.calstatela.edu/sierpinski/sierpinski.htm">Sierpinski Triangles</a> %H A047999 Hieu D. Nguyen, <a href="http://arxiv.org/abs/1412.3181">A Digital Binomial Theorem</a>, arXiv:1412.3181 [math.NT], 2014. %H A047999 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 A047999 A. M. Reiter, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Issues/31-2.pdf">Determining the dimension of fractals generated by Pascal's triangle</a>, Fibonacci Quarterly, 31(2), 1993, pp. 112-120. %H A047999 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 A047999 Vladimir 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 A047999 N. J. A. Sloane, <a href="/A047999/a047999.png">Illustration of rows 0 to 32</a> (encoignure style) %H A047999 N. J. A. Sloane, <a href="/A047999/a047999_1.png">Illustration of rows 0 to 64</a> (encoignure style) %H A047999 N. J. A. Sloane, <a href="/A047999/a047999_2.png">Illustration of rows 0 to 128</a> (encoignure style) %H A047999 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 A047999 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SierpinskiSieve.html">Sierpiński Sieve</a>, <a href="https://mathworld.wolfram.com/Rule60.html">Rule 60</a>, <a href="https://mathworld.wolfram.com/Rule102.html">Rule 102</a> %H A047999 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a> %H A047999 <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a> %H A047999 <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a> %F A047999 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 A047999 Sum_{k>=0} T(n, k) = A001316(n) = 2^A000120(n). %F A047999 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 A047999 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 A047999 From _Vladimir Shevelev_, Dec 31 2013: (Start) %F A047999 For polynomial {s_n(x)} we have %F A047999 s_0(x)=1; for n>=1, s_n(x) = Product_{i=1..A000120(n)} (x^(2^k_i) + 1), %F A047999 if the binary expansion of n is n = Sum_{i=1..A000120(n)} 2^k_i; %F A047999 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 A047999 Let x>1, t>0 be real numbers. Then %F A047999 Sum_{n>=0} 1/s_n(x)^t = Product_{k>=0} (1 + 1/(x^(2^k)+1)^t); %F A047999 Sum_{n>=0} (-1)^A000120(n)/s_n(x)^t = Product_{k>=0} (1 - 1/(x^(2^k)+1)^t). %F A047999 In particular, for t=1, x>1, we have %F A047999 Sum_{n>=0} (-1)^A000120(n)/s_n(x) = 1 - 1/x. (End) %F A047999 From _Valentin Bakoev_, Jul 11 2020: (Start) %F A047999 (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 A047999 T(i,0) = T(i,i) = 1, or %F A047999 T(i,j) = 0 if i < j, or %F A047999 T(i,j) = T(i-k,j), if j < k, or %F A047999 T(i,j) = T(i-k,j-k), if j >= k. %F A047999 Thus, for given i and j, T(i,j) can be computed in O(log_2(i)) steps. (End) %e A047999 Triangle begins: %e A047999 1, %e A047999 1,1, %e A047999 1,0,1, %e A047999 1,1,1,1, %e A047999 1,0,0,0,1, %e A047999 1,1,0,0,1,1, %e A047999 1,0,1,0,1,0,1, %e A047999 1,1,1,1,1,1,1,1, %e A047999 1,0,0,0,0,0,0,0,1, %e A047999 1,1,0,0,0,0,0,0,1,1, %e A047999 1,0,1,0,0,0,0,0,1,0,1, %e A047999 1,1,1,1,0,0,0,0,1,1,1,1, %e A047999 1,0,0,0,1,0,0,0,1,0,0,0,1, %e A047999 ... %p A047999 # Maple code for first M rows (here M=10) - _N. J. A. Sloane_, Feb 03 2016 %p A047999 ST:=[1,1,1]; a:=1; b:=2; M:=10; %p A047999 for n from 2 to M do ST:=[op(ST),1]; %p A047999 for i from a to b-1 do ST:=[op(ST), (ST[i+1]+ST[i+2]) mod 2 ]; od: %p A047999 ST:=[op(ST),1]; %p A047999 a:=a+n; b:=a+n; od: %p A047999 ST; # _N. J. A. Sloane_ %p A047999 # alternative %p A047999 A047999 := proc(n,k) %p A047999 modp(binomial(n,k),2) ; %p A047999 end proc: %p A047999 seq(seq(A047999(n,k),k=0..n),n=0..12) ; # _R. J. Mathar_, May 06 2016 %t A047999 Mod[ Flatten[ NestList[ Prepend[ #, 0] + Append[ #, 0] &, {1}, 13]], 2] (* _Robert G. Wilson v_, May 26 2004 *) %t A047999 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 A047999 Mod[#,2]&/@Flatten[Table[Binomial[n,k],{n,0,20},{k,0,n}]] (* _Harvey P. Dale_, Jun 26 2019 *) %o A047999 (PARI) \\ Recurrence for Pascal's triangle mod p, here p = 2. %o A047999 p = 2; s=13; T=matrix(s,s); T[1,1]=1; %o A047999 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 A047999 for(n=1,s,for(k=1,n,print1(T[n,k],", "))) \\ _Gerald McGarvey_, Oct 10 2009 %o A047999 (PARI) A011371(n)=my(s);while(n>>=1,s+=n);s %o A047999 T(n,k)=A011371(n)==A011371(k)+A011371(n-k) \\ _Charles R Greathouse IV_, Aug 09 2013 %o A047999 (PARI) T(n,k)=bitand(n-k,k)==0 \\ _Charles R Greathouse IV_, Aug 11 2016 %o A047999 (Haskell) %o A047999 import Data.Bits (xor) %o A047999 a047999 :: Int -> Int -> Int %o A047999 a047999 n k = a047999_tabl !! n !! k %o A047999 a047999_row n = a047999_tabl !! n %o A047999 a047999_tabl = iterate (\row -> zipWith xor ([0] ++ row) (row ++ [0])) [1] %o A047999 -- _Reinhard Zumkeller_, Dec 11 2011, Oct 24 2010 %o A047999 (Python) %o A047999 def A047999_T(n,k): %o A047999 return int(not ~n & k) # _Chai Wah Wu_, Feb 09 2016 %o A047999 (Magma) %o A047999 A047999:= func< n,k | BitwiseAnd(n-k, k) eq 0 select 1 else 0 >; %o A047999 [A047999(n,k): k in [0..n], n in [0..15]]; // _G. C. Greubel_, Dec 03 2024 %Y A047999 Sequences based on the triangles formed by reading Pascal's triangle mod m: (this sequence) (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 A047999 Other versions: A090971, A038183. %Y A047999 Cf. A007318, A054431, A001317, A008292, A083093, A034931, A034930, A008975, A034932, A166360, A249133, A064194, A227133. %Y A047999 From _Johannes W. Meijer_, Jun 05 2011: (Start) %Y A047999 A106344 is a skew version of this triangle. %Y A047999 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 A047999 nonn,tabl,easy,nice %O A047999 0,1 %A A047999 _N. J. A. Sloane_ %E A047999 Additional links from _Lekraj Beedassy_, Jan 22 2004