@jungleford/math-folding-doc v0.0.1

Background: 对折序列问题（Number Folding Problem）

(Chinese edition)

故事的起因是在一个同学微信群里有大佬抛出一道据说是奥数题，就是下面这个——

虽然问题本身很容易理解，不过名不正则言不顺，首先需要定义一些概念。以下命名皆为本人自行命名，未查证在数学里的标准命名方式，未必规范严格，可能有所出入：

• 轮（Turn）：经过一系列操作使对象达到与操作前“自相似”的状态，我们称为“一轮”，每一轮都有着相同的操作序列。如一张纸条从右往左对折，成为宽度减半，厚度加倍的“纸条”，这算作一轮；一张正方形的纸，从下往上对折，然后从右往左对折，成为面积1/4，厚度4倍的“纸”，这也算作是一轮。
• 步（Step）。每一轮操作可以细分成若干步，每一步即为一次对折操作。完成整个折叠过程的总“步数”简记为s。
• 次（Power）：或称“次数”，“幂次”，简记为k。显然，“幂次”就是“轮数”（count of turns）。但“次数”却未必等于“步数”（count of steps），当且仅当——见如下“阶”的定义——一阶情况下，“次数”才等于“步数”。
• 阶（Order）：问题的“维数”（dimension），简记为r。如纸条的对折，称为“一阶”的；而正方形纸的对折，称为“二阶”的。
• 基（Base）：以2为底，阶数为指数的幂次数（此为一般数学意义上的幂次，与前面所定义的“幂次”有所区别），简记为b。
• 元（Unit）：即写在操作对象上的那些自然数。事实上未必一定要是数字，任何可数有序的符号元素（组成“全序集”）皆可，为方便叙述与理解该问题，我们在此仅采用从1开始的连续自然数序列。数字的总数称为“元数”，简记为n。
• 堆（Pile）：初始状态下，每个数字单独组成一个堆，共n堆。当每一步对折操作结束后，堆数减半；而当每一轮操作结束后，堆数减少为前一轮的1/b。

位置与值：

• 记为对折后数字x在最终序列的位置，也称作“点位”。
• 记为对折后位置p上的数字，称为位p上的“值”。

一些显见的结论：

• 。一阶对折的基为2，二阶对折的基为4（），依此类推。
• 幂次等于轮数k。只有一阶对折情形下，“次”等于真实对折的次数（即“步数”），即。高于一阶，。如二阶对折实际要折叠2k次。
• 每一步对折操作结束后，堆数减半；每一轮操作结束后，堆数减少为前一轮的。
• 。如“一阶二次”是4个数（也称为一阶四元对折），“二阶三次”是64个数（也称为二阶64元对折），等等。
• 位置P(x)与值V(x)互为逆函数。

一些不那么显见的结论：

• 数字和位置的对称性。见以下讨论。

先从简单的“一阶对折问题”（First Order Folding）入手。

一阶对折（First Order Folding）

问题

一张纸条，均分成格，每个格子内按从左到右顺序写下自然数序列1，2，3，……，n

将纸条从右往左不断对折（共k步），直至剩下一个格子，求： 1) 最后从下往上数字的序列 1) 数字x（）的最终位置 1) 最终序列中位置p的数字

一阶对折的对称性

对折前显然是对称，然而经过k轮对折后，依然是对称的！ 1) 给定同一个x，有 1) 1) 1) 如果我们把最终序列重新写在另一张白纸条上的话，又对这张新纸条进行对折操作，最终你又能重新得到原始的自然数序列1，2，3，……，n

头部稳定性

第t轮对折得到的个堆中，前面的一半，即前个堆，在下一次第t+1轮对折后保持本堆自身的序列不变。特别地，第一堆的顺序绝对稳定不变。这话有点拗口，但是结果却是很直观的：比如一阶三次对折的最后一个数是8，在第一次对折后它成了第一堆（此时为1，8两个元素）的第二个元素，此后，无论多少次对折，它永远是第二个元素，直到结束。这个结论对下面的推导很重要。

一阶对折的菊形增长规律

我们观察从一阶一次至一阶五次的最终序列——

1 2

1 4 3 2

1 8 5 4 3 6 7 2

1 16 9 8 5 12 13 4 3 14 11 6 7 10 15 2

1 32 17 16 9 24 25 8 5 28 21 12 13 20 29 4 3 30 19 14 11 22 27 6 7 26 23 10 15 18 31 2

再对这个表稍微整理一下——

1                                                                                    2      <- k=1

1                                        4 3                                         2      <- k=2

1                  8 5                   4 3                   6 7                   2      <- k=3

1       16 9       8 5       12 13       4 3       14 11       6 7       10 15       2      <- k=4

1 32 17 16 9 24 25 8 5 28 21 12 13 20 29 4 3 30 19 14 11 22 27 6 7 26 23 10 15 18 31 2      <- k=5

这个排列很有趣，我们至少可以观察到这么几点（当然，这个规律需要数学上的严格证明）： 1) 保序性：在一阶k次序列在一阶k+1次（以及以后各次）中相对顺序保持不变。 1) 等距分布：k次序列除去头尾两个数字（即1和2），其他数字以两两为一个单元（以下简称“块”，block），在高于k次的序列中保持等距。 1) 菊形增长：k+1次序列总是在k次序列的每两个“块”之间插入一个新的“块”，然后这个新的块将成为k+2次序列的“种子”。如果我们将上图的所有数字按等距分布，居中排列的话，这个图从上往下看就犹如一个层层嵌套不断绽放的菊花，因此我称之为“菊形增长”。

块和锚点

下面我们看看从已知的k次序列中的一个数字及其位置，如何推导出：

首先，在进行k次折叠时，记数字x所在的“块”的序号为B(x)。
由于1和2分别位于头尾，这里，定义
    B(1)=0
    B(2)=N
由于块内元素数目始终不超过2，故
    N=n/2+1-1=n/2，加1是因为头尾块均只有1个元素，减1是因为“块”从0开始编号
即
    B(2)=2^(k-1)

那么我们考察B(x)，则B(x)与B(1)之间有B(x)个“空隙”。
于是当进行k+1次折叠的时候，这些空隙间就可以插入2*B(x)个数。
所以，在进行k+1次折叠时，数字x所在位置，就是在k次折叠时的位置再加上前面这些插入的数字的个数：
    P(x)=(1+2*(B(x)-1))+2*B(x)+1=4*B(x) ............. (1)
或
    P(x)=(1+2*(B(x)-1))+2*B(x)+2=4*B(x)+1 ........... (2)
注意，上面的表达式是带下标的，其中B(x)的下标是k，而P(x)的下标是k+1。

而对于当前的k次折叠，B(x)与P(x)的关系不难得出：
    P(x)=2*B(x)
或
    P(x)=2*B(x)+1
即
    B(x)=P(x)/2，当P(x)为偶数时
或
    B(x)=(P(x)-1)/2，当P(x)为奇数时
这里B(x)与P(x)两者下标均为k，且分别对应(1)式和(2)式。

于是将下标为k的B(x)带入(1)式和(2)式，可得：
    P[k+1](x)=2*P[k](x)，当P(x)为偶数时
或
    P[k+1](x)=2*P[k](x)-1，当P(x)为奇数时

此时我们就得到了第一个迭代：

这里除了P(1)和P(2)容易得知

之外，还有一个比较特殊的点位，即P(n)，通过观察我们似乎能得出

根据前面我们总结的“头部稳定性”可得知这个结论是正确的。

从此结论出发，可以进一步观察，我们发现所有2的指幂所在的位置都是“特殊点位”！

这些点，我不妨将其称为“锚点”（anchor）。锚点有这样一些特点： 1) 锚点在它所在的块当中，总是这个块里的两个数字当中排在前面的那个。 1) 除数字1排在第一个以外，其余锚点是按降序排列。 1) 锚点间距是递增的，确切地说，除1以外，排在后面的锚点j（即数字）与排在前面的锚点j+1（即数字）之间间隔了个数字（或者说个块）。

在此，我们已经得到了这幅拼图当中的一小块，能够精确计算锚点的位置了。现在我们尝试继续往前迈一步，分析“块”的性质： 1) 首先，容易看出的，除去头尾两个数字，每个块均由一奇一偶两个数字组成，且偶数总是排在前面。于是对于任何一个折叠序列，总是奇偶相间排列的。 1) 因此，加上头尾的1和2，我们可以断定：奇数总是排列在奇数号位置，偶数总是排列在偶数号位置。 1) 锚点所在的块中，紧跟着锚点j后面的数字是，因此根据上面总结的锚点位置公式，有，不妨将此点称为“邻锚点”。拼图又接上了一小块。

我们通过层层推理，推出了所有锚点和邻锚点的准确位置，那么根据对折的轴对称性质，可以立即推算出比它们大1或小1的相邻数的位置了。这里锚点的镜像位数字比锚点数小1，而邻锚点的镜像位数字比邻锚点大1：

补完两块新的拼图。至此，当k>1时，我们能够准确推算的点位数有：

• 锚点：k+1个（包括1和2）
• 邻锚点：k-1个（除去1和2这两个数没有邻锚点）
• 锚点的对称位点：k-2个（除去1和2这两个数互为对称，以及中间块的4的对称点恰为邻锚点，不再重复统计）
• 邻锚点的对称位点：k-2个（除去中间块的4，其对称点3恰为邻锚点，不再重复统计）

总共4k-4个数。还剩个数的位置待确定。

块首倍增

在单独一个序列不容易看出规律的情况下，我们再次来观察两个相邻的序列，看看有什么规律。当然，我们很快就找到了——

对于k次序列，对于分布在1和2之间的各块，有：对于块i的第一个数字，在k+1次序列中的相同位置处的数字是它的两倍。

给定，它的第一个数字（根据上面块的性质第一条，一定是个偶数）是x，那么在中，第一个数字是2x，即

这里我们记块i的第一个数字为，第二个数字为。而对于每个块的第二个数字（奇数）——

对于k次序列的块i的第二个数字x，在k+1次序列中的相同位置处的数字是2x-1。

即

用值关系表示为，我们得到第二个迭代：

观察第一和第二迭代式，似乎长得完全一样啊？不对，其实它们是两个不同的等式。因为第一迭代式的条件是P(x)即位置序号的奇偶性；而第二迭代式的条件是x本身的奇偶性。但是却可以得出形式完全相同的迭代关系，这也从另一个角度揭示了前面总结过的对称性。

如果换算成数字的位置关系，则应该是：

至此，k+1次序列的前一半的所有块的数字，都可以从k次序列完全推出！

而序列的后一半数字呢？我们也观察到了——

k次序列的后半段数字与前半段有着镜像对应关系。
偶数在后半段的镜像位数字比该偶数数小1，而奇数在后半段镜像位数字比该奇数大1。

这个性质和前面锚点/邻锚点及其镜像点位的关系完全一致，即

此处记M(x)为数字x对称位（镜像位）上的数字。转换成位置函数关系就是：

或

于是序列的后半段也可以完全构造出来。至此，我们已经可以完全计算整个序列： 1) 确定头尾分别为1和2，即

1) 确定中间块的两个数字分别为4和3，即

1) 如何确定一个数是分布在序列的前半段（也称为“左边”）还是后半段（也称为“右边”）呢？这里有个快速的判断方法：

   数字模4余0或余1的，分布在左边；而余2和余3的，则分布在右边。

知道这个规律以后就可以分别构造前半段和后半段了。

1) 构造序列的前半段（模4余0或余1）：

......

......

1) 构造序列的后半段（模4余2或余3）：

......

......

根据对称性，求序列位置上的数字的公式也是完全一样的。

这个迭代计算的方法，我们可以总结为一句话——一阶k-1次对折序列决定了k次序列的前半段，而k次序列的前半段又决定了k次序列的后半段。

最后，必须重申的是：以上我的所有推理都是根据观察和归纳，并非严格的数学证明。

二阶对折（Second Order Folding）

问题

一张正方形的纸，均分成格，先按从左到右，然后从上到下顺序在每个格子写下自然数序列1，2，3，……，n

将纸条先从下往上，然后从右往左不断对折（共k轮，2k步），直至剩下一个格子，求： 1) 最后从下往上数字的序列 1) 数字x（）的最终位置 1) 最终序列中位置p的数字

照旧列个表：

名称     二阶一次对折  二阶二次对折                                 二阶三次对折

初始方阵  1 2          1  2  3  4                                 1  2  3  4  5  6  7  8
         3 4          5  6  7  8                                 9 10 11 12 13 14 15 16
                      9 10 11 12                                17 18 19 20 21 22 23 24
                     13 14 15 16                                25 26 27 28 29 30 31 32
                                                                33 34 35 36 37 38 39 40
                                                                41 42 43 44 45 46 47 48
                                                                49 50 51 52 53 54 55 56
                                                                57 58 59 60 61 62 63 64

对折轮数   1                2                                              3

最终序列  1 3 4 2      1 13 16 4 8 12 9 5 6 10 11 7 3 15 14 2    1 57 64 8 32 40 33 25 28 36 37 29 5 61 60 4 12 52 53 13 21 45 44 20 17 41 48 24 16 56 49 9 10 50 55 15 23 47 42 18 19 43 46 22 14 54 51 11 3 59 62 6 30 38 35 27 26 34 39 31 7 63 58 2

二阶对折的对称性

二阶对折的对称性不太容易直接观察到。我在这里不妨做一个试验。

在前面的一阶对折的对称性当中我曾经谈到过：“如果我们把最终序列重新写在另一张白纸条上的话，又对这张新纸条进行对折操作，最终你又能重新得到原始的自然数序列”。那么对于二阶对折，我将最终序列也按照方阵排列的话——

二阶一次对折
1 3
4 2

二阶二次对折
1 13 16 4
8 12  9 5
6 10 11 7
3 15 14 2

二阶三次对折
 1 57 64  8 32 40 33 25
28 36 37 29  5 61 60  4
12 52 53 13 21 45 44 20
17 41 48 24 16 56 49  9
10 50 55 15 23 47 42 18
19 43 46 22 14 54 51 11
 3 59 62  6 30 38 35 27
26 34 39 31  7 63 58  2

二阶四次对折
 1 241 256 16 128 144 129 113 120 136 137 121  9 249 248  8
56 200 201 57  73 185 184  72  65 177 192  80 64 208 193 49
52 196 205 61  77 189 180  68  69 181 188  76 60 204 197 53
 5 245 252 12 124 140 133 117 116 132 141 125 13 253 244  4
20 228 237 29 109 157 148 100 101 149 156 108 28 236 229 21
37 213 220 44  92 172 165  85  84 164 173  93 45 221 212 36
33 209 224 48  96 176 161  81  88 168 169  89 41 217 216 40
24 232 233 25 105 153 152 104  97 145 160 112 32 240 225 17
18 226 239 31 111 159 146  98 103 151 154 106 26 234 231 23
39 215 218 42  90 170 167  87  82 162 175  95 47 223 210 34
35 211 222 46  94 174 163  83  86 166 171  91 43 219 214 38
22 230 235 27 107 155 150 102  99 147 158 110 30 238 227 19
 3 243 254 14 126 142 131 115 118 134 139 123 11 251 246  6
54 198 203 59  75 187 182  70  67 179 190  78 62 206 195 51
50 194 207 63  79 191 178  66  71 183 186  74 58 202 199 55
 7 247 250 10 122 138 135 119 114 130 143 127 15 255 242  2

二阶五次对折
  1 993 1024  32 512 544 513 481 496 528 529 497  17 1009 1008  16 240  784  785 241 273 753 752 272 257 737 768 288 256  800  769 225
232 776  793 249 281 761 744 264 265 745 760 280 248  792  777 233   9 1001 1016  24 504 536 521 489 488 520 537 505  25 1017 1000   8
104 904  921 121 409 633 616 392 393 617 632 408 120  920  905 105 137  873  888 152 376 664 649 361 360 648 665 377 153  889  872 136
129 865  896 160 384 672 641 353 368 656 657 369 145  881  880 144 112  912  913 113 401 625 624 400 385 609 640 416 128  928  897  97
100 900  925 125 413 637 612 388 397 621 628 404 116  916  909 109 141  877  884 148 372 660 653 365 356 644 669 381 157  893  868 132
133 869  892 156 380 668 645 357 364 652 661 373 149  885  876 140 108  908  917 117 405 629 620 396 389 613 636 412 124  924  901 101
  5 997 1020  28 508 540 517 485 492 524 533 501  21 1013 1004  12 236  780  789 245 277 757 748 268 261 741 764 284 252  796  773 229
228 772  797 253 285 765 740 260 269 749 756 276 244  788  781 237  13 1005 1012  20 500 532 525 493 484 516 541 509  29 1021  996   4
 36 964  989  61 477 573 548 452 461 557 564 468  52  980  973  45 205  813  820 212 308 724 717 301 292 708 733 317 221  829  804 196
197 805  828 220 316 732 709 293 300 716 725 309 213  821  812 204  44  972  981  53 469 565 556 460 453 549 572 476  60  988  965  37
 69 933  956  92 444 604 581 421 428 588 597 437  85  949  940  76 172  844  853 181 341 693 684 332 325 677 700 348 188  860  837 165
164 836  861 189 349 701 676 324 333 685 692 340 180  852  845 173  77  941  948  84 436 596 589 429 420 580 605 445  93  957  932  68
 65 929  960  96 448 608 577 417 432 592 593 433  81  945  944  80 176  848  849 177 337 689 688 336 321 673 704 352 192  864  833 161
168 840  857 185 345 697 680 328 329 681 696 344 184  856  841 169  73  937  952  88 440 600 585 425 424 584 601 441  89  953  936  72
 40 968  985  57 473 569 552 456 457 553 568 472  56  984  969  41 201  809  824 216 312 728 713 297 296 712 729 313 217  825  808 200
193 801  832 224 320 736 705 289 304 720 721 305 209  817  816 208  48  976  977  49 465 561 560 464 449 545 576 480  64  992  961  33
 34 962  991  63 479 575 546 450 463 559 562 466  50  978  975  47 207  815  818 210 306 722 719 303 290 706 735 319 223  831  802 194
199 807  826 218 314 730 711 295 298 714 727 311 215  823  810 202  42  970  983  55 471 567 554 458 455 551 570 474  58  986  967  39
 71 935  954  90 442 602 583 423 426 586 599 439  87  951  938  74 170  842  855 183 343 695 682 330 327 679 698 346 186  858  839 167
162 834  863 191 351 703 674 322 335 687 690 338 178  850  847 175  79  943  946  82 434 594 591 431 418 578 607 447  95  959  930  66
 67 931  958  94 446 606 579 419 430 590 595 435  83  947  942  78 174  846  851 179 339 691 686 334 323 675 702 350 190  862  835 163
166 838  859 187 347 699 678 326 331 683 694 342 182  854  843 171  75  939  950  86 438 598 587 427 422 582 603 443  91  955  934  70
 38 966  987  59 475 571 550 454 459 555 566 470  54  982  971  43 203  811  822 214 310 726 715 299 294 710 731 315 219  827  806 198
195 803  830 222 318 734 707 291 302 718 723 307 211  819  814 206  46  974  979  51 467 563 558 462 451 547 574 478  62  990  963  35
  3 995 1022  30 510 542 515 483 494 526 531 499  19 1011 1006  14 238  782  787 243 275 755 750 270 259 739 766 286 254  798  771 227
230 774  795 251 283 763 742 262 267 747 758 278 246  790  779 235  11 1003 1014  22 502 534 523 491 486 518 539 507  27 1019  998   6
102 902  923 123 411 635 614 390 395 619 630 406 118  918  907 107 139  875  886 150 374 662 651 363 358 646 667 379 155  891  870 134
131 867  894 158 382 670 643 355 366 654 659 371 147  883  878 142 110  910  915 115 403 627 622 398 387 611 638 414 126  926  899  99
 98 898  927 127 415 639 610 386 399 623 626 402 114  914  911 111 143  879  882 146 370 658 655 367 354 642 671 383 159  895  866 130
135 871  890 154 378 666 647 359 362 650 663 375 151  887  874 138 106  906  919 119 407 631 618 394 391 615 634 410 122  922  903 103
  7 999 1018  26 506 538 519 487 490 522 535 503  23 1015 1002  10 234  778  791 247 279 759 746 266 263 743 762 282 250  794  775 231
226 770  799 255 287 767 738 258 271 751 754 274 242  786  783 239  15 1007 1010  18 498 530 527 495 482 514 543 511  31 1023  994   2

在此我将这个方阵称为“同阶结果方阵”（Equi-order Result Matrix）或者“结果方阵”。那么对这样一个方阵也按对折方式操作，是否最后也能够回到初始方阵呢？如果我把从开始的方阵进行对折操作得到最终的一维序列称为“一局”（Round）的话，需要对少局这样的对折才能回到初始方阵呢？

二阶一次对折（2局）
1 3  ->  1 4  ->  1 2
4 2      2 3      3 4

二阶二次对折（3局）
1 13 16 4     1  3  2  4    1 16 13 4    1  2  3  4
8 12  9 5 ->  5  7  6  8 -> 8  9 12 5 -> 5  6  7  8
6 10 11 7    12 10 11  9    7 10 11 6    9 10 11 12
3 15 14 2    16 14 15 13    2 15 14 3   13 14 15 16

二阶三次对折稍微复杂一些，亦可以自行检验，在最初的几局过后似乎都无法回归到初始方阵，但是，如果你有足够的耐心的话，可以验证到第27局的时候终于能够恢复到初始方阵了！（运行本项目的Web程序，在SOF标签页点击“Fold”之后会有个“Explore More”的开关，打开隐藏面板就可以展示这个反复对折的过程，目前只支持k从1到3的序列）。

从一次对折的2局还原，到二次对折是3局即可还原，然而三次对折突然有了一个比较大幅度的跨越，需要27局才能还原。四次及以上对折是否依旧可以还原到初始方阵呢？猜想似乎可以，并且猜想需要大得多的局数才能完成，但目前我还无法证明这个结论的真伪。

头部稳定

二阶对折过程同样服从头部稳定规律，但是这里需要是以“轮”为一个计数单位。

锚点

还是按照在推演一阶对折的公式中曾经用到过的思路：找特殊点位。

首先我们能找到三个比较明显点位：数字1，数字2和最后一个数字

• （结论1）1仍然是第一个数字
• （结论2）2是最后一个数字，即号位
• （结论3）位于3号位

转换成方阵的话：

• （结论1'）1位于左上角
• （结论2'）2位于右下角，也就是1的对角位置
• （结论3'）位于顶边的第3个位置，也就是和数字1隔了一个数字。当k=1时例外，4位于左下角，因为此时数字太少，仅有4个。

结论1和结论2与一阶对折的情形完全一致。

然后，紧跟着的两个数字，也就是第4个和第5个数字也很特别：

• （结论4）第4个数字是n的平方根，也就是
• （结论5）第5个数字是n的一半，也就是

即——

或——

还有：

• （结论6）除2以外的2的各幂次皆位于结果方阵的上半部分。这点和一阶对折的情形很相似。

数字4及其偶数倍数（8，16……等）似乎也很特别：

• （结论7）从二次对折开始，数字4总是位于结果方阵最右边，且在这一边的位置呈2的幂次数变化，也就是说，4是最右边的第个数，换算成一维结果，则是第个数。
• （结论8）从四次对折开始，数字8总是位于结果方阵最右边，且在这一边的位置呈2的幂次数变化，也就是说，4是最右边的第个数，换算成一维结果，则是第个数。
• ……

如果考察全部2的幂次值的话，我们发现：

• （结论9）2的幂次分布于三处：第1行，第列（最后一列），以及第列（倒数第4列）。

中间数

此外，与一阶对折情况类似地，结果序列（并非方阵）排在中间的两个数字也值得关注：

• （结论10）结果序列中，位于正中间的两个数的值是连续的，较小的那一个是奇数并且排在前面，两个数分别是呈2的幂次数变化，也就是说，4是最右边的第个数，换算成一维结果，则是第和

  

  

结论10如下图所示——

这两个数我称为“中间数"（Middle Numbers），它们在下面还将起到重要作用。

一阶对折与二阶对折之间的关系

略微对比一下马上就能发现，一阶对折的结果序列在同次的二阶对折结果序列中是保序的——

并且，对任意次对折我们总是可以迭代计算一阶任意位置x的值在二阶结果中的位置（这里的下标代表阶数）：

令s为以2为底的x的对数取上整，即
    s=ceil(log2(x))

记累加数sum
    sum+=2^(2*s-1)+1, s>0
or
    sum+=1, s=0

记变量x'
    x'=x-2^(s-1), s>0

将x'作为下一个x带入s，迭代计算sum，直至s=0
最后得到的sum即为P2(V1(x))

在一阶对折的推导过程中我们曾经发现过“镜像对称”关系，既然一阶序列在二阶序列中保序，那么二阶序列（或方阵）是否存在类似的性质呢？

中心对称与孪生点

我们把初始自然数序列按两两为一组，就像这样：(1,2) (3,4) (5,6) ... (, )

然后观察这些数字对在结果方阵中的位置，我们很快就发现一个有趣的现象：

• （结论11）这些数对中的每一对数字，在结果方阵里都呈现“中心对称”分布！也就是说，如果我们把对称中心定在这个结果方阵的正中心位置，那么我们挑选的一对数字正是以此为中心的对称。

不信你可以在上面给出的一次到五次结果方阵中验证。比如任意次数的结果方阵中，1和2分别位于左上和右下两对角位；二阶三次结果方阵中，3位于第7行（倒数第2行）第1列，而4位于第2行第8列；二阶四次结果方阵，100在第5行第8列，而第12行（倒数第5行）第9列正是数字99。

这里我就将这样一对数称为“孪生数”或者“孪生点”。

在结果方阵中的中心对称意味着什么呢？意味着我们把结果方阵重新还原成结果序列的话，那么孪生点在结果序列中是沿中心轴对称（当然也是中心对称，因为序列是一维的）。

中心对称规律的发现，立即将推算的点位数减少了一半，这显然是非常给力的。（当然，仍然只是我的观察结果，并非数学证明）

分布规律

由于二阶一次对折比较简单且特殊，可以视为平凡结论，因此下文中如未作特殊声明，我们皆视为二阶二次及以上各次对折（及其同阶结果方阵）。

我们以中位数（即）为参考点，将这n个数分为前后两部分：“高位数”（Upper Numbers，大于）和“低位数”（Lower Numbers，小于或等于）。

再观察结果方阵中的每一行，我们发现：

• （结论12）中位数位于方阵的上半部分。这个由结论5可知。
• （结论13）在任意一行中，高位数和低位数总是各占一半。
• （结论14）在行与行之间，高位数与低位数总是以两个为一组（头尾除外，它们分别只有一个数，并且皆为低位数）间隔着排列。

结论14可以用下图来表示——

在这里我沿用在一阶对折的推导过程中使用过的概念，也将每个方框内的那些数定义为一个“块”（Block）。块的分布规律让我们定位范围又缩小了一些。

块的间隔分布又可以导出另外一个重要发现——

• （结论15）在任意一行中每隔一列的两个数字相加，得到的值相等，并且等于n+1。

  

例如：二次折叠的第1列和第3列，第2列和第4列，分别相加，值均为17（16+1）；三次折叠，第1列和第3列，第2列和第4列，第5列和第7列，第6列和第8列，两两相加，得到65（64+1）；四次折叠也类同，加和为257（256+1）。如下图所示——

因此可以说结论3（以及结论3'）是结论15的特例。

我将这样的两列称为“互补”（Complementary），互补列中对应的两个数互相称为“补数”（Complement）。

当然，对于每列数字，相邻的两行数字两两相加也可以得到一个相等的数，比如三次对折的结果方阵的第1列：1+28=12+17=10+19=3+26=29。但这其实是中心对称性质的一个推论，并且不同列得到的加和也不一定相等（只有轴对称的两列的各自加和才相等）。

这个规律（结论15）使得需要计算的数目又减少了一半，结合中心对称规律，至此我们最多需要推算即个数的位置即可。到这里我们是否能联想到什么呢？总数的，不正好就是k-1次对折和k次对折之间的比例关系吗？还记得我们在一阶对折的推导中最后得出的那个迭代关系吗：

（一阶）k-1次对折序列决定了k次序列的前半段，而k次序列的前半段又决定了k次序列的后半段。

那么对于二阶对折，是否也存在类似的迭代计算方法？关键是要找到二阶k-1次结果方阵在k次结果方阵中的分布规律。

次间的迭代规律

先看粗的分布。下图用不同颜色的框，在k次结果方阵中把k-1次折叠中出现的所有数字标注出来——

可见k-1次折叠的各元，在k次折叠的结果方阵中大致呈列状分布。一次和二次折叠存在间隔，呈离散状，但在三次及以上折叠的结果方阵中，k-1次各元均稳定且（按列）“连续”整齐排列。

分布规律再探

结合上面的从一阶点位对二阶点位的迭代推算方法，我们可以准确得出个数的位置。这些推算出来的点位在下图中用马克笔高亮标示——

再结合结论10的中间数规律，还能再推出4个点位——

然后我们很快又发现一个规律：

• （结论16）中间数排在前面的那个（即）的补数，在它前面的数恰好就是！同时它的补数也就立知了。

这样我们又多推出4个数的点位——

关于列的加和，还有另外一个：

• （结论17）最左边和最右边的两列，分别与它们往中间数4列，然后这两列的加和是，即

  

类似地，也可以说结论5是结论17的特例。

当然，事情到此并未结束，继续观察可以发现四次及以上对折还能挖掘出更多加和为的成对两列出来——

偶先数对

在研究中心对称规律的时候我们引入过孪生数对的概念，只要两个前后相继的数是奇数排在偶数前面，那么必然满足中心对称。那么我们是否可以在此基础上再进一步，如果在初始方阵中一对前后相继的数对是偶数排在前面呢？首先，容易观察到方阵的左右两边列似乎有较多这样的数对，我就二次到五次对折整理了一下位于侧边列的分布，将偶数在前的两个数用线连接起来——

为了让规律看起来更清晰一些，我把k的值继续升至6，这样元数就有4096个之多，形成一个相当大的64x64的结果方阵——

这里将在初始方阵中前后相继且偶数在前的一对数称为“偶先数对”（Even-First Pair）。上面从二次到六次对折，两侧边列的偶先对满足这样一种分布规律：

• （结论18）侧边列的偶先数对在结果方阵的上半部分和下半部分有着不同的分布规律。为了避免与前面定义的“高位数”和“低位数”概念混淆，我在这里将方阵沿垂直方向划分为数字个数相等的上下两部分，其中上半部分称为“上半区”或“前半区”（First Half），而下半部分称为“下半区”或“后半区”（Later Half）。二次对折比较特殊，两对数都位于下半区且呈轴对称；三次对折，有四对数全部分布在下半区，且以下半区的垂直方向再均分为上下两部分，四对数平均分布在两部分，且沿各自的对称中心分布；四次及以上对折，下半区呈现和三次对折相同的规律，上半区开始有数对出现，但是总数要少于下半区。

以上是偶先数位于结果方阵两端的情形。如果数对位于方阵内部的话——

可见

• （结论19）内部的偶先数对分布规律与侧边的偶先数对几乎相反。除了二次对折的内部偶先数对也是位于下半区之外，三次及以上对折全部的内部偶先数对皆分布与上半区。

偶先数对在方阵下半区的分布尤为引人注目，比起上半区，下半区显然规律性更强一些。比如我们继续观察位于中间的两列，同样可以发现和侧边列偶先数对相同的分布规律——

继而你可以发现，整个下半区只要是对称的两列，全部服从这种“半中心对称”规律！

利用-1的奇偶幂次正负交变的性质，上式可以简化为——

若定义二值函数

又可以进一步简化为——

或

正规节与正规节组

下半区的分布已经得到完美解决，真正困难的在于上半区，虽然有一部分数字分布有规律，但整体的规律性却不好找，现在能发现的一些规律是：

• （结论20）结果方阵还原成一维序列的话，内部偶先数对出现的位置和间隔对于不同次数的对折都是相同的，但是还不能确定在这些位置上的确切数字。
• （结论21）从三次对折开始，上半区的数字里有一半是呈现轴对称或“半中心对称”，且其中对于每行上的数字而言有着相同的对称中心。

事实上，所谓“中心对称”或“半中心对称”都是以方阵形态为观察对象，如果把“对称”的这一部分重新还原成局部一维序列的话，它们都是轴对称的。以这种视角来观察上半区的构造，就会发现它非常像是一种“分形”（Fractal）的结构。为方便描述上半区规律，这里我先定义两个概念：正规和正规节。

• 一段一维数字序列是“正规的”（Regular），当且仅当序列含偶数个数字，且所有数字按偶先数对形成中心对称。
• 这样的一个序列称为一个正规节（Regular Segment），若序列包含m对偶先数对，该序列也称为“m-正规”，m也称为“节容”（Segment Size）。也就是说，m是序列所含元数的一半。
• 不满足正规条件的序列称为“非正规的”（Non-regular）。

于是当上半区展开成一维序列之后，满足这样一种结构：

非正规，2-正规 x 4，非正规，8-正规 x 4，非正规，2-正规 x 4，非正规，32-正规 x 4，非正规，2-正规 x 4，非正规，8-正规 x 4，非正规，2-正规 x 4，非正规，128-正规 x 4，非正规，2-正规 x 4，非正规，8-正规 x 4，非正规，2-正规 x 4，非正规，32-正规 x 4，非正规，2-正规 x 4，非正规，8-正规 x 4，非正规，2-正规 x 4，非正规，……

看着头晕么？那么依次列举就是：

二次对折：
  非正规（4个数）
  非正规

三次对折：
  非正规（8个数）
    2-正规 x 4  <-中心节组
  非正规

四次对折：
  非正规
    2-正规 x 4
  非正规
      8-正规 x 4  <-中心节组
  非正规
    2-正规 x 4
  非正规

五次对折：
  非正规
    2-正规 x 4
  非正规
      8-正规 x 4
  非正规
    2-正规 x 4
  非正规
        32-正规 x 4  <-中心节组
  非正规
    2-正规 x 4
  非正规
      8-正规 x 4
  非正规
    2-正规 x 4
  非正规

六次对折：
  非正规
    2-正规 x 4
  非正规
      8-正规 x 4
  非正规
    2-正规 x 4
  非正规
        32-正规 x 4
  非正规
    2-正规 x 4
  非正规
      8-正规 x 4
  非正规
    2-正规 x 4
  非正规
          128-正规 x 4  <-中心节组
  非正规
    2-正规 x 4
  非正规
      8-正规 x 4
  非正规
    2-正规 x 4
  非正规
        32-正规 x 4
  非正规
    2-正规 x 4
  非正规
      8-正规 x 4
  非正规
    2-正规 x 4
  非正规

……

这里的一个“非正规节”是一段包含8个数字的小序列。中间最长的一个正规节称为“中心节”（Center Regular Segment），正规节一般一次连续出现4个，称为“正规节组”（Regular Segment Group，简称为“节组”），因此中间这4个也就是“中心节组”（Center Regular Segment Group），中心节组占有上半区一半的数字，也就是，或者说个数。不同数目的正规节以4倍为一个周期增长，并且这些节组在整个上半区也是以中心节组为中心对称分布。

• （结论22）中心节的节容为，这里
• （结论22'）各正规节的节容为

其实如果我们把范围不仅局限于上半区的话，那么下半区的两个“半中心对称”区域同样可以视为两个正规节，也就是半个节组，节容为。所以，

• （结论23）整个k次对折的结果序列的分布形态正好就构成k+1次对折的前部分的分布形态！

图中位于方框内的都是正规节，由于比较稠密，可能不容易分辨。

因此如果偶数x的位置P(x)能够正好落到一个“正规节”区间，那还是能够推算它的配对奇数的位置的。例如，对于中心节组——

若以或者说为基准单位，上式可整理为——

同理可以计算落到比中心节组“次一级”的正规节区间的偶数，其后继奇数的位置——

若以或者说为基准单位，上两式可整理为——

依此类推再次一级的正规节组——

由于每一级节组均匀等距分布于它的上一级节组的两侧，我们可以计算它们的间距

• （结论24）假定本级节组的基准单位为u（一般为形式，是节容m的两倍），则距离它的高一级节组的最近间隔是2u。

例如，中心节组基准单位是，则次级节组的基准单位是，而它前后两个最近的次级节组距离中心节组边缘是；三级节组距离次级节组最近间距是；依此类推。

由于下半区可视为k+1次序列的中心节组的前半段（两个-正规节），故结论19中的所谓“半中心对称规律”也可以用统一化的表示——

至此，我们可以定位到所有落在结果序列的正规节内的偶先数对的位置了。那么二阶对折问题只剩下最后一道坎：非正规节内的偶先数对。

番外

这里有一个简易的判断方法（尚未证明），用于判定任意一个值它到底是在上半区还是下半区——

• （结论25）在初始方阵中分布于上半区的数字和分布于下半区的数字以每两列为一个单位（头尾除外，分别占一列），间隔排列，这样就分成两组，其中头尾所在的那一组是在上半区的数字，而另外一组则是下半区的数字。

这和前面结论14得到的高位数和低位数分布规律是不是非常相似？但记住这里是对初始方阵而言的。

非正规节

“非正规节”并非没有规律可循。如果我们把非正规节的u值固定为8的话（对于二次对折的结果方阵的前两行合并为一个非正规节），就能发现：

• （结论26）所有非正规节的中间4个数字皆为偶数。而且不仅如此，
• （结论26'）非正规节中间这4个偶数皆为的倍数！

为了看得清楚一些，我把这些偶数单独拎出来

上图中每个数字上面用不同颜色标注的数字是的倍数。于是前面的结论4至结论9皆可视为结论26'的推论。

如果我们单独考察这些倍数的话，

4 1 2 3

8 1 4 5 6 3 2 7

16 1 8 9 12 5 4 13 14 3 6 11 10 7 2 15

32 1 16 17 24 9 8 25 28 5 12 21 20 13 4 29 30 3 14 19 22 11 6 27 26 7 10 23 18 15 2 31

是不是有些眼熟？还记不记得前面推导过的一阶各次序列

1 2

1 4 3 2

1 8 5 4 3 6 7 2

1 16 9 8 5 12 13 4 3 14 11 6 7 10 15 2

1 32 17 16 9 24 25 8 5 28 21 12 13 20 29 4 3 30 19 14 11 22 27 6 7 26 23 10 15 18 31 2

可见

• （结论27）这些的倍数组成的序列，恰好就是一阶序列中把数字两两一组，然后组内的两个数字相互交换，这样得到的一个序列。

虽然这个规律可以推导出这些倍数以及原数字，但考虑到非递归一阶序列计算也是要花费时间和空间的，故我们希望最好避开直接使用一阶序列。由于我们前面已经得到了列的“加和规律”（结论15），于是只要确定其中偶数的位置，非正规节内剩下的4个奇数的位置马上也能计算出来（因为一个非正规节只有8个数，且4个偶数位于中间）。如何在不引用一阶序列的计算过程的情况下推算偶数的位置呢？首先，我们发现这个倍数的序列也是满足两两加和相等的规律：

• （结论28）的倍数组成的序列中，两两编为一组，其加和相等，且等于

我们再把这些倍数中的偶倍数单独提出来——

4 2
8 4 6 2
16 8 12 4 14 6 10 2
32 16 24 8 28 12 20 4 30 14 22 6 26 10 18 2

把这些偶倍数再两两编为一组

(4 2)
(8 4) (6 2)
(16 8) (12 4) (14 6) (10 2)
(32 16) (24 8) (28 12) (20 4) (30 14) (22 6) (26 10) (18 2)

于是我们可以发现这么一个规律：

• （结论29）把这些偶倍数分为高位和低位两部分，即较大的个为高位的偶倍数，较小的个为低位的偶倍数，首先，每个编组内各包含一个高位偶倍数和一个低位偶倍数，且高位偶倍数排在前面，编组内的两个数之差为。
• （结论29'）然后把这些编组也均分为前后两部分，高位偶倍数从前半段开始轮流填入前后半段，低位偶倍数亦然。

以k=5为例，8个高位偶倍数是：18，20，22，24，26，28，30，32。它们是这样分布的： 1) 首先挑出最大的32，放在前半段第一个编组的第一位；再挑出次大的30，放在后半段第一个编组，即第五个编组的第一位。 1) 然后是28放在前半段的后半段的前半段，即第三个编组的第一位；26放在后半段的后半段的前半段，即第三个编组的第一位。 1) 接着是24放在前半段的前半段的后半段，即第二个编组的第一位；22放在后半段的前半段的后半段，即第二个编组的第一位。 1) 最后是20放在前半段的后半段的后半段，即第四个编组的第一位；18放在后半段的后半段的后半段，即第四个编组的第一位。

低位偶倍数依相同规律放置，但是放在编组的第二位。

这样理解恐怕是比较繁琐的，事实上我们可以每次把倍数的规模递减一半——

32  1 16 17 24  9  8 25 28  5 12 21 20 13  4 29 30  3 14 19 22 11  6 27 26  7 10 23 18 15  2 31

32    16    24     8    28    12    20     4    30    14    22     6    26    10    18     2

32          24          28          20          30          22          26          18

32                      28                      30                      26

32                                              30

32

可见每减少一轮，剩下的倍数在序列里总是等距的。于是我们就知道该如何构造这个偶倍数的序列。

这样所有偶倍数的位置都可以确定了，根据前面的“倍数的加和规律”（结论28），所有奇倍数的位置也可以确定，事实上，奇倍数的位置分布和上面这个规律恰好相似，只不过是高低位互换，低位奇倍数排在编组的第一位，且从低到高开始轮流填入前后半段。

事实上由于等效性，此规律也可以用于解决前面的一阶序列问题。

到此为止，我们就解决了非正规节，从而也完整解决了二阶序列的计算问题。

非递归的计算步骤

1) 准备工作：首先构造关于正规节和非正规节的两张映射关系表。

1) 首先，根据次数k值，推出上半区最多能有几级正规节组，计算、、、、……，直至最小值4。 1) 构造“取值区间-偶先数对”的对应关系表，称为“表I”。 1) 从最大的正规节组（即构成整个下半区的两个节组）开始，u值为 1) u值减半得到上半区的中心节组，其最后一个数与下半区第一个数之间的距离是2u（此时u已减半，为中心节组的u）。 1) 从中心节组开始，重复上一步操作，在其两侧定位次一级的节组。 1) 直至遍历完前面计算出的节组级数。 1) 构造“取值区间-非正规节”的对应关系表，称为“表II”。 1) 选取最大的倍数（即），放到第一位。 1) 选取次大的偶倍数，放到第位。 1) 选取再小的两个偶倍数，按照前两步的排列好的先后顺序，插入前面两数以后空当的正中位置，即和 1) 重复以上步骤，每次选取前一步的两倍个偶倍数，按前一步形成的大小次序逐个插入前一步形成的空当中，直至全部偶倍数选取完毕。 1) 利用“倍数的加和规律”（结论28），计算出奇倍数的位置。 1) 确定非正规节的取值区间。 1) 利用“列的加和规律”（结论15）计算出除了倍数以外的数字位置。

1) 从第一个数1开始，若遇到奇数，则使用“中心对称规律”（结论11），得到下一个偶数位置为

进入下一步

1) 若遇到偶数，

1) 若该偶数落入一个正规节取值区间（包括下半区）内，那么查表I，根据该区间上的函数得到下一个奇数的位置。 1) 若该偶数不属于任何一个正规节区间，则其落入了一个非正规节区间，那么查表II，得到下一个奇数的位置。 1) 回到步骤2。

1) 二阶一次对折的结果可作为平凡结论直接给出。

算法

目前支持最容易设计的“递归算法”（Recursive），以及非递归的“迭代公式算法”（Formula，即应用本篇文字所归纳总结的结论）。

Web程序的UI部分基于React JS和Material UI。

余论

在（非严格地）解决了一阶和二阶对折问题之后，我们是否可以进一步推广到三阶对折情形——

一个立方形，均分成8^k小立方体，
从最底下的位置开始算起，先按从左到右，然后从上到下，最后从底到顶的顺序
在每个小立方体内写下自然数序列1，2，3，……，n

将立方体先从顶部往底部，然后从下往上，最后从右往左不断“对折”（共k轮，3k步），直至剩下一个格子，求：
1. 最后从下往上数字的序列
2. 数字x的最终位置
3. 最终序列中位置p的数字

这里首先要理解所谓立方体是如何“对折”的。一个真实的三维立方体当然无法“对折”，这样它就会从中间断裂开，并且得到的是一个柱体，明显与我们在一阶纸条和二阶纸片的直观结果不符。所以这里并非是一个真实的，充满一块空间的“立方体”，而是撕开来的n张正方形小纸片，按照问题中的排列方式，整齐排列在一个三维立方体内部，然后就可以定义“对折”操作了：每次对折是把一部分纸片叠放到另一部分纸片的“上面”。每轮对折过后，纸片的“堆数”是前一轮的

所以这个问题可以一直推广到更一般的“r阶对折”的情形——

一个r维空间的“超立方形”，均分成2^(r*k)小超立方体，
从最后一维开始算起，每次在该维内按从低到高的顺序
在每个小立方体内写下自然数序列1，2，3，……，n

将这个超立方体从最后一维开始，把后半部分往前半部分不断“对折”（共k轮，r*k步），直至剩下一个一维序列，求：
1. 最后从下往上数字的序列
2. 数字x的最终位置
3. 最终序列中位置p的数字

这个“最一般”的问题虽然我们可以理解了，但计算依然不是一件容易的事情。大家是否可以推导出它的一般规律呢？