不含质数的类斐波那契数列

IBM Ponder This #277 · 2021 年 5 月

斐波那契数列由 $F_{0} = 0, F_{1} = 1$ 与递推 $F_{n} = F_{n - 1} + F_{n - 2}$ 定义。若序列 $A_{0}, A_{1}, A_{2}, \dots$ 对所有 $n \geq 2$ 满足 $A_{n} = A_{n - 1} + A_{n - 2}$ ，就称其为类斐波那契数列。普通数列中有许多质数，例如 $F_{3} = 2, F_{11} = 89$ 。希望选择互质初值 $A_{0}$ 、 $A_{1}$ ，使新数列没有任何质数。

关键是寻找三元组集合 [(p_1,m_1,a_1),…,(p_t,m_t,a_t)]，满足：

$1 \leq a_{k} \leq m_{k}$ ；
对每个自然数 n，总有某个 k，使 n 模 $m_{k}$ 同余于 $a_{k}$ ，即 $m_{k}$ 整除 $n - a_{k}$ ；
$p_{k}$ 为 $F_{m_{k}}$ 的质因数；
所有 $p_{k}$ 互不相同，而 $m_{k}$ 、 $a_{k}$ 可以重复。

从这样的集合可以构造 $A_{0}$ 、 $A_{1}$ ，使 $A_{0}$ 模 $p_{k}$ 同余于 $F_{m_{k} - a_{k}}$ ，且 $A_{1}$ 模 $p_{k}$ 同余于 $F_{m_{k} - a_{k} + 1}$ 。再利用适用于所有类斐波那契数列的恒等式 $A_{m + n} = A_{m} F_{n - 1} + A_{m + 1} F_{n}$ ，可以证明没有质数。

任务：给出满足四条要求的三元组集合。官方提示，存在十八组三元组的解，其中全部 $m_{k}$ 的质因数只含 2、3、5。

附加问题：实际计算 $A_{0}$ 、 $A_{1}$ ，并解释为何每个 $A_{n}$ 都被某个 $p_{k}$ 整除，却不等于该质数。

解答

认真尝试后再打开

待补充。

IBM Ponder This #277 · 2021 年 5 月 ​

IBM Ponder This #277 · 2021 年 5 月