Pozzo：极速幸运数检测器深度解读

背景

在计算机科学和数论的交叉领域，"幸运数"（Lucky Numbers）是一个经典且迷人的概念。与素数类似，幸运数也是通过一种特殊的筛选过程生成的。根据 OEIS（Online Encyclopedia of Integer Sequences，在线整数数列百科全书）Wiki 的描述，生成过程如下：

首先列出所有正奇数： 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, ...

第一步筛选：第一个非单位幸存数是 3，因此划去列表中第 3 个、第 6 个、第 9 个……位置上的数字。 剩余序列变为： 1, 3, [5], 7, 9, [11], 13, 15, [17], 19, 21, [23], 25, 27, [29], 31, ... (注：方括号表示被划去的数字)

第二步筛选：下一个未被划去的幸存数是 7，因此从新列表中划去第 7 个、第 14 个……位置上的数字。 剩余序列变为： 1, 3, 7, 9, 13, 15, [19], 21, 25, 27, 31, 33, 37, [39], 43, ...

依此类推，那些永远不被划去的数字即为幸运数： 1, 3, 7, 9, 13, 15, 21, 25, 31, ...

幸运数之所以受到关注，是因为它们在统计特性上与素数有着惊人的相似性。然而，随着搜索范围的扩大，传统算法在效率上遇到了瓶颈。为了突破这一限制，开发者开发了 Pozzo 这一工具，旨在以极高的效率检测大整数的幸运数属性，并将多个 OEIS 数列的搜索边界大幅推高。

核心内容

Pozzo 的核心突破在于其底层算法架构和内存管理策略，这使得它比前代工具效率提升了 1,000 到 100,000,000 倍。

高效的数据结构：Fenwick Tree（二叉索引树）

传统的幸运数筛选通常依赖于庞大的布尔数组或位图，随着数字增大，内存消耗呈线性甚至超线性增长。Pozzo 采用了一种更紧凑且高效的方法：

1. 位级压缩：为了检查 $k$ 个数字的幸运性，Pozzo 在 $k$ 个比特上维护一个 Fenwick Tree（二叉索引树）。
2. 快速查找与更新：树中的每个节点记录其范围内置位（set bits）的数量。通过遍历这棵树，程序可以非常快速地查找并取消设置第 $i$ 个置位比特。
3. 内存效率：筛选过程对每个奇数整数仅占用两个比特（一个用于位图，另一个用于 Fenwick Tree 的摊销空间）。这意味着平均每个比特内存可以处理一个整数。这种极致的内存优化限制了筛选窗口的大小，但并未限制最终能证明幸运性的数字上限。

超越筛选窗口的证明算法

虽然物理内存限制了筛选窗口（Sieve）的大小，但 Pozzo 允许对远高于筛选窗口的候选数进行幸运性证明。其算法逻辑如下：

1. 初始化排名：对于每个候选数 $n$，计算其在奇数序列中的排名：$rank = (n + 1) / 2$。
2. 迭代筛选：对于每一个幸运删除因子 $l$：
   • 如果 $rank % l == 0$，则该候选数被拒绝（即它会被第 $l$ 轮筛选剔除）。
   • 否则，更新排名：$rank -= rank / l$。
3. 终止条件：一旦 $rank < l$，意味着该候选数已经幸存于所有未来的删除操作，因此被判定为幸运数。

实际成果：Hackathon 项目与 OEIS 边界突破

作者幽默地表示，这个项目始于一次黑客松（Hackathon），灵感来源于杜尚（Duchamp）式的现成品艺术——直接选取一个现成的整数作为项目核心。经过在多个黑客松中尝试诸如“为听力失聪的狗提供优步服务”等创意后，作者决定回归纯粹的计算挑战。

Pozzo 显著扩展了多个 OEIS 数列的已知边界，以下是具体成果：

• A031882: 幸运十进制重复数字 (Lucky decimal repdigits)

  • 旧边界：$a(16) > 10^9$
  • 新边界：$a(18) \ge 777,777,777,777,777$
  • 搜索空间扩大倍数：$1, 3, 7, 15, 31, 63, 127, 511, 1023, 4095, 8191, 131071, 524287, 2097151, 4194303, 8388607, 33554431, 67108863, 8589934591, 68719476735, 1099511627775, 4398046511103$

• A057613: 形式为 $2^k - 1$ 的幸运数

  • 旧边界：$a(20) \ge 2^{34} - 1$
  • 新边界：$a(23) \ge 2^{49} - 1$
  • 搜索空间扩大倍数：$1, 3, 7, 31, 127, 8191, 131071, 524287, 8388607$

• A057612: 形式为 $2^p - 1$ (p为素数) 的幸运数

  • 旧边界：$a(9) > 2^{31} - 1$
  • 新边界：$a(9) \ge 2^{59} - 1$
  • 搜索空间扩大倍数：$1, 3, 13, 21, 1597, 6765, 75025, 32951280099$

• A057589: 幸运斐波那契数 (Lucky Fibonacci numbers)

  • 旧边界：$a(8) \ge 12,586,269,025$
  • 新边界：$a(9) \ge 727,234,602,481,41$
  • 搜索空间扩大倍数：$1, 3, 7, 3571, 9349, 710647, 12752043$

• A306632: 幸运卢卡斯数 (Lucky Lucas numbers)

  • 旧边界：$a(8) \ge 10^9$
  • 新边界：$a(8) \ge 100,501,350,283,429$
  • 搜索空间扩大倍数：$1, 15,