谢尔宾斯基筛法

谢尔宾斯基筛法是由谢尔宾斯基于 1915 年描述的一种分形，在 13 世纪的意大利艺术中就已出现 (Wolfram 2002, p. 43)。它也被称为谢尔宾斯基垫片或谢尔宾斯基三角形。该曲线可以写成 Lindenmayer 系统，初始字符串为"FXF--FF--FF", 字符串重写 规则"F" -> "FF", "X" -> "--FXF++FXF++FXF--", 和角度 .

谢尔宾斯基筛法的第 次迭代在 Wolfram Language 中实现为SierpinskiMesh[n].

设 为迭代 后黑色三角形的数量， 为三角形边的长度， 为第 次迭代后黑色的 面积 分数。则

			(1)
			(2)
			(3)

因此，容量维度为

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

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

谢尔宾斯基筛法由美丽的递推方程产生

(8)

其中 表示按位 异或。它也由下式给出

(9)

其中 是由下式定义的第 个最低有效位

(10)

并且乘积取遍所有满足 的 (Allouche and Shallit 2003, p. 113)。

谢尔宾斯基筛法由 帕斯卡三角形 (mod 2) 给出，给出序列 1; 1, 1; 1, 0, 1; 1, 1, 1, 1; 1, 0, 0, 0, 1; ... (OEIS A047999; 左图)。换句话说，在帕斯卡三角形中，将所有奇数着色为黑色，将偶数着色为白色，会产生谢尔宾斯基筛法 (Guy 1990; Wolfram 2002, p. 870; 中图)。二项式系数 mod 2 可以使用按位运算 AND(NOT(), ) 计算，给出序列 0; 0, 0; 0, 1, 0; 0, 0, 0, 0; 0, 1, 2, 3, 0; ... (OEIS A102037; 右图)，然后如果结果为 0 则将三角形着色为黑色，否则着色为白色。这是 卢卡斯对应定理 对于二项式系数模素数的推论。

令人惊讶的是，基本元胞自动机规则 60、90 和 102 (当省略尾随零时) 也产生谢尔宾斯基筛法 (Wolfram 2002, p. 870)。Wolfram (2002, pp. 931-932) 给出了大量可用于计算谢尔宾斯基筛法的算法。

Gardner (1977) 和 Watkins (Conway 和 Guy 1996, Krížek et al. 2001) 独立注意到，边数为奇数的可构造多边形的边数由谢尔宾斯基筛法的前 32 行解释为 二进制数给出，给出 1, 3, 5, 15, 17, 51, 85, 255, ... (OEIS A004729, Conway 和 Guy 1996, p. 140)。换句话说，每一行都是不同费马素数的乘积，项由二进制计数给出。