Sierpiński Sieve

The Sierpiński sieve is a fractal described by Sierpiński (1915). Finite versions of its nested pattern appear 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 .

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

Start with an equilateral triangle of side length 1 at iteration zero. For a nonnegative integer , let be the number of black triangles after iteration , the side length of each triangle, and the fractional area which is black after the th iteration. Then

			(1)
			(2)
			(3)

The capacity dimension is therefore

			(4)
			(5)
			(6)
			(7)

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

The rows of the Sierpiński sieve, interpreted as binary numbers with least significant bit corresponding to the first entry in the row, satisfy the recurrence equation

(8)

where , is a positive integer, and denotes bitwise XOR. For a nonnegative integer , the same sequence is given by

(9)

where is the bit at position , counting from the least significant bit, in the binary expansion defined by

(10)

and the product is taken over all such that (Allouche and Shallit 2003, p. 113).

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 , for integers , is odd iff the bitwise operation AND(NOT(), ) gives 0. The operation itself gives the sequence 0; 0, 0; 0, 1, 0; 0, 0, 0, 0; 0, 1, 2, 3, 0; ... (OEIS A102037; right figure), whose zero and nonzero entries are colored black and white, respectively. This is a consequence of the Lucas correspondence theorem for binomial coefficients modulo a prime number.

Surprisingly, elementary cellular automaton rules 60, 90 and 102, starting with a single black cell on a white background and omitting 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.

Gardner (1977) and independently Watkins (Conway and Guy 1996, Krížek et al. 2001) noticed that the first 32 rows of the Sierpiński sieve interpreted as binary numbers give 1 together with the 31 known side counts of constructible polygons with an odd number of sides, beginning 1, 3, 5, 15, 17, 51, 85, 255, ... (OEIS A004729; Conway and Guy 1996, p. 140). Each of these first 32 rows is a product of distinct Fermat primes, with value 1 when no primes are selected. The terms follow binary counting.