数字生成器

一个数字生成器，生成规则如下：第$1$次生成一个数$x$，以后每次生成的结果是将上一次生成的每一个数$x$生成两个数，一个是$-x$，另一个是$x+3$．设第$n$次生成的数的个数为$a_n$，则数列$\{a_n\}$的前$n$项和$S_n=$_______；若$x=1$，前$n$次生成的所有数中不同的数的个数为$T_n$，则$T_n=$_______．

分析与解　$2^n-1$；$\begin{cases} \dfrac 12n(n+1),&n\leqslant 4,\\ 4n-6,& n\geqslant 5.\end{cases}$

关键是证明当$n\geqslant 5$时，$T_n-T_{n-1}=4$．

法一　记$P$为取相反数的操作，$Q$为加$3$的操作，例如用$PQQ$来表示数字$5$的生成操作，简记为$PQ^2$． (1) 容易知道第$n$($n\geqslant 2$)次生成数字后，所产生的数字在区间$\left[Q^{n-2}P,Q^{n-1}\right]$内，即为$[-3n+5,3n-2]$内．也就是说每次操作最多在两端各自新生成$3$个连续整数．

(2) 由于$1$模$3$余$1$，而$P,Q$操作都不能使得该操作数由不能被$3$整除的数变为能被$3$整除的，所以每次操作最多新产生$4$个数；

(3) 在第$n$次生成数字后，会在两端产生新数字$Q^{n-2}P$和$Q^{n-1}$；接下来证明$PQ^{n-2}$和$PQ^{n-3}P$也是新数字：
首先，若一个数可以通过$k$($k<n-1$)次$P$或$Q$操作生成，那么它必然不在新生成的数字之列；
其次，对于$n-2$次$P$或$Q$操作来说，$PQ^{n-3}$是所能生成的除$Q^{{n-2}}$外的最大的数，因此$PQ^{n-3}Q$和$PQ^{n-3}P$分别是$n-1$次$P$或$Q$操作所能产生的除$Q^{n-1}$和$Q^{n-2}P$以外的最大的数和最小的数．
综上所述，结论得证．

注　在$n-1$次操作后，$[Q^{n-2}P,Q^{n-1}]=[-3n+5,3n-2]$中除了$3$的倍数的坑不可能填上数外，就只有两个空有待下次生成，一是$Q^{n-2}P+2$，另一个是$Q^{n-1}-2$，这两个数必须经过$n$次操作才可以产生，为$PQ^{n-2}P$与$PQ^{n-1}$，事实上，每次操作后都会留下这两个坑等待下次操作时填补．所以从第$4$次操作开始，每次操作都会产生$4$个新数．

法二　我们把每次生成过程中产生新的数的分支称为“有价值的”，可以发现规律：当$n\geqslant 4$时，所有左支在贡献一次价值之后就无法带来任何价值了．

我们可以用这种方法选出所有有价值的分支：每个新生节点(代表一个新生成的数)每发一次芽(也就是生成两个新数)后马上把它的左支砍掉．这样做的结果就是每次操作都生成$4$个新数，而这$4$个新数中只有$2$个有“繁殖”能力，它们能在下次操作用生成另外$4$个新数，这样我们就得到了通项公式．

通过这种方法，很显然“被砍掉”的数都是无价值的，下面证明新生成的数都是有价值的．

可以写出第$n$($n\geqslant 4$)次操作后新生成的$4$个数的通项公式： $$10-3n,3n-7,5-3n,3n-2.$$ 如果$10-3n$没有价值，设它第一次出现时对应的操作数为$m$($0<m<n$)，则$10-3n$是以下$4$个数之一： $$10-3m,3m-7,5-3m,3m-2,$$ 于是以下$4$个等式之一成立： $$m=n,3(m+n)=17,3(n-m)=5,m+n=4,$$ 矛盾．因此$10-3n$有价值．类似的可以证明$3n-7,5-3n,3n-2$也有价值．