开关灯问题

问题

某生产车间有 盏照明灯，编号分别为 ,初始时刻所有灯全部处于关闭状态，检修机器人按照下面的步骤进行检修 (改变某灯的开关状态的含义是，若该灯处于关闭状态，改变状态后则处于打开状态，反之则处于关闭状态):

1. 改变编号为 的倍数的灯的开关状态，即打开所有灯;

2. 改变编号为 的倍数的灯的开关状态，即关闭所有编号为偶数的灯. 以此类推第 步改变编号为 的倍数的灯的开关状态，直至 时，检修完成.

(1) 检修完成时，求编号为 的灯的开关状态;

(2) 记 , :

(i) 求数列 的前 项和 ;

(ii) 检修完成时，求所有处于打开状态的灯的编号总和.

解答

(1) 编号为 30 的灯的开关状态

一盏灯的开关状态取决于其被操作的次数：初始关闭时，操作奇数次则打开，偶数次则关闭。灯的编号为 30，其被操作的次数等于 30 的正约数个数（第 k 步操作编号为 k 倍数的灯）。
30 的正约数为 1, 2, 3, 5, 6, 10, 15, 30，共 8 个（偶数）。因此，30 号灯被操作 8 次，最终处于关闭状态。

(2) (i) 数列 的前 项和

已知 ，先化简 ：

前 项和 。

利用平方和公式 及 ，得：

(2) (ii) 所有打开状态灯的编号总和

灯的最终状态由被操作次数（约数个数）决定：完全平方数有奇数个约数（被打开），非完全平方数有偶数个约数（被关闭）。

1 到 900 中，最大完全平方数为 ，故打开的灯编号为 。
利用平方和公式，总和为：

出题人假设你不会平方和公式给了第一问辅助，但是如果你会呢（

答案：(1) 关闭；(2)(i) ；(ii) 9455。

题目更改

把题目中的 "改变灯的开关状态" 变为 "把灯关闭",这样就变成了 "埃氏筛" 的操作，与平方数有关变成了与素数有关。

原问题中 “改变开关状态” 本质是对灯进行 “ toggle 操作”（开变关、关变开），最终状态由约数个数的奇偶性决定（平方数因约数个数为奇数而保持打开）。而将操作改为 “把灯关闭”（即仅执行 “关闭” 动作，不改变已关闭状态）后，整个过程完全对应埃拉托斯特尼筛法，最终打开的灯不再是平方数，而是素数。

还有一件事：

数学归纳法，证明略。

…