128. 六边形地砖差值(Hexagonal Tile Differences)
一个六边形地砖上写有数字 \(1\)，它被一圈六块六边形地砖所环绕。从"12点钟方向"开始，按逆时针方向为地砖编号 \(2\) 到 \(7\)。
以同样的方式添加新的圈层，接下来的圈层编号依次为 \(8\) 到 \(19\)，\(20\) 到 \(37\)，\(38\) 到 \(61\)，以此类推。
通过计算地砖 \(n\) 与其六个邻居之间的差值，我们定义 \(\operatorname{PD}(n)\) 为这些差值中素数的个数。
例如，顺时针绕地砖 \(8\) 走一圈，差值分别为 \(12, 29, 11, 6, 1\) 和 \(13\)。因此 \(\operatorname{PD}(8) = 3\)。
类似地，绕地砖 \(17\) 的差值为 \(1, 17, 16, 1, 11\) 和 \(10\)，因此 \(\operatorname{PD}(17) = 2\)。
可以证明 \(\operatorname{PD}(n)\) 的最大值为 \(3\)。
将所有满足 \(\operatorname{PD}(n) = 3\) 的地砖按升序排列构成一个序列，第 \(10\) 块地砖是 \(271\)。
找出该序列中第 \(2000\) 块地砖。
一、数学背景
六边形网格的坐标表示
采用立方体坐标 \((x, y, z)\) 满足 \(x+y+z=0\)。中心地砖 \(1\) 位于 \((0,0,0)\)。六个邻居方向向量为：
地砖 \((x,y,z)\) 所在的圈层 \(L\) 定义为 \(L = \max(|x|,|y|,|z|)\)。圈层 \(k\)（\(k \ge 1\)）包含 \(6k\) 块地砖，编号从"12点钟方向"开始逆时针排列。
圈层 \(k\) 的起始地砖（12点钟位置）编号为：
圈层 \(k\) 的终止地砖（恰好位于12点钟顺时针方向）编号为：
哪些地砖可能满足 \(\operatorname{PD}(n) = 3\)
通过穷举前若干圈层的所有地砖，可以发现：只有位于六边形环的"角"位置的地砖才可能具有 \(\operatorname{PD}=3\)。具体而言，仅有 \(s_k\)（12点钟方向的角）和 \(e_k\)（相邻的角，位于约1点钟方向）可能满足条件，外加中心地砖 \(1\)。
\(s_k\) 的邻居差分析
地砖 \(s_k\) 坐标为 \((0, k, -k)\)。六个邻居及其差值：
| 方向 | 邻居坐标 | 邻居编号 | 差值 |
|---|---|---|---|
| \(\mathbf{v}_0\) | \((1, k-1, -k)\) | \(s_k+1\) | \(1\) |
| \(\mathbf{v}_1\) | \((1, k, -k-1)\) | \(s_{k+1}+1\) | \(6k+1\) |
| \(\mathbf{v}_2\) | \((0, k+1, -k-1)\) | \(s_{k+1}\) | \(6k\) |
| \(\mathbf{v}_3\) | \((-1, k+1, -k)\) | \(e_{k+1}\) | \(12k+5\) |
| \(\mathbf{v}_4\) | \((-1, k, -k+1)\) | \(e_k\) | \(6k-1\) |
| \(\mathbf{v}_5\) | \((0, k-1, -k+1)\) | \(s_{k-1}\) | \(6(k-1)\) |
其中 \(1\) 不是素数；\(6k\) 和 \(6(k-1)\) 为偶数（\(k \ge 1\) 时 \(>2\)），不是素数。因此只有三个候选值可能为素数：
\(e_k\) 的邻居差分析
地砖 \(e_k\) 坐标为 \((-1, k, -k+1)\)。类似分析可得六个邻居差值：
| 方向 | 差值 |
|---|---|
| \(\mathbf{v}_4\) | \(1\) |
| \(\mathbf{v}_1\) | \(6k-1\) |
| \(\mathbf{v}_0\) | \(12k-7\) |
| \(\mathbf{v}_5\) | \(6k\) |
| \(\mathbf{v}_2\) | \(6(k+1)\) |
| \(\mathbf{v}_3\) | \(6k+5\) |
其中 \(1\)、\(6k\)、\(6(k+1)\) 均不是素数。因此：
（注意：\(k=1\) 时 \(e_1=7\) 的邻居情况有差异，因内层邻居是中心地砖 \(1\) 而非 \(s_0\)。实际计算 \(e_1\) 的 \(\operatorname{PD}=2\)，不满足条件。）
二、算法设计
基于上述分析，我们只需遍历 \(k = 1, 2, 3, \dots\)，对每个 \(k\) 检查：
- 若 \(6k-1\)、\(6k+1\)、\(12k+5\) 均为素数，则将 \(s_k = 3k(k-1)+2\) 加入结果列表。
- 若 \(k \ge 2\) 且 \(6k-1\)、\(12k-7\)、\(6k+5\) 均为素数，则将 \(e_k = 3k(k+1)+1\) 加入结果列表。
由于 \(s_k\) 和 \(e_k\) 都要求 \(6k-1\) 为素数，可将其作为前置条件，避免冗余的素性检测。
初始结果列表包含地砖 \(1\)（\(\operatorname{PD}(1)=3\) 恒成立）。
三、复杂度分析
- 空间复杂度：\(\mathcal{O}(1)\)，仅需存储结果列表和少量临时变量。
- 时间复杂度：需要遍历 \(k\) 直至找到 \(2000\) 个满足条件的地砖。第 \(2000\) 个地砖对应的 \(k \approx 69563\)。对每个 \(k\) 最多进行 \(4\) 次素性检测（\(6k-1\) 被复用）。使用预计算小素数表进行试除法素性检测，每次检测耗时 \(\mathcal{O}(\sqrt{n})\)，其中 \(n \approx 12k \approx 8 \times 10^5\)，\(\sqrt{n} \approx 900\)。预计算的素数表上限需覆盖 \(\sqrt{n}\)，即约 \(1000\) 以内的所有素数（\(168\) 个）。
总体运算量约为 \(69563 \times 4 \times 168 \approx 4.7 \times 10^7\) 次除法运算，在 Python 中可在 \(0.5\) 秒内完成。
四、代码实现与说明
核心素性检测
def is_prime(n):
"""使用试除法检测素数，预计算小素数表"""
if n < 2:
return False
limit = int(n ** 0.5)
for p in SMALL_PRIMES:
if p > limit:
return True
if n % p == 0:
return False
p = SMALL_PRIMES[-1] + 2
while p <= limit:
if n % p == 0:
return False
p += 2
return True
主循环
pd3_tiles = [1] # 地砖1恒有PD(3)
k = 1
while len(pd3_tiles) < 2000:
a = 6 * k - 1
if is_prime(a):
# 检查s_k条件
if is_prime(6 * k + 1) and is_prime(12 * k + 5):
pd3_tiles.append(3 * k * (k - 1) + 2)
# 检查e_k条件 (k >= 2)
if k >= 2 and is_prime(12 * k - 7) and is_prime(6 * k + 5):
pd3_tiles.append(3 * k * (k + 1) + 1)
k += 1
- 地砖 \(1\) 直接加入结果：\(\operatorname{PD}(1)=3\) 恒成立
6*k-1作为 \(s_k\) 和 \(e_k\) 的共同前置条件，先检测以减少计算量- 对 \(k=1\) 的 \(e_k\) 不做检测：\(e_1=7\) 的邻居结构特殊，\(\operatorname{PD}(7)=2\)
- \(s_k\) 和 \(e_k\) 天然满足 \(s_k < e_k < s_{k+1}\)，追加顺序即为升序，无需额外排序