login
This site is supported by donations to The OEIS Foundation.

 

Logo


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. 136
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, 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, 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

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

Also triangle giving successive states of cellular automaton generated by "Rule 60" and "Rule 102". - Hans Havermann, May 26 2002

Also triangle formed by reading triangle of Eulerian numbers (A08292) mod 2. - Philippe Deléham, Oct 02 2003

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

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

Also triangle formed by reading triangles A011117, A028338, A039757, A059438, A085881, A086646, A086872, A087903, A0104219 mod 2. - Philippe Deléham, Jun 18 2005

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

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

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

T(n,k) = A057427(A143333(n,k)). - Reinhard Zumkeller, Oct 24 2010

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

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

T(n,k) = A134636(n,k) mod 2. - Reinhard Zumkeller, Nov 23 2012

T(n,k) = 1 - A219463(n,k), 0 <= k <= n. - Reinhard Zumkeller, Nov 30 2012

From Vladimir Shevelev, Dec 31 2013: (Start)

Also table of coefficients of polynomials s_n(x) of degree n which are defined by formula s_n(x) = sum{i=0,...,n} mod(binomial(n,i), 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.

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

           s_n(2) = A001317(n),

           s_n(3) = A100307(n),

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

           s_n(5) = A100308(n),

           s_n(6) = A100309(n),

           s_n(7) = A100310(n),

           s_n(8) = A100311(n),

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

           s_n(10) = A006943(n),

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

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

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)

Comment from N. J. A. Sloane, Jan 18 2016: (Start)

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:

[1, 1, 1, 1, 1, 1]

[1, 0, 1, 0, 1, 0]

[1, 1, 0, 0, 1, 1]

[1, 0, 0, 0, 1, 0]

[1, 1, 1, 1, 0, 0]

[1, 0, 1, 0, 0, 0]

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)

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

REFERENCES

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).

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

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

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

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

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10584 [First 144 rows, flattened; first 50 rows from T. D. Noe].

J.-P. Allouche and V. Berthe, Triangle de Pascal, complexite et automates, Bulletin of the Belgian Mathematical Society Simon Stevin 4.1 (1997): 1-24.

J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen and G. Skordev, Linear cellular automata, finite automata and Pascal's triangle, Discrete Appl. Math. 66 (1996), 1-22.

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191.

J. Baer, Explore patterns in Pascal's Triangle

A. Bogomolny, Dot Patterns and Sierpinski Gasket

Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, 2014.

E. Burlachenko, Fractal generalized Pascal matrices, arXiv:1612.00970 [math.NT], 2016. See p. 9.

S. Butkevich, Pascal Triangle Applet

David Callan, Sierpinski's triangle and the Prouhet-Thue-Morse word, arXiv:math/0610932 [math.CO], 2006.

B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part I

B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part II

C. Cobeli, A. Zaharescu, A game with divisors and absolute differences of exponents, Journal of Difference Equations and Applications, Vol. 20, #11, 2014. Also arXiv 1411.1334.

A. Granville, Pascal's Triangle Interface

R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.

I. Kobayashi et al., Pascal's Triangle

Dr. Math, Regular polygon formulas [Broken link?]

Y. Moshe, The distribution of elements in automatic double sequences, Discr. Math., 297 (2005), 91-103.

National Curve Bank, Sierpinski Triangles

Hieu D. Nguyen, A Digital Binomial Theorem, arXiv:1412.3181 [math.NT], 2014.

S. Northshield, Sums across Pascal's triangle modulo 2, Congressus Numerantium, 200, pp. 35-52, 2010.

F. Richman, Javascript for computing Pascal's triangle modulo n. Go to this page, then under "Modern Algebra and Other Things", click "Pascal's triangle modulo n".

V. Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2 and their polynomial generalization, J. of Algebra Number Theory: Advances and Appl., 7 (2012), no.1, 11-29. Also arXiv:1011.6083, 2010.

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Eric Weisstein's World of Mathematics, Sierpiński Sieve, Rule 60, Rule 102

Index entries for sequences related to cellular automata

Index entries for triangles and arrays related to Pascal's triangle

Index entries for sequences generated by sieves

FORMULA

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

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

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

From Vladimir Shevelev, Dec 31 2013: (Start)

For polynomial {s_n(x)} we have

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

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

G.f. sum {n>=0} s_n(x)*z^n = prod{k>=0}(1 + (x^(2^k)+1)z^(2^k)) (0<z<1/x).

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

sum{n>=0}1/s_n(x)^t = prod{k>=0}(1 + 1/(x^(2^k)+1)^t);

sum{n>=0}(-1)^A000120(n)/s_n(x)^t = prod{k>=0}(1 - 1/(x^(2^k)+1)^t).

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

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

EXAMPLE

Triangle begins:

.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,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,1,1,0,0,0,0,1,1,1,1,

.1,0,0,0,1,0,0,0,1,0,0,0,1,

....

MAPLE

# Maple code for first M rows (here M=10) - N. J. A. Sloane, Feb 03 2016

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

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

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

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

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

ST; # N. J. A. Sloane

# alternative

A047999 := proc(n, k)

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

end proc:

seq(seq(A047999(n, k), k=0..n), n=0..12) ; # R. J. Mathar, May 06 2016

MATHEMATICA

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

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 *)

PROG

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

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

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 ));

for(n=1, s, for(k=1, n, print1(T[n, k], ", "))) \\ Gerald McGarvey, Oct 10 2009

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

T(n, k)=A011371(n)==A011371(k)+A011371(n-k) \\ Charles R Greathouse IV, Aug 09 2013

(PARI) T(n, k)=bitand(n-k, k)==0 \\ Charles R Greathouse IV, Aug 11 2016

(Haskell)

import Data.Bits (xor)

a047999 :: Int -> Int -> Int

a047999 n k = a047999_tabl !! n !! k

a047999_row n = a047999_tabl !! n

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

-- Reinhard Zumkeller, Dec 11 2011, Oct 24 2010

(Python)

def A047999_T(n, k):

    return int(not ~n & k) # Chai Wah Wu, Feb 09 2016

CROSSREFS

Other versions: A090971, A038183.

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

From Johannes W. Meijer, Jun 05 2011: (Start)

A106344 is a skew version of this triangle.

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)

Sequence in context: A144093 A143200 A166282 * A054431 A164381 A106470

Adjacent sequences:  A047996 A047997 A047998 * A048000 A048001 A048002

KEYWORD

nonn,tabl,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional links from Lekraj Beedassy, Jan 22 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 24 02:10 EDT 2017. Contains 283984 sequences.