Cullen and Woodall numbers in Padovan and Perrin sequences

技术摘要：Padovan 和 Perrin 序列中的 Cullen 与 Woodall 数

问题陈述
本文探讨了两类特定的指数丢番图数与线性递推序列的交集。具体而言，作者研究了Woodall 数（形式为 $W_m = m \cdot 2^m - 1$ 的整数）在Padovan 序列 $\{P_n\}$ 中的存在性，以及Cullen 数（形式为 $C_m = m \cdot 2^m + 1$ 的整数）在Perrin 序列 $\{R_n\}$ 中的存在性。

Padovan 序列和 Perrin 序列均由递推关系 $U_{n+3} = U_{n+1} + U_n$ 定义，但具有不同的初始条件：

• Padovan：$P_0 = P_1 = P_2 = 1$。
• Perrin：$R_0 = 3, R_1 = 0, R_2 = 2$。

虽然 Bravo 和 Irmak [4] 之前的工作已确定了 Padovan 序列中的 Cullen 数和 Perrin 序列中的 Woodall 数，但互补情形（Padovan 序列中的 Woodall 数、Perrin 序列中的 Cullen 数）仍属未解。作者旨在彻底解决这些剩余情形。

方法论
证明策略遵循求解线性递推序列中丢番图方程的标准框架，结合了解析数论与计算验证：

1. 闭式分析：作者利用两个序列的 Binet 型公式，将各项表示为特征多项式 $\phi(X) = X^3 - X - 1$ 的根的幂的线性组合。这使得能够进行增长估计，并推导出界定索引 $n$ 和 $m$ 的不等式。
2. 对数线性型：为了建立变量 $m$ 的绝对上界，作者应用了关于代数数三个对数的线性型的Matveev 定理。通过构造涉及 $\log 2$、$\log \alpha$（其中 $\alpha$ 是 $\phi(X)$ 的实根）和 $\log m$ 的线性型 $\Lambda$，他们推导出了 $|\Lambda|$ 的下界。将此下界与从递推增长推导出的上界进行比较，得出了 $m$ 的初始（尽管很大）上界（Padovan 情形约为 $5.6 \times 10^{14}$，Perrin 情形约为 $5.4 \times 10^{14}$）。
3. 2-进赋值分析：为了将 Matveev 定理获得的巨大上界缩减至计算可行的范围，作者对移位序列 $\{P_n + 1\}$ 和 $\{R_n - 1\}$ 的2-进赋值（$\nu_2$）进行了详细分析。
   • 他们基于 $n$ 模特定整数（例如 Padovan 为 112，Perrin 为 14）的余数，建立了 $\nu_2(P_n + 1)$ 和 $\nu_2(R_n - 1)$ 的显式公式。
   • 对于不存在统一闭式表达的“异常”余数类，他们采用基于倍增递推（引理 2.10 和 2.11）的贪心算法，计算在先前建立的界限内 $n$ 的最大可能赋值。
   • 该分析得出了不等式 $m \leq \nu_2(\text{移位项})$，从而极大地缩减了 $m$ 的搜索空间。
4. 计算验证：一旦 $m$ 的界限被缩减为小常数（具体为 Padovan 情形 $m \leq 56$，Perrin 情形 $m \leq 51$），作者便使用SageMath进行穷举计算搜索，以检查缩减范围内是否存在解。

主要贡献与结果
本文提供了关于这些特定序列中 Woodall 数和 Cullen 数的两个未解问题的完整解答：

• 定理 1.1：Padovan 序列中唯一的 Woodall 数是 1 和 7。
  • 推论 1.2：因此，Padovan 序列中唯一的 Woodall 素数是 7。
• 定理 1.3：Perrin 序列中唯一的 Cullen 数是 3。
  • 推论 1.4：因此，Perrin 序列中唯一的 Cullen 素数是 3。

证明依赖于 $P_n + 1$ 和 $R_n - 1$ 的 2-进赋值的特定性质。值得注意的是，作者识别了这些移位序列的非有理 2-进零点，这促使他们针对异常余数类采用了算法方法。

意义与主张
作者将这项工作定位为 Bravo 和 Irmak [4] 发起的研究的自然延续。通过确定互补的数集，本文完整刻画了 Woodall 数和 Cullen 数与 Padovan 序列及 Perrin 序列的交集。

其意义在于：

1. 完备性：它解决了这些特定三阶线性递推序列的剩余未解情形。
2. 方法论改进：本文展示了分析移位序列（$P_n+1$ 和 $R_n-1$）的 2-进赋值而非序列本身的必要性，突显了特定初始条件和目标数形式（$m \cdot 2^m \pm 1$）所引入的复杂性。
3. 算法应用：该工作利用并改进了计算异常余数类中 2-进赋值的算法，为这些序列提供了非有理 2-进零点的显式近似。

本文并未声称超出所解决的具体丢番图问题之外的更广泛应用，但为关于指数丢番图方程与线性递推序列交集的日益丰富的文献做出了贡献。