IBM Research

谜题   IBM-277

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

IBM Research · Ponder This · 2021 年 5 月

IBM Ponder This #277 · 2021 年 5 月 ​

斐波那契数列由 F0=0,F1=1 与递推 Fn=Fn−1+Fn−2 定义。若序列 A0,A1,A2,… 对所有 n≥2 满足 An=An−1+An−2,就称其为类斐波那契数列。普通数列中有许多质数,例如 F3=2,F11=89。希望选择互质初值 A0、A1,使新数列没有任何质数。

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

  1. 1≤ak≤mk;
  2. 对每个自然数 n,总有某个 k,使 n 模 mk 同余于 ak,即 mk 整除 n−ak;
  3. pk 为 Fmk 的质因数;
  4. 所有 pk 互不相同,而 mk、ak 可以重复。

从这样的集合可以构造 A0、A1,使 A0 模 pk 同余于 Fmk−ak,且 A1 模 pk 同余于 Fmk−ak+1。再利用适用于所有类斐波那契数列的恒等式 Am+n=AmFn−1+Am+1Fn,可以证明没有质数。

任务:给出满足四条要求的三元组集合。官方提示,存在十八组三元组的解,其中全部 mk 的质因数只含 2、3、5。

附加问题:实际计算 A0、A1,并解释为何每个 An 都被某个 pk 整除,却不等于该质数。

解答

认真尝试后再打开

待补充。