Project Euler 570
Project Euler 570
题目
Snowflakes
A snowflake of order \(n\) is formed by overlaying an equilateral triangle (rotated by \(180\) degrees) onto each equilateral triangle of the same size in a snowflake of order \(n-1\). A snowflake of order \(1\) is a single equilateral triangle.
Some areas of the snowflake are overlaid repeatedly. In the above picture, blue represents the areas that are one layer thick, red two layers thick, yellow three layers thick, and so on.
For an order \(n\) snowflake, let \(A(n)\) be the number of triangles that are one layer thick, and let \(B(n)\) be the number of triangles that are three layers thick. Define \(G(n) = \gcd(A(n), B(n))\).
E.g. \(A(3) = 30, B(3) = 6, G(3)=6\)
\(A(11) = 3027630, B(11) = 19862070, G(11) = 30\)
Further, \(G(500) = 186\) and \(\sum_{n=3}^{500}G(n)=5124\)
Find \(\displaystyle \sum_{n=3}^{10^7}G(n)\).
解决方案
从阶数 \(n\) 到 \(n+1\) 的构造具有三向对称性，并且厚度变化只会发生在不同厚度区域的交界附近。为了只抓住与 \(A(n)\)、\(B(n)\) 相关的信息，我们只关心厚度为 \(1\) 或 \(3\) 的小三角形，并按它们与更厚区域的相邻边数分类。
厚度为 \(1\) 的小三角形，其三条边中有多少条与厚度为 \(2\) 的区域相邻，只可能是 \(1,2,3\) 三种：\(A_1(n)\)：厚度 \(1\)，且恰有 \(1\) 条边邻接厚度 \(2\)；\(A_2(n)\)：厚度 \(1\)，且恰有 \(2\) 条边邻接厚度 \(2\)；\(A_3(n)\)：厚度 \(1\)，且 \(3\) 条边都邻接厚度 \(2\)。显然
\[ A(n)=A_1(n)+A_2(n)+A_3(n). \]
同理，厚度为 \(3\) 的小三角形，关心其三条边中有多少条与厚度 \(\ge 4\) 的区域相邻，只可能是 \(0,1,2,3\) 四种： \(B_0(n),B_1(n),B_2(n),B_3(n)\)：厚度 \(3\)，且分别有 \(0,1,2,3\) 条边邻接厚度 \(\ge4\)。于是
\[ B(n)=B_0(n)+B_1(n)+B_2(n)+B_3(n). \]
对每一种局部类型，把它在一次对所有同向三角形叠加旋转三角形的操作后所产生/转化出的局部类型逐一数出来（利用三向对称，实际上只需画出代表性的局部邻域即可）。由此得到如下线性递推：
蓝色三类： \[ \begin{aligned} A_1(n) &= 3A_1(n-1)+A_2(n-1),\\ A_2(n) &= 2A_1(n-1)+2A_2(n-1),\\ A_3(n) &= A_2(n-1)+3A_3(n-1). \end{aligned} \]
黄色四类： \[ \begin{aligned} B_0(n) &= A_1(n-1)+2A_2(n-1)+3A_3(n-1),\\ B_1(n) &= 6B_0(n-1)+3B_1(n-1)+B_2(n-1),\\ B_2(n) &= 2B_1(n-1)+2B_2(n-1),\\ B_3(n) &= B_2(n-1)+3B_3(n-1). \end{aligned} \]
初始条件可由低阶图形直接数出：阶数 \(1\)：只有一个厚度 \(1\) 三角形，且并不存在厚度 \(2\) 邻域结构，因此更方便从 \(n=2\) 作为进入稳定分类后的起点；阶数 \(2\)：蓝色只有外侧 \(6\) 个且每个只邻接一条厚度 \(2\) 边，因此\(A_1(2)=6,A_2(2)=0,A_3(2)=0,\)且此时没有厚度 \(3\)：\(B_0(2)=B_1(2)=B_2(2)=B_3(2)=0.\)
接下来我们求出\(A\)的闭式。先解前三式。注意到\(A_1(n)-A_2(n)=(3A_1(n)+A_2(n))-(2A_1(n)+2A_2(n))=A_1(n-1)-A_2(n-1),\) 所以 \(A_1(n)-A_2(n)\) 为常数。由 \(n=2\) 得\(A_1(n)-A_2(n)=6,(n\ge2).\)
用第二式得：\(A_2(n)=2A_1(n-1)+2A_2(n-1)=2(A_2(n-1)+6)+2A_2(n-1)=4A_2(n-1)+12.\)结合 \(A_2(2)=0\)，得
\[A_2(n)=12\sum_{k=0}^{n-3}4^k=12\cdot\frac{4^{n-2}-1}{4-1}=4^{n-1}-4.\]
于是
\[A_1(n)=A_2(n)+6=4^{n-1}+2.\]
再解第三式：\(A_3(n)=A_2(n-1)+3A_3(n-1), A_3(2)=0.\)展开求和：
\[\begin{aligned} A_3(n)&=\sum_{j=2}^{n-1}3^{n-1-j}A_2(j)\\ &=\sum_{j=2}^{n-1}3^{n-1-j}(4^{j-1}-4)\\ &=(4^{n-1}-4\cdot3^{n-2})-2(3^{n-2}-1)\\ &=4^{n-1}-6\cdot3^{n-2}+2. \end{aligned}\]
最终
\[ \begin{aligned} A(n)&=A_1(n)+A_2(n)+A_3(n)\\ &=(4^{n-1}+2)+(4^{n-1}-4)+(4^{n-1}-6\cdot3^{n-2}+2)\\ &=3\cdot4^{n-1}-2\cdot3^{n-1}. \end{aligned} \]
接下来我们求出\(B\)的闭式。由定义递推：\(B_0(n)=A_1(n-1)+2A_2(n-1)+3A_3(n-1).\)代入上节结果（对 \(n\ge3\)）：
\[ \begin{aligned} B_0(n) &=(4^{n-2}+2)+2(4^{n-2}-4)+3(4^{n-2}-6\cdot3^{n-3}+2)\\ &=6\cdot4^{n-2}-18\cdot3^{n-3}\\ &=6\bigl(4^{n-2}-3^{n-2}\bigr). \end{aligned} \]
令\(S(n)=B_1(n)+B_2(n), D(n)=B_1(n)-B_2(n).\)由递推：
\[ \begin{aligned} D(n) &= B_1(n)-B_2(n) = \bigl(6B_0+3B_1+B_2\bigr)-\bigl(2B_1+2B_2\bigr)=D(n-1)+6B_0(n-1),\\ S(n) &= B_1(n)+B_2(n) = \bigl(6B_0+3B_1+B_2\bigr)+\bigl(2B_1+2B_2\bigr)=4S(n-1)+D(n-1)+6B_0(n-1). \end{aligned} \]
可知，第一行给出\(D(n)-D(n-1)=6B_0(n-1),\)所以第二行可化为\(S(n)=4S(n-1)+D(n).\)又 \(B_1(2)=B_2(2)=0\)，故 \(S(2)=D(2)=0\)。
先解 \(D(n)\)。由 \(B_0(n-1)=6(4^{n-3}-3^{n-3})\)，得
\[ D(n)=\sum_{t=3}^{n}6B_0(t-1)=\sum_{t=3}^{n}36(4^{t-3}-3^{t-3}) =12\cdot4^{n-2}-18\cdot3^{n-2}+6. \]
再解 \(S(n)=4S(n-1)+D(n)\)，展开：\(\displaystyle S(n)=\sum_{t=3}^{n}4^{n-t}D(t).\)将 \(D(t)=12\cdot4^{t-2}-18\cdot3^{t-2}+6\) 分项求和，可得
\[ S(n)=(12n-76)\cdot4^{n-2}+54\cdot3^{n-2}-2. \]
于是 \[ B_1(n)=\frac{S(n)+D(n)}2=(6n-32)\cdot4^{n-2}+18\cdot3^{n-2}+2, \] \[ B_2(n)=\frac{S(n)-D(n)}2=(6n-44)\cdot4^{n-2}+36\cdot3^{n-2}-4. \]
由递推：\(B_3(n)=B_2(n-1)+3B_3(n-1)\)整理得到
\[ B_3(n)=(6n-68)\cdot4^{n-2}+(4n+10)\cdot3^{n-1}+2. \]
因此
\[ B(n)=B_0(n)+B_1(n)+B_2(n)+B_3(n)=(18n-138)\cdot4^{n-2}+(4n+26)\cdot3^{n-1}. \]
接下来化简\(G(n)\)。由闭式：\(A(n)=3\cdot4^{n-1}-2\cdot3^{n-1}=12\cdot4^{n-2}-6\cdot3^{n-2}=6(2\cdot4^{n-2}-3^{n-2}).\)设\(X(n)=2\cdot4^{n-2}-3^{n-2}.\)同理\(B(n)=(18n-138)\cdot4^{n-2}+(4n+26)\cdot3^{n-1}=6((3n-23)\cdot4^{n-2}+(2n+13)\cdot3^{n-2}).\)
设\(Y(n)=(3n-23)\cdot4^{n-2}+(2n+13)\cdot3^{n-2}.\)则\(G(n)=\gcd(A(n),B(n))=6\gcd(X(n),Y(n)).\)接下来用一次欧几里得算法的线性组合消去 \(4^{n-2}\)：
\[ \begin{aligned} 2Y(n)-(3n-23)X(n) &=2\Bigl((3n-23)\cdot4^{n-2}+(2n+13)\cdot3^{n-2}\Bigr)-(3n-23)\Bigl(2\cdot4^{n-2}-3^{n-2}\Bigr)\\ &=\Bigl(4n+26+3n-23\Bigr)\cdot3^{n-2} =(7n+3)\cdot3^{n-2}. \end{aligned} \]
因此\(\gcd(X(n),Y(n))=\gcd\bigl(X(n),(7n+3)\cdot3^{n-2}\bigr).\)又 \(X(n)\equiv 2\pmod 3\)，所以 \(\gcd(X(n),3)=1\)，从而 \(\gcd(X(n),3^{n-2})=1\)。于是\(\gcd(X(n),Y(n))=\gcd\bigl(X(n),7n+3\bigr).\)最终得到极简形式：
\[ G(n)=6\cdot \gcd(2\cdot4^{n-2}-3^{n-2},7n+3). \]
代码
1 |
|