KPnd序列

KPnd序列，是318`4定义的序数表示法，用一个自然数组表示序数。

1.概念和定义

   不降格的KP序列（Keidonxi's Polynomial Sequence with no debasing）简称KPnd，其中Keidonxi是318`4 10年前用拼音推出的外文人名，Polynomial是多项式，no debasing代指没有“降格”这个操作，Sequence即序列；这个名字中，Polynomial是唯一能体现序列特征的：展开KP序列的依据是一组多项式。

   KP序列是一系列正在发展的序列，包括初始KP序列(initial KP)、KPnd序列、KDP序列(Keidonxi's Diagonalized Polynomial，定义已基本完善)、TKP序列(Triple KP，现处于原理研究阶段)、YKP(现处于原理理解阶段)、LKP序列(Lifting KP，现处于计划阶段)等。

   以下为KPnd序列的定义，不是很严谨（一个序列的展开取决于其他序列的展开）：

2.基本原理

  0-Y序列有一个特点：一个序列的展开可以由它的阶差序列决定。例如1,4,6,10，阶差序列为1,3,2,4；1,3,2,4=1,3,2,3,4,5,6,7,...，所以1,4,6,10=1,4,6,9,13,18,24,31,...。其中的核心是令某项(记作aᵢ)等于它的父项(aₚ₍ᵢ₎)加上阶差(dᵢ)

   而KP序列中一个序列的展开是由多个序列共同决定的，这里面的核心是令某项(aᵢ)等于把它的父项(aₚ₍ᵢ₎)代入一个多项式函数，即aᵢ=Πᵢ(aₚ₍ᵢ₎)，其中Πᵢ(x)是一个多项式函数。

   例如1,2,4,9,20，2=1×1+1，4=2×2，9=4×2+1，20=9×2+2，于是组成了一次项系数序列(记作Q₁)0,1,2,2,2，常数项序列(记作Q₀)0,1,0,1,2，于是在特定条件下展开这两个序列，最后返回原本序列。Q₁的末项加1然后展开：0,1,2,2,3=0,1,2,2,2,2,2,2,...；Q₀直接展开：0,1,0,1,2=0,1,0,1,1,1,1,1,...，返回得到1,2,4,9,19,39,79,159,...

   但是这个特定条件比较复杂，涉及很多新定义的概念。

   对于一个包含x+1项的序列A=(a₀,a₁,a₂,a₃,...,aₓ)，aᵢ的父项是aₚ₍ᵢ₎（整数i∈[0,x)）

   首先，定义多项式的系数：令aᵢ=Πᵢ(aₚ₍ᵢ₎)，其中Πᵢ(x)=q₀ᵢ+q₁ᵢx+q₂ᵢx²+q₃ᵢx³+...；对任意自然数k，整数qₖᵢ∈[0,aₚ₍ᵢ₎)。Πᵢ还同时表示列向量，即第i项的系数向量。

   向量组Q=(Π₀,Π₁,Π₂,...,Πₓ)，是一个矩阵，称为子序列矩阵。子序列矩阵又由多个行向量组成：Q₀,Q₁,Q₂,Q₃,...，即Qₜ=(qₜ₀,qₜ₁,qₜ₂,qₜ₃,...,qₜₓ)，行向量Qₜ称为序列A的t层子序列。

    一个序列有无穷多个子序列，但是非零向量的子序列只有有限个。    定义项的等级比较：对于两个项aᵢ和aₖ，如果，那么称“aₖ在s层比aᵢ高级”。

3.阶差序列

   在1,2,4,9之前，KP序列和1-Y序列是完全相同的，只是KP序列多了一个补层的行为。

   以1-Y的典例1,2,4,8,10,8为例，展开KPnd(1,2,4,8,10,8)：

   因为2=1×1+1，4=2×2+0，8=4×2+0，10=8×1+2，8=4×2+0，所以对于1,2,4,8,10,8，Q₀=0,1,0,0,2,0，Q₁=0,1,2,2,1,2，并且P=(0,0,1,2,3,2)（记住首项是第0项）。

   这里首先就会遇到两个规定：如果一个项aᵢ=1，那么它对应的多项式Πᵢ(x)=0（这是两个违反多项式运算的地方之一），且规定父项为第0项；而如果一个项aᵢ的父项是1，那么它对应的多项式Πᵢ(x)=x+(aᵢ-1)。这才使得Q₀=0,1,0,0,2,0，Q₁=0,1,2,2,1,2而不是Q₀=1,0,0,0,2,0，Q₁=?,2,2,2,1,2。

   接下来是可计算化。从逻辑上讲，一个有x+1项的序列(末项为第x项)，它的展开式的第x项一定比展开前的第x项的值少1，但是在1,2,4,8,10,8中，Q₀的末项是0，怎么少1呢？因此要有一个运算，让Q₀的末项不是0。    在1,2,4,8,10,8中，末项(a₅=8)的父项是4，那么让q₁₅减1，q₀₅加4，整个序列的值是不变的，只是从8=4×2+0改成了8=4×1+4。于是现在Q₀=0,1,0,0,2,4，Q₁=0,1,2,2,1,1，可以按照逻辑上的q₀₅-1来展开了。这个让Q₀的末项不再是0的过程称为可计算化。

   然后是一个比较复杂的行为，补层。先在子序列中找到末项的父项及其之前的连续的0，也就是Q₀=0,1,0,0,2,4和Q₁=0,1,2,2,1,1。如果这个0是序列的首项，那么不管它，也就是不用管Q₁的这个0，只需要注意Q₀的这两个0。它们分别在0层子序列的第2项和第3项，那么比较a₂,a₃和末项在1层的级别，显然，这两个项的级别都比末项高；所以，q₁₂和q₁₃都减1（如果是末项级别更高或者级别相等则不需要减1）；接下来是补层的核心：把第i+1项的0改成aᵢ。

   在这样的一系列操作下，Q₀变成了0,1,2,4,2,4，Q₁变成了0,1,1,1,1,1。在这之后，要展开的序列就变成了0,1,2,4,2,4和0,1,1,1,1,2，显然后者等于0,1,1,1,1,1,1,1,1,1,...。实际上任何小于1,2,4,9的序列中，Q₁的展开式都是0,1,1,1,1,1,1,1,1,1,...，Q₀就是这个序列的阶差。

   于是，1,2,4,8,10,8的展开问题就转化为了0,1,2,4,2,4怎么展开。    和1-Y一样，0,1,2,4,2,4也可以进一步转化为0,0,1,2,1,2的展开（注意末项的父项是a₂）。末项与其父项的差是1，可以展开：0,0,1,2,1,1,2,1,1,2,1,1,2,1,...，注意a₄的父项是a₁。    回到0,1,2,4,2,4，它等于0,1,2,4,2,3,5,2,4,6,2,5,7,2,...，由于此时a₄的父项是a₁，比a₂靠前，a₄₊₃ₙ的父项始终是a₁。

   最后回到1,2,4,8,10,8，即1,2,4,8,10,7,12,14,11,17,19,16,23,25,...。

   其他的1,2,4,9之前的KPnd序列也是类似的，可以用完全相同的1-Y的规则展开。

4.阶斜率序列

   大于等于1,2,4,9，小于1,2,5的KPnd序列称为阶斜率序列，也可以称为阶线性序列、阶一次序列，因为每一项对应的多项式函数都是一次函数（不叫“阶商序列”是因为名称和后面的阶二次序列等无法衔接，同时曾经的KD序列占用了该名称）。

   因为2×2等于4，2²也等于4，1,2,5只能视为阶二次序列的开端，阶斜率序列就只能从1,2,4,9开始了。并且还要规定，当aᵢ=4且aₚ₍ᵢ₎=2时，Πᵢ(x)=2x而不是x²。

    在定义中有一个“占位运算”，实际上就是用来让高级项的低级子序列不提升的。其中最小的例子是1,2,4,10,7。

   在1,2,4,10,7中，Q₀=0,1,0,2,3，Q₁=0,1,2,2,1，末项的多项式函数是一个一次函数，记这个表达式的展开层次s=1。如果一个项在s层比末项高级，那么可以简称为“这个项比末项高级”

   补层后得到Q₀=0,1,0,2,3，Q₁=0,1,2,2,1，末项的父项是a₂。这里的补层又要注意一点：如果待补层项的序号等于p(p(...(p(x))...))（记作pᶜ(x)），并且存在第pᵏ(x)项(k<c)，这一项和待补层项都比末项高级，那么不需这个补层。所以此时的Q₀并不是0,1,2,2,3，Q₁也不是0,1,1,2,1。

   现在要展开0,1,0,2,3和0,1,2,2,2。显然后者等于0,1,2,2,1,2,2,1,2,2,...。因为任何项的父项都不能比这个项高级，所以0,1,0,2,3中a₄的父项是a₁。但是a₃的父项是a₂，比a₁靠后；这样下来0,1,0,2,3应该是0,1,0,2,2,0,3,3,0,4,...。可是实际上它等于0,1,0,2,2,0,2,3,0,2,...，这是因为q₀₃=2对应的a₃，是比末项高级的，这不能被提升。

   于是展开式的Q₀=0,1,0,2,2,0,2,3,0,2,...，Q₁=0,1,2,2,1,2,2,1,2,2,...。为了便于逐项对应，一般会用矩阵Q表示，即Q

   故1,2,4,10,7=1,2,4,10,6,12,26,15,30,62,...

   现在来看1,2,4,9,12的展开式：    Q     即1,2,4,9,12=1,2,4,9,11,22,45,48,96,193,...

   那么这个展开式的前6项，1,2,4,9,11,22，怎么展开呢？

   很快计算出Q₀=0,1,0,1,2,11，Q₁=0,1,2,2,1,1（已可计算化）。0,1,2,2,1,2很容易展开，就是0,1,2,2,1,1,1,1,1,1,...；而0,1,0,1,2,11，则需要进一步求子序列。

   所以在A=0,1,0,1,2,11的情况下，Π₅(x)等于什么？是x³+x+1吗？如果是这样。那么Q₀=0,0,0,0,1,1，Q₁=0,0,0,0,1,1，Q₂=0，Q₃=0,0,0,0,0,1，这个大小和1,2,11是相同的，这将形成一个超大的循环定义。那么，应该如何解决？

   附加降格的作用体现出来了：子序列的末项只能比原序列的末项(在0层)低级。这句话的意思是：在1,2,4,9,11,22中，Π₅(x)=x+11；那么在0,1,0,1,2,11中，Π₅(x)要满足。所以这个Π₅(x)只能等于11（因为函数的级别是逐级下降的，所以降低到满足这个不等式后就不用继续降低了），常数函数已经是多项式函数的最低级别。

   现在，0,1,0,1,2,11，Q₀=0,0,0,0,1,11，Q₁=0,0,0,0,1,0，于是展开为Q₀=0,0,0,0,1,10,19,28,37,...，Q₁=0,0,0,0,1,0,0,0,0,0,...，得到0,1,0,1,2,11=0,1,0,1,2,10,19,28,37,...。

    回到1,2,4,9,11,22，Q₀=0,1,0,1,2,10,19,28,37,...，Q₁=0,1,2,2,1,1,1,1,1,1,...，故1,2,4,9,11,22=1,2,4,9,11,21,40,68,115,...

   1,2,4,10等于什么？可以发现，Q₀=0,1,0,2，Q₁=0,1,2,2。在这里，补层又回来了。将q₀₂改为a₁，由于a₂不比末项高级，q₁₂不变，即Q₀=0,1,2,2，Q₁=0,1,2,2。     0,1,2,2=0,1,2,1,2,1,2,1,2,...，0,1,2,3=0,1,2,2,2,2,2,2,2,...，注意这里分别展开了(0,1,2,2)[3]和(0,1,2,3)[6]，在存在补层的情况下，不同子序列的基本列长度单位可能是不同的。    于是1,2,4,10=1,2,4,9,20,41,84,169,340,...

   再看向1,2,4,10,12的展开式：    Q     即1,2,4,10,12=1,2,4,10,11,22,46,47,94,190,...

   这个展开式的前7项，1,2,4,10,11,22,46，展开时应该如何补层？

   1,2,4,10,11,22,46，Q₀=0,1,0,2,1,0,2，Q₁=0,1,2,2,1,2,2，需要给q₀₅补层。根据前面的规则，q₀₅应该改为a₄，但是0,1,0,2,1,11,2显然也是无法展开的。    q₀₅=0，q₁₅=2，现在要找到另一个类似的q₀ᵢ=0，q₁ᵢ=2的项，如果这个项不存在，就找比a₅高级但q₀ᵢ=0的项；当然，这个项是存在的，就是a₂。因此，替换掉q₀₅的不是a₄，而是a₁。所以，Q

   故1,2,4,10,11,22,46=1,2,4,10,11,22,45,92,185,372,745,1492,...

   以上基本就是阶斜率序列会遇到的所有情况了。在1,2,4,13之前，Q₁的展开式一定是PrSS的表达式。而1,2,4,13，Q₀=0,1,0,1展开为0,1,0,0,0,0,0,...，Q₁=0,1,2,3展开为0,1,2,3,4,5,6,...，所以1,2,4,13=1,2,4,12,48,240,1440,...呈现出阶乘的形式。阶斜率呈现等差数列，或者说阶斜率的阶差是常数，把阶差运算记作q⁰，阶斜率运算记作q¹，这个式子可以表述为q⁰(q¹)=常数。

   接下来是1,2,4,16,113： Q ，即1,2,4,16,113=1,2,4,16,112,1232,19712,433664,12576256,...，也就是q⁰(q⁰(q¹))=常数。1,2,4,16,128,1921（Q₁=1,2,4,8,15）展开式即为q⁰(q⁰(q⁰(q¹)))=常数。对q⁰(q¹), q⁰(q⁰(q¹)), q⁰(q⁰(q⁰(q¹)))取对角化，可以得到q¹(q¹)=常数：1,2,4,16,129=1,2,4,16,128,2048,65536,4194304,…（Q₁=1,2,4,8,16,32,64,...）。

   最后，q¹(q¹(...(q¹(q¹))...))=常数 的极限，就是阶斜率序列的极限：1,2,4,16,256,65536,4294967296,...

5.完整的序列

   阶二次序列开始于1,2,5，Q₀=0,0,1，Q₁=0,0,0，Q₂=0,1,1，展开为Q₀=0,1,0,0,0,0,...，Q₁=0，Q₂=0,1,1,1,1,1,...；1,2,5=1,2,4,16,256,65536,...

   这里可以看到，我强行让2的Π(x)=x²，这里也违反了多项式运算。实际上这里的Π(x)取决于第2项的值，当a₂≥5时，Π₁(x)=x^[log₂(a₂-1)]（如果a₂经过附加降格后Π₁(x)变成了x，那么改为x+1）。这么多特殊的规定，都是为了对抗同一个噩梦般的特性：2×2=2²

   在1,2,5之后，基本上不会遇到新的情况了。

   1,2,5,25，Q=，这里的可计算化，本来需要q₁₃的值减1，但是q₁₃也是0，所以需要q₂₃的值减1，q₁₃的值加5，再让q₁₃的值减1，q₀₃的值加5，即Π₃(x)=4x+5。接下来： Q=即为 故1,2,5,25 =1,2,5,24,576,331777,2654224,7044905042176,49630687053276828338814977,...

   对于1,2,5,24,576，Q=补层为展开为 （完整的展开式是什么就不算了）

   在1,2,5之后，可能会出现多次补层，或者跨层次的可计算化，同时2×2=2²造成的负面作用也明显体现出来，让规则变得复杂。

    1,2,8：Q=展开为，1,2,7,65,4423,19580625,...    1,2,8,193：Q= 展 开 为          ，即q⁰(q²)=常数    1,2,8,256,2049：Q=展开为   ，即q¹(q²)=常数    1,2,8,257：Q=，即q²(q²)=常数    1,2,8,512,131073：Q=，即q²(q²(q²))=常数

    于是，阶三次序列出现：1,2,9=1,2,8,512,2²⁷,2⁸¹,2²⁴³,...。后面就不一一列举了

   1,2,16,12289（q⁰(q³)=常数）；1,2,16,16384,2⁴⁵+1（q¹(q³)=常数）；1,2,16,16385（q²(q³)=常数）；1,2,16,32769（q³(q³)=常数）；1,2,16,65536,2⁶³+1（q³(q³(q³))=常数）

   1,2,17：q⁴=常数    1,2,33：q⁵=常数    1,2,65：q⁶=常数

   最后，KPnd序列的极限，1,2,ω形成。1,2,ω的基本列是1,2；1,2,4；1,2,4,9；1,2,5；1,2,9；1,2,17；1,2,33；...