TOPICS
Search

Sierpiński Sieve


SierpinskiSieve
Sierpinski sieve from rule 90

The Sierpiński sieve is a fractal described by Sierpiński in 1915 and appearing in Italian art from the 13th century (Wolfram 2002, p. 43). It is also called the Sierpiński gasket or Sierpiński triangle. The curve can be written as a Lindenmayer system with initial string "FXF--FF--FF", string rewriting rules "F" -> "FF", "X" -> "--FXF++FXF++FXF--", and angle 60 degrees.

The nth iteration of the Sierpiński sieve is implemented in the Wolfram Language as SierpinskiMesh[n].

Let N_n be the number of black triangles after iteration n, L_n the length of a side of a triangle, and A_n the fractional area which is black after the nth iteration. Then

N_n=3^n
(1)
L_n=(1/2)^n=2^(-n)
(2)
A_n=L_n^2N_n=(3/4)^n.
(3)

The capacity dimension is therefore

d_(cap)=-lim_(n->infty)(lnN_n)/(lnL_n)
(4)
=log_23
(5)
=(ln3)/(ln2)
(6)
=1.584962500...
(7)

(OEIS A020857; Wolfram 1984; Borwein and Bailey 2003, p. 46).

The Sierpiński sieve is produced by the beautiful recurrence equation

 a_n=a_(n-1) xor 2a_(n-1),
(8)

where  xor denote bitwise XOR. It is also given by

 a_n=product_(j; e(j,n)=1)2^(2^(e(j,n)))+1,
(9)

where e(j,n) is the (j+1)st least significant bit defined by

 n=sum_(j=0)^te(j,n)2^j
(10)

and the product is taken over all j such that e(j,n)=1 (Allouche and Shallit 2003, p. 113).

SierpinskiSievePascal

The Sierpinski sieve is given by Pascal's triangle (mod 2), giving the sequence 1; 1, 1; 1, 0, 1; 1, 1, 1, 1; 1, 0, 0, 0, 1; ... (OEIS A047999; left figure). In other words, coloring all odd numbers black and even numbers white in Pascal's triangle produces a Sierpiński sieve (Guy 1990; Wolfram 2002, p. 870; middle figure). The binomial coefficient (n; k) mod 2 can be computed using bitwise operations AND(NOT(n), k), giving the sequence 0; 0, 0; 0, 1, 0; 0, 0, 0, 0; 0, 1, 2, 3, 0; ... (OEIS A102037; right figure), then coloring the triangle black if the result is 0 and white otherwise. This is a consequence of the Lucas correspondence theorem for binomial coefficients modulo a prime number.

SierpinskiSieveRules

Surprisingly, elementary cellular automaton rules 60, 90 and 102 (when omitting the trailing zeros) also produce the Sierpinski sieve (Wolfram 2002, p. 870). Wolfram (2002, pp. 931-932) gives a large number of algorithms that can be used to compute a Sierpiński sieve.

PolygonConstructionTri

Gardner (1977) and independently Watkins (Conway and Guy 1996, Krížek et al. 2001) noticed that the number of sides for constructible polygons with odd Numbers of sides are given by the first 32 rows of the Sierpiński sieve interpreted as binary numbers, giving 1, 3, 5, 15, 17, 51, 85, 255, ... (OEIS A004729, Conway and Guy 1996, p. 140). In other words, every row is a product of distinct Fermat primes, with terms given by binary counting.


See also

Chaos Game, Lindenmayer System, Lucas Correspondence Theorem, Pascal's Triangle, Rule 90, Rule 102, Sierpiński Arrowhead Curve, Sierpiński Carpet, Sierpiński Gasket Graph, Tetrix

Explore with Wolfram|Alpha

References

Allouche, J.-P. and Shallit, J. Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, 2003.Borwein, J. and Bailey, D. "Pascal's Triangle." §2.1 in Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 94-95, 2003.Bulaevsky, J. "The Sierpinski Triangle Fractal." http://ejad.best.vwh.net/java/fractals/sierpinski.shtml.Conway, J. H. and Guy, R. K. In The Book of Numbers. New York: Springer-Verlag, 1996.Crandall, R. and Pomerance, C. Prime Numbers: A Computational Perspective, 2nd ed. New York: Springer-Verlag, 2005.Crownover, R. M. Introduction to Fractals and Chaos. Sudbury, MA: Jones & Bartlett, 1995.Dickau, R. M. "Two-Dimensional L-Systems." http://mathforum.org/advanced/robertd/lsys2d.html.Dickau, R. M. "Typeset Fractals." Mathematica J. 7, 15, 1997. Dickau, R. "Sierpinski-Menger Sponge Code and Graphic." http://library.wolfram.com/infocenter/Demos/4662/.Gardner, M. "Pascal's Triangle." Ch. 15 in Mathematical Carnival: A New Round-Up of Tantalizers and Puzzles from Scientific American. New York: Vintage Books, pp. 194-207, 1977.Guy, R. K. "The Second Strong Law of Small Numbers." Math. Mag. 63, 3-20, 1990.Harris, J. W. and Stocker, H. "Sierpinski Gasket." §4.11.7 in Handbook of Mathematics and Computational Science. New York: Springer-Verlag, p. 115, 1998.Kabai, S. Mathematical Graphics I: Lessons in Computer Graphics Using Mathematica. Püspökladány, Hungary: Uniconstant, p. 127, 2002.Krížek, M.; Luca, F.; and Somer, L. 17 Lectures on Fermat Numbers: From Number Theory to Geometry. New York: Springer-Verlag, 2001.Lauwerier, H. Fractals: Endlessly Repeated Geometric Figures. Princeton, NJ: Princeton University Press, pp. 13-14, 1991.Mandelbrot, B. B. The Fractal Geometry of Nature. New York: W. H. Freeman, p. 142, 1983.Peitgen, H.-O.; Jürgens, H.; and Saupe, D. Chaos and Fractals: New Frontiers of Science. New York: Springer-Verlag, pp. 78-88, 1992.Peitgen, H.-O. and Saupe, D. (Eds.). The Science of Fractal Images. New York: Springer-Verlag, p. 282, 1988.Sierpiński, W. "Sur une courbe dont tout point est un point de ramification." C. R. A. S. 160, 302-305, 1915.Simmt, E. and Davis, B. "Fractal Cards: A Space for Exploration in Geometry and Discrete Mathematics." Math. Teacher 91, 102-108, 1998.Sloane, N. J. A. Sequences A004729, A020857, A047999, and A102037 in "The On-Line Encyclopedia of Integer Sequences."Steward, I. "Four Encounters with Sierpiński's Gasket." Math. Intel. 17, pp. 52-64, 1995.Sved, M. "Divisibility--with Visibility." Math. Intell. 10, 56-64, 1988.Wagon, S. Mathematica in Action. New York: W. H. Freeman, pp. 108 and 151-153, 1991.Update a linkWang, P. "Renderings." http://www.ugcs.caltech.edu/~peterw/portfolio/renderings/Wolfram, S. "Computation Theory of Cellular Automata." Comm. Math. Phys. 96, 15-57, 1984.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 870 and 931-932, 2002.

Referenced on Wolfram|Alpha

Sierpiński Sieve

Cite this as:

Weisstein, Eric W. "Sierpiński Sieve." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SierpinskiSieve.html

Subject classifications