倍数无关集

一个 集合 的 正整数 是倍数无关的，如果对于任何整数 , 该集合 (或者等价地， 意味着 )。 例如，在 的子集中，集合 , , , , , 和 是倍数无关的，而 和 不是。

集合 的倍数无关子集数量 可以使用 和以下 递推关系 计算

(1)

其中 是 斐波那契数, 1, 1, 2, 3, 5, 8, ... (OEIS A000045), 并且 是 二进制进位序列，表示 的 二进制 表示中末尾 0 的数量。 对于 , 2, ..., 由 0, 1, 0, 2, 0, 1, 3, 0, 1, ... (OEIS A007814) 给出，而相应的 是 2, 3, 6, 10, 20, 30, 60, 96, 192, ... (OEIS A050291)。

定义

(2)

其中 是 的 基数 (成员数量)。 那么对于 , 2, ..., 由 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10, ... (OEIS A050292) 给出。 的显式公式由下式给出

(3)

其中

(4)

如果 的 特征函数 (如上定义)，并且 的前几个值是 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ... (OEIS A035263)。 的一个简单 递推关系 由下式给出

(5)

其中 (Wang 1989)，其中 是 向下取整函数， 是 向上取整函数。 的一个渐近公式由下式给出

(6)

(Wang 1989)。