Project Euler 335
Project Euler 335
题目
Gathering the beans
Whenever Peter feels bored, he places some bowls, containing one bean each, in a circle. After this, he takes all the beans out of a certain bowl and drops them one by one in the bowls going clockwise. He repeats this, starting from the bowl he dropped the last bean in, until the initial situation appears again. For example with \(5\) bowls he acts as follows:
So with \(5\) bowls it takes Peter \(15\) moves to return to the initial situation.
Let \(M(x)\) represent the number of moves required to return to the initial situation, starting with \(x\) bowls. Thus, \(M(5) = 15\). It can also be verified that \(M(100) = 10920\).
Find \(\displaystyle \sum_{k=0}^{10^{18}} M(2^k + 1)\). Give your answer modulo \(7^9\).
解决方案
设某一步操作把分布变成全 \(1\)。这一操作来自某个碗 \(p\)，取出 \(t=x_p\) 颗豆子并依次放到后面 \(t\) 个碗。要让操作后每个碗都是 \(1\)，注意：
- 被取走的碗 \(p\) 操作后是 \(0\)，因此它必须在撒豆过程中也被加到一次，即撒豆必须绕圈覆盖到 \(p\) 本身；
- 每个碗最终要加到 恰好一次，否则不会都变成 \(1\)。
因此撒豆必须覆盖整整一圈的 \(n\) 个碗，每个碗加 \(1\) 一次，故必须有\(t=n.\)而在该步开始之前，被撒到的每个碗都会被加 \(1\)，要最终变成 \(1\)，它们之前必须是 \(0\)。同时出发碗 \(p\) 之前必须有 \(n\) 颗豆子。于是“最后一步之前”的分布必然是：恰有一个碗里有 \(n\) 颗豆子，其余 \(n-1\) 个碗全为 \(0\)。 最后一步把这 \(n\) 颗豆子均匀撒一圈，回到全 \(1\)。
下面固定\(n=2^k+1, N=n-1=2^k.\)
虽然 \(M(n)\) 不要求“当前位置”回到起点，但为了分析方便，我们约定从碗 \(p=0\) 开始，跟踪当前位置 \(p\)。观察一个现象：当 \(p\) 再次变回 \(0\) 时，可以把过程自然切成若干段（称为一轮）。
- 第 \(r\) 轮：从某次 \(p=0\)（轮开始）起，直到下一次 \(p=0\)（下一轮开始）为止；
- 注意：最后一轮的结束点是“分布回到全 \(1\)”那一刻（此时 \(p\) 不一定是 \(0\)）。
在 \(n=2^k+1\) 的情形，实验现象非常稳定且可归纳证明：一共正好有 \(N=2^k\) 轮。更具体地，在每一轮开始时：
- 碗 \(0\) 里恰好是 \(1\)；
- 最后一个碗 \(n-1\) 里的豆子数会从 \(1\) 逐轮增长到 \(N\)，也就是第 \(r\) 轮开始时，碗 \(n-1\) 中有 \(r+1\) 颗豆子（\(r=0,1,\dots,N-1\)）。
直观解释：每一轮从 \(p=0\) 出发，最终会发生一次“绕回到 \(0\)”的跨界，这一次跨界恰好会让最后一个碗多得到 \(1\) 颗豆子；因为总豆子数固定为 \(n=N+1\)，当最后一个碗增长到 \(N\) 时，其余碗只剩下碗 \(0\) 的那 \(1\) 颗豆子，下一轮会把这 \(1\) 颗也逐步推进，最终形成“某个碗有 \(n\) 颗，其余为 \(0\)”并完成最后一步回到全 \(1\)。
于是 \(M(n)\) 就等于所有轮长之和：\(\displaystyle{M(2^k+1)=\sum_{r=0}^{2^k-1} \ell_k(r),}\)其中 \(\ell_k(r)\) 是第 \(r\) 轮的操作次数（轮长）。
定义“缺口”（表示和\(n\)的相比，少走的步数）\(d_k(r)=n-\ell_k(r).\)从大量小 \(k\) 的展开可以发现并可用归纳法证明：对 \(n=2^k+1\)，所有缺口 \(d_k(r)\) 都是 \(0\) 或 \(2\) 的幂，并且整列缺口有严格的自相似递推。递推写成序列形式最清晰。记缺口序列为 \[ \mathbf{d}_k=(d_k(0),d_k(1),\dots,d_k(2^k-1)). \] 直接由过程“从 \(2^{k-1}+1\) 扩到 \(2^k+1=2(2^{k-1}+1)-1\)”的结构（把圆在碗 \(0\) 处切开、比较“轮内不回到 \(0\) 的前进段”在两种规模下的对应关系）可得到：
- 基础：当 \(k=1\)（\(n=3\)）时两轮长度是 \((2,3)\)，故\(\mathbf{d}_1=(1,0).\)
- 递推：对 \(k\ge 2\)，令 \(m=2^{k-1}\)。则\(\mathbf{d}_k=(2d_{k-1}(0),2d_{k-1}(1),\dots,2d_{k-1}(m-2),m,d_{k-1}(0),d_{k-1}(1),\dots,d_{k-1}(m-1)).\) 也就是说：前半段（除去一个特殊位置）把旧缺口乘 \(2\)，中间插入一个缺口 \(2^{k-1}\)，后半段原样复制旧缺口。
这个递推与真实过程一一对应：前半段轮的“回到 \(0\)”发生得更早，因此轮长相对于 \(n\) 的缺口会被放大；当轮序达到 \(2^{k-1}-1\) 时发生一次“正好跨过半圈”的特殊回返，对应插入缺口 \(2^{k-1}\)；之后进入后半段，过程在结构上等价于规模 \(k-1\) 的继续推进，因此缺口原样重复。
令\(\displaystyle{D_k=\sum_{r=0}^{2^k-1} d_k(r)}\)为缺口总和。由上面的序列递推，直接对总和求递推（注意 \(\mathbf{d}_{k-1}\) 的最后一个元素总为 \(0\)，因此“前半段乘 \(2\) 且少一项”的细节不会带来额外麻烦）可得：\(\displaystyle{D_k = 2\sum_{r=0}^{2^{k-1}-2} d_{k-1}(r)+2^{k-1}+\sum_{r=0}^{2^{k-1}-1} d_{k-1}(r)= 3D_{k-1}+2^{k-1},}\)并且 \(D_1=1\)。
解这个一阶递推：\(D_k-3D_{k-1}=2^{k-1}n\)可得\(D_k=3^k-2^k.\)
另一方面，由定义 \(d_k(r)=n-\ell_k(r)\)，并且一共有 \(2^k\) 轮，并且有\(\displaystyle{\sum_{r=0}^{2^k-1}\ell_k(r)=2^k\cdot n - D_k.}\) 代入 \(n=2^k+1\) 与 \(D_k=3^k-2^k\)，得到
\[ M(2^k+1)=2^k(2^k+1)-(3^k-2^k) =4^k+2^{k+1}-3^k. \]
最终所求结果为
\[ \sum_{k=0}^{N} M(2^k+1)=\sum_{k=0}^{N}(4^k+2^{k+1}-3^k)=\dfrac{4^{N+1}-1}{3} + (2^{N+2}-2) - \dfrac{3^{N+1}-1}{2}. \]
因为 \(\gcd(2,M)=\gcd(3,M)=1\)，所以在模 \(M\) 下 \(2,3\) 都可逆，直接用模逆元即可。
代码
1 | N = 10 ** 18 |