Project Euler 319
Project Euler 319
题目
Bounded Sequences
Let \(x_1, x_2,\dots, x_n\) be a sequence of length \(n\) such that:
- \(x_1 = 2\)
- for all \(1 < i \le n\) : \(x_{i-1} < x_i\)
- for all \(i\) and \(j\) with \(1 \le i, j \le n : (x_i)^j < (x_j + 1)^i\)
There are only five such sequences of length \(2\), namely: \(\{2,4\}, \{2,5\}, \{2,6\}, \{2,7\}\) and \(\{2,8\}\).
There are \(293\) such sequences of length \(5\); three examples are given below:
\(\{2,5,11,25,55\}, \{2,6,14,36,88\}, \{2,8,22,64,181\}.\)
Let \(t(n)\) denote the number of such sequences of length \(n\).
You are given that \(t(10) = 86195\) and \(t(20) = 5227991891\).
Find \(t(10^{10})\) and give your answer modulo \(10^9\).
解决方案
题目给序列 \(x_1,\dots,x_n\)，满足：
- \(x_1=2\)，且严格递增（后面会发现这一条其实自动满足）
- 对任意 \(i,j\)：\((x_i)^j < (x_j+1)^i .\)
把不等式两边取 \(ij\) 次方根，得到等价形式\(x_i^{1/i} < (x_j+1)^{1/j}\)，也就是进一步可以写成\(\displaystyle{\max_i\{x_i^{1/i}\}<\min_j\{(x_j+1)^{1/j}\}}\).
令区间\(I_i=[x_i^{1/i},(x_i+1)^{1/i}).\)也就是\(\displaystyle{\bigcap_{i=1}^n I_i \neq \varnothing}.\)
因此 题目条件等价于：存在实数 \(\alpha\) 使得对所有 \(i\) 都有\(x_i \le \alpha^i < x_i+1\Longleftrightarrow x_i=\lfloor \alpha^i\rfloor.\)
再用 \(x_1=2\)：\(2=\lfloor \alpha\rfloor \Longleftrightarrow2\le \alpha <3.\)
所以每个合法序列都对应某个 \(\alpha\in[2,3)\)，且\(x_i=\lfloor \alpha^i\rfloor.\)
反过来，给定任意 \(\alpha\in[2,3)\)，定义 \(x_i=\lfloor \alpha^i\rfloor\)，则显然\(x_i^j \le \alpha^{ij} < (x_j+1)^i\)
从而题目不等式成立。并且因为 \(\alpha\ge2\)，有\(\alpha^i-\alpha^{i-1}=\alpha^{i-1}(\alpha-1)\ge 2^{i-1}>1(i\ge2),\) 所以 \(\lfloor \alpha^i\rfloor>\lfloor \alpha^{i-1}\rfloor\)，严格递增也自动满足。
结论： 合法序列与 \(\alpha\in[2,3)\) 产生的序列 \[ (2,\lfloor\alpha^2\rfloor,\dots,\lfloor\alpha^n\rfloor) \] 一一对应；因此 \(t(n)\) 就是当 \(\alpha\) 在 \([2,3)\) 连续变化时，产生的不同序列个数。
对任意 \(i\ge2\)，由 \(\alpha\in[2,3)\) 得\(2^i \le \alpha^i < 3^i\Longrightarrow2^i \le x_i=\lfloor\alpha^i\rfloor \le 3^i-1.\)
因此第 \(i\) 列可能取的整数一共有\((3^i-1)-2^i+1 = 3^i-2^i\)个；当 \(\alpha\) 增大时，\(x_i\) 会从 \(2^i\) 依次跳到 \(2^i+1,\dots,3^i-1\)。
跳变发生在 \(\alpha^i\) 穿过某个整数 \(m\) 的时刻，即\(\alpha = m^{1/i},\quad m=2^i+1,2^i+2,\dots,3^i-1.\)
因此第 \(i\) 列在区间 \((2,3)\) 内的“跳变点”个数\(a(i)\)是
\[a(i)= (3^i-1)-(2^i+1)+1=3^i-2^i-1.\]
令\(\displaystyle{S_i=\left\{m^{1/i}:2^i<m<3^i,m\in\mathbb Z\right\}}\)表示第\(i\)项的跳变点集合。
把所有列的跳变点放在一起：\(\displaystyle{S=\bigcup_{i=2}^n} S_i\)。当 \(\alpha\) 从 \(2\) 走到 \(3\)，每遇到一个 不同的 跳变点，序列就会发生变化一次，所以\(t(n)=1+|S|.\)
但不同 \((i,m)\) 可能给出同一个实数跳变点。例如\((8)^{1/2} = (64)^{1/4}=2\sqrt2,\) 这对应“同一个跳变点在不同列出现”，其本质是 完全幂导致的重复。
设一个跳变点写成最简的形式 \[ \beta = u^{1/d}, \] 其中 \(u\) 不是任何 \(k\ge2\) 次幂（即“幂指数为 1”），称 \(d\) 为它的“最小列号”。
那么这个 \(\beta\) 会出现在所有列号为 \(d\) 的倍数的列里：若 \(i=kd\)， \[ \beta = u^{1/d} = (u^k)^{1/i}, \] 因此它会在第 \(i\) 列的某个整数 \(m=u^k\) 处出现同一个跳变点。
也就是说：每个“原始跳变点”（最小列号为 \(d\)）会在集合 \(S_d,S_{2d},S_{3d},\dots\) 中反复出现。
令 \(u(d)\) 表示“最小列号恰为 \(d\) 的原始跳变点个数”。则第 \(i\) 列的跳变点数恰好是\(a(i)=\displaystyle{\sum_{d\mid i} u(d).}\)
令
\[ F(n)=\sum_{d=2}^n u(d)=|S| \]
即所有列号 \(\le n\) 的原始跳变点总数，那么 \(t(n)=1+F(n)\)。
考虑 \[ A(n)=\sum_{i=2}^n a(i). \]
从 \(u(d)\) 的角度看：一个最小列号为 \(d\) 的原始跳变点，会出现在列 \(d,2d,\dots,\lfloor n/d\rfloor d\)，一共出现 \(\lfloor n/d\rfloor\) 次，所以
\[ A(n)=\sum_{d=2}^n u(d)\Big\lfloor\frac{n}{d}\Big\rfloor. \]
而另一方面， $$ \[\begin{aligned} \sum_{k=1}^n F\left(\Big\lfloor\frac{n}{k}\Big\rfloor\right)&=\sum_{k=1}^n\sum_{d\le \lfloor n/k\rfloor} u(d)\\ &=\sum_{d=2}^n u(d)\left\lfloor\dfrac{n}{d}\right\rfloor. \end{aligned}\]$$
因此得到关键恒等式
\[ A(n)=\sum_{k=1}^n F\left(\left\lfloor\frac{n}{k}\right\rfloor\right). \]
把右边单独提出 \(k=1\) 的项就是 \(F(n)\)，于是 \[ F(n)=A(n)-\sum_{k=2}^n F\left(\left\lfloor\frac{n}{k}\right\rfloor\right). \]
由 \(a(i)=3^i-2^i-1\)，可得：\(\displaystyle{A(n)=\sum_{i=2}^n (3^i-2^i-1)=\frac{3^{n+1}+1}{2}-2^{n+1}-n}\)。
可见，这就是经典的数论分块求解。
令 \(N=10^{10},M=10^9\)，我们要求 \(t(N)\bmod M\)。
唯一麻烦是 \(A(n)\) 里有 \(\dfrac{3^{n+1}+1}{2}\)，但 \(2\) 在模 \(10^9\) 下不可逆。做法是：
在模 \(2M\) 下算\(3^{n+1}+1\pmod{2M}\)，它一定是偶数，于是可以先做整数除以 2，再对 \(M\) 取模，这样得到的就是 \(\bmod M\) 的正确结果。
于是，使用数论分块即可完成本题的高效计算。
代码
1 | from functools import lru_cache |