Project Euler 419
Project Euler 419
题目
Look and say sequence
The look and say sequence goes \(1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, \dots\)
The sequence starts with \(1\) and all other members are obtained by describing the previous member in terms of consecutive digits.
It helps to do this out loud:
\(1\) is ‘one one’ → \(11\)
\(11\) is ‘two ones’ → \(21\)
\(21\) is ‘one two and one one’ → \(1211\)
\(1211\) is ‘one one, one two and two ones’ → \(111221\)
\(111221\) is ‘three ones, two twos and one one’ → \(312211\)
\(\dots\)
Define \(A(n), B(n)\) and \(C(n)\) as the number of ones, twos and threes in the \(n\)’th element of the sequence respectively.
One can verify that \(A(40) = 31254, B(40) = 20259\) and \(C(40) = 11625\).
Find \(A(n), B(n)\) and \(C(n)\) for \(n = 10^{12}\).
Give your answer modulo \(2^{30}\) and separate your values for \(A, B\) and \(C\) by a comma.
E.g. for \(n = 40\) the answer would be \(31254,20259,11625\)
解决方案
Cosmological 定理 说明：当外观数列发展到足够大时，序列会“衰变”为若干个互不干扰的 原子串（atomic elements） 的拼接。论文介绍了这些原子串集合；这些原子来自一个有限集合（在只含数字 \(1,2,3\) 的情形下共有 \(92\) 个）。
换句话说，对足够大的 \(n\)，存在唯一的分解：\(a_n = E_{i_1}E_{i_2}\cdots E_{i_t},\)其中每个 \(E_i\) 都是固定的原子串，并且下一步外观变换满足：\(a_{n+1}=s(a_n)=s(E_{i_1})s(E_{i_2})\cdots s(E_{i_t}),\)也就是说原子之间不会在边界发生混合。
因此从某一项开始，整个问题转化为：追踪各原子出现次数的线性演化。
把 \(92\) 个原子编号为：\(E_0,E_1,\dots,E_{91}.\)
定义第 \(n\) 项的原子出现次数向量（列向量）\(\mathbf{v}_n\in\mathbb Z_{\ge 0}^{92}\)，其中\((\mathbf{v}_n)_i\)表示在\(a_n\)的分解中\(E_i\)出现次数.
对每个原子 \(E_j\)，它在一次外观变换后会衰变为若干原子拼接：\(s(E_j)=E_{t_1}E_{t_2}\cdots E_{t_r}.\)
于是存在一个固定的 \(92\times 92\) 转移矩阵 \(T\)，满足\(\mathbf{v}_{n+1}=T\mathbf{v}_n,\)并且矩阵元素\(T_{i,j}\)含义为：在\(s(E_j)\)中原子\(E_i\)的出现次数。从而得到闭式：\(\mathbf{v}_n=T^{n-n_0}\mathbf{v}_{n_0}.\)
对每个原子 \(E_i\)，预处理它内部数字 \(1,2,3\) 的出现次数：\(\mathbf{d}_i=(d_{i,1},d_{i,2},d_{i,3}),\)其中\(d_{i,j},j\in\{1,2,3\}\)表示\(j\)在原子\(E_i\)出现的次数。
则第 \(n\) 项中数字统计为
\[ \begin{pmatrix} A(n)\\B(n)\\C(n) \end{pmatrix} =\sum_{i=0}^{91}(\mathbf{v}_n)_i \begin{pmatrix} d_{i,1}\\d_{i,2}\\d_{i,3} \end{pmatrix}. \]
外观数列前几项为：\(1,11,21,1211,111221,312211,13112221,1113213211,\dots\)，从已知的原子分解表可得到第 \(8\) 项（即 \(a_8\)）的原子分解为两种原子之和：\(a_8=E_{\text{Hf}},E_{\text{Sn}}.\)
在编号体系下对应两个下标（用 \(0\) 开始计数）：\(\text{Hf}=23,\text{Sn}=38.\)因此初始向量为：\((\mathbf{v}_8)_{23}=1,(\mathbf{v}_8)_{38}=1\)，\(\mathbf{v}_8\)的其余位置是\(0\)。对于目标 \(n=10^{12}\)，于是\(\mathbf{v}_{n}=T^{n-8}\mathbf{v}_8.\)
综上即可计算出\(A(n),B(n),C(n)\)的值。
代码
1 | import numpy as np |