最大公因数递推中的质数差分

IBM Ponder This #305 · 2023 年 9 月

Marco Bellocchi 提出了这个问题。序列 $a_{1}, a_{2}, a_{3}$ 满足 $a_{n} = a_{n - 1} + gcd (n, a_{n - 1})$ ，其中 $gcd (x, y)$ 表示最大公因数。

例如 $a_{1} = 11$ 时，由 $gcd (2, 11) = 1$ 得 $a_{2} = 12$ ，由 $gcd(3,12)=3$ 得 $a_{3} = 15$ ，继续得到：

11, 12, 15, 16, 17, 18, 19, 20, 21, 22, 33, 36,...

从 $n = 2$ 起考虑差分 $d_{n} = a_{n} - a_{n - 1} = gcd (n, a_{n - 1})$ ：

1, 3, 1, 1, 1, 1, 1, 1, 1, 11, 3, ...

其中第一项 $d_{2} = 1$ 、第二项 $d_{3} = 3$ 。继续并删除全部 1 后得到：

3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 941, 3, 7, 1889, ...

可以证明，当 $a_{1} = 11$ 时，剩余各项都是质数。原差分序列中 $3 = d_{3} = d_{12} = d_{24} = d_{48} = d_{51}$ ，因此 3 第五次出现在 $n = 51$ 。

任务：初值为 $a_{1} = 531$ 时，求 5 第十次出现对应的 $n$ 。另外，找出 $k, n$ ，使初值 $a_{1} = k$ 下有某个 $d_{n} > 1$ 却不是质数。

附加问题：初值 $a_{1} = 531$ 时，求 5 第二百次出现对应的 $n$ 。

解答

认真尝试后再打开

待补充。