四阶上帝之数新进展

铯_猪哥恐鸣

去年暑假我证明了四阶OBT度量下的上帝之数<=57。Tomas Rokicki首先确认了这一结果，并在这基础上进一步更新了SST和BT度量下四阶上帝之数的上界，具体如下表所示：

1.           OBT    SST     BT
   
2.          ------ ------ ------
   
3. Stage 1    8      8      7
   
4. Stage 2   14 -1  13     12
   
5. Stage 3   16     15     15 -1
   
6. 3x3       20     20     20
   
7. -------  ------ ------ ------
   
8. Total     57     56     53
   
9. Low Bound 35     32     29

复制代码

其中各阶段状态分布如下表所示：

1.   OBT  Stage 1         Stage 2            Stage 3
   
2. -----  -------  --------------  -----------------
   
3.     0        3               6                  1
   
4.     1        6              12                  3
   
5.     2      108              48                 34
   
6.     3    1,434             381                356
   
7.     4   15,210           3,643              3,568
   
8.     5  126,306          45,030             34,223
   
9.     6  420,312         606,937            331,445
   
10.     7  171,204       8,154,706          3,279,289
    
11.     8      888     102,867,620         32,869,934
    
12.     9            1,114,713,818        322,793,264
    
13.    10            8,194,798,024      3,071,165,269
    
14.    11           21,637,154,427     28,175,871,844
    
15.    12            7,652,855,512    230,035,097,211
    
16.    13               49,121,344  1,381,997,542,963
    
17.    14                       92  3,877,591,153,596
    
18.    15                           1,518,183,963,004
    
19.    16                               1,909,413,996
    
20. -----  -------  --------------  -----------------
    
21. Total  735,471  38,760,321,600  7,041,323,520,000
    
22.   Avg    6.016          10.922             13.941
    
23. 
    
24.   SST  Stage 1         Stage 2            Stage 3
    
25. -----  -------  --------------  -----------------
    
26.     0        3               6                  1
    
27.     1        6              12                  3
    
28.     2      144              78                 40
    
29.     3    2,070             736                419
    
30.     4   21,984           8,163              4,665
    
31.     5  143,040         108,504             52,862
    
32.     6  408,672       1,642,541            595,554
    
33.     7  159,120      25,051,200          6,828,900
    
34.     8      432     354,505,613         78,698,572
    
35.     9            3,855,130,124        890,241,566
    
36.    10           18,190,204,075      9,649,560,534
    
37.    11           15,214,615,212     97,220,792,244
    
38.    12            1,119,011,837    796,714,246,234
    
39.    13                   43,499  3,582,837,239,094
    
40.    14                           2,544,863,842,658
    
41.    15                               9,061,416,654
    
42. -----  -------  --------------  -----------------
    
43. Total  735,471  38,760,321,600  7,041,323,520,000
    
44.   Avg    5.954          10.330             13.219
    
45. 
    
46.    BT  Stage 1         Stage 2            Stage 3
    
47. -----  -------  --------------  -----------------
    
48.     0        3               6                  1
    
49.     1        6              24                  3
    
50.     2      210             126                 49
    
51.     3    3,576           1,441                600
    
52.     4   49,326          19,227              7,814
    
53.     5  334,302         334,248            102,809
    
54.     6  340,776       6,154,548          1,348,606
    
55.     7    7,272     112,313,065         17,868,420
    
56.     8            1,741,855,110        234,452,146
    
57.     9           14,780,736,610      2,974,523,970
    
58.    10           21,220,484,824     35,959,010,450
    
59.    11              898,419,145    380,135,222,472
    
60.    12                    3,226  2,571,726,262,872
    
61.    13                           3,958,934,429,976
    
62.    14                              91,340,289,756
    
63.    15                                          56
    
64. -----  -------  --------------  -----------------
    
65. Total  735,471  38,760,321,600  7,041,323,520,000
    
66.   Avg    5.405           9.543             12.523

复制代码

铯_猪哥恐鸣

折翼蚂蝗 发表于 2015-3-7 19:21
还有测度有种实变函数的赶脚

手抖了。。。应该是“度量”。。。

铯_猪哥恐鸣

谢老师 发表于 2015-3-7 22:00
CS厉害！上帝之数

最新结果是55步，结果还在进一步确认中。

铯_猪哥恐鸣

pengw 发表于 2015-3-9 17:28
上界:即小于或等于某个值
下界:即大于或等于某个值
-------------

可以参考我在知乎上的回答：http://www.zhihu.com/question/23619010/answer/29414485

铯_猪哥恐鸣

pengw 发表于 2015-3-10 08:46
计算下界的本质是，假设转式数与状态数正好相等(实际上是不可能),而推导出的转式长度,除非楼主有新的可行的 ...

好的，请证明一下。

铯_猪哥恐鸣

pengw 发表于 2015-3-9 21:53
18楼不是证明，照17楼的定义，下界应该小很多，我可以给出一个证明，不过，希望首先看到楼主的57步证明

57步的证明的描述在 http://cubezzz.dyndns.org/drupal/?q=node/view/525 ，具体计算结果1楼也有贴出。55步的证明在这里：http://cubezzz.dyndns.org/drupal/?q=node/view/541

铯_猪哥恐鸣

pengw 发表于 2015-3-10 14:29
如果，仅仅是把簇的最远状态相加做为魔方最远状态，肯定没有这么简单，单看三阶最远状态，其中的角簇还是初 ...

你说的没错。

铯_猪哥恐鸣

pengw 发表于 2015-3-10 15:32
续上贴，况且，各簇的最远状态能否搭配在一起还要看能否与N阶定律相容或与扰动关系冲突否

是的，我同意。

铯_猪哥恐鸣

pengw 发表于 2015-3-10 19:30
楼主的的方法虽然还存在一起需要克服或验证的问题，但是，如果一但可行，那么处理难度将成几何级数的下降， ...

我认为我的证明没问题，如果你觉得有问题，请明确的指出。

铯_猪哥恐鸣

pengw 发表于 2015-3-10 21:14
如果，你的计算原理真如25楼说的那样，疑点就会非常多. 你能可否解释一下stage1-stage3，我的理解是，四阶三个簇你分别对应三阶的三个簇，你用四阶的三个簇的最远状态之和加上三阶的最远状态，就是你说的四阶最远状态?

我的证明方法和你25楼所述的显然并不一样，我并没有对每个簇分开进行处理，而是采用了类似降群法的思路。但由于降阶阶段的状态用生成群表示很困难，所以我尝试用生成群之间的乘法来表述。我的证明方法简言之可以总结如下。
首先定义四组集合：
S0: <U, R, F, D, L, B, Uw, Rw, Fw, Dw, Lw, Bw>
S1: <U, R, F, D, L, B, Uw Dw', Rw Lw', Fw Bw'> * <U, R, F, D, L, B, Uw2, Rw, Fw2, Dw2, Lw, Bw2>
S2: <U, R, F, D, L, B, Uw Dw', Rw Lw', Fw Bw'> * <U, R2, F, D, L2, B, Uw2, Rw2, Fw2, Dw2, Lw2, Bw2>
S3: <U, R, F, D, L, B, Uw Dw', Rw Lw', Fw Bw'>
其中“<>”表示生成群，“*”表示集合乘法。于是，S0包含了四阶所有可能性，S3即为在四阶上仅打乱外层或整体转动能够达到的所有可能性（即降阶完成的状态）。
Stage1证明S0中的任何一个状态可以在8步以内转化成S1中的某个状态。
Stage2证明S1中的任何一个状态可以在13步以内转化成S2中的某个状态。
Stage3证明S2中的任何一个状态可以在16步以内转化成S3中的某个状态。
然后根据三阶上帝之数为20，S3中任何一个状态可以在20步内还原。
从而四阶所有状态都可以在不超过8+13+16+20=57步内还原。

最后，我再次强调我并没有将三个簇分开处理，而是通过上述“降群”的方式一步步联合处理了它们。