有理数循环小数的周期长度规律

我是01指挥员

有理数循环小数的周期长度规律

简介：本文寻找出不同类型奇数倒数的小数循环周期长度规律，探讨如何利用这种规律来解决数论中的某些难题，例如，质数识别和某种类型的最大公约数问题。本文主要有两个创新点：一、找出了合数和质数之间循环周期长度的差异规律，可以作为一种新型的判断质数的必要条件。二、首次提出循环周期长度的复杂度定义，并给出了一种可包含有任意多、且任意大、具有特定结构的数值，循环周期的长度却相对很短，始终为多项式时间等级。本文的基础性研究工作，将为开创出数论的一个新分支，有别于传统方法寻找极大质数的新算法，打下基础。
初中时就没有认真想过：为什么数还要分为有理和无理的，有理数究竟有多少道理？好像它只不过就是一种数系的分类而已。不懂就不懂吧，反正并没有损失什么，似乎也没有影响到作者后来学会了微积分，也懂得了拉普拉斯变换等一些更高级一点的数学概念。现在想来，可能就是因为我们更多的是把有理数和无理数，仅仅作为数学理论体系上数系的一种严谨划分，而忽视了它本身具有的丰富内涵。
有理数为整数和分数的统称，它的定义可有多种等价方式，其中之一就是：任何一个整数的倒数，小数点后面都是有限循环小数；而无理数，则是无限不循环小数。难道就只有这么多道理了吗？

一、倒数小数点后面循环周期长度的规律
请仔细观察，下表中列出合数和质数的循环周期长度（还可以给出更多，但这些已经足够），其中有什么差异和规律？
表1 奇数倒数小数点后的循环周期以及规律示意表（其中［a,b］表示为合数质因数a和b各自循环周期之间的最小公倍数）
奇数        质性        因数分解        循环周期长度及规律        周期内的循环数值
3        质数                1=(3-1)/2        短循环周期0.3
7        质数                6=7-1        长循环周期0.142857
9        合数        3*3        1=［1,1］        不规则短循环周期（含有多次方因子）0.1
11        质数                2=(11-1)/5        短循环周期0.09
13        质数                6=(13-1)/2        短循环周期0.076923
17        质数                16=17-1        长循环周期0.0588235294117647
19        质数                18=19-1        长循环周期0.052631578947368421
21        合数        3*7        6=［1,6］        短循环周期0.047619
23        质数                22=23-1        长循环周期0.0434782608695652173913
27        合数        3*3*3        3=1*3        不规则短循环周期（含有多次方因子）0.037
29        质数                28=29-1        长循环周期0.0344827586206896551724137931
31        质数                15=(31-1)/2        短循环周期0.032258064516129
33        合数        3*11        2=［1,2］        短循环周期0.03
37        质数                3=(37-1)/12        短循环周期0.027
39        合数        3*13        6=［1,6］        短循环周期0.025641
41        质数                5=(41-1)/8        短循环周期0.02439
43        质数                21=(43-1)/2        短循环周期0.023255813953488372093
47        质数                46=47-1        长循环周期
49        合数        7*7        42=6*7        不规则短循环周期（含有多次方因子）
51        合数        3*17        16=［1,16］        短循环周期0.0196078431372549
53        质数                13=(53-1)/4        短循环周期0.0188679245283
57        合数        3*19        18=［1,18］        短循环周期0.017543859649122807
59        质数                58=59-1        长循环周期
61        质数                60=61-1        长循环周期
63        合数        3*3*7        6=［1,6］        不规则短循环周期（含有多次方因子）0.015873
67        质数                66=67-1        长循环周期
69        合数        3*23        22=［1,22］        短循环周期0.0144927536231884057971
71        质数                35=(71-1)/2        短循环周期
73        质数                8=(73-1)/9        短循环周期0.01369863
77        合数        7*11        6=［6,2］        短循环周期0.012987
79        质数                13=(79-1)/6        短循环周期0.0126582278481
81        合数        3*3*3*3        9=1*3*3        不规则短循环周期（多次方因子）0.012345679
83        质数                41=(83-1)/2        短循环周期
87        合数        3*29        28=［1,28］        短循环周期0.0114942528735632183908045977
89        质数                44=(88-1)/2        短循环周期
91        合数        7*13        6=［6,6］        短循环周期0.010989
93        合数        3*31        15=［1,15］        短循环周期0.010752688172043
97        质数                96=97-1        长循环周期
99        合数        3*3*11        2=［1,2］        不规则短循环周期（含有多次方因子）0.01
101        质数                4=（101-1）/25        短循环周期0.0099
103        质数                34=（103-1）/3        短循环周期
107        质数                53=（107-1）/2        短循环周期
109        质数                108=109-1        长循环周期
111        合数        3*37        3=［1,3］        短循环周期0.009
113        质数                112=113-1        长循环周期
117        合数        3*3*13        6=［1,6］        不规则短循环周期（含有多次方因子）0.008547
119        合数        7*17        48=［6,16］        短循环周期
121        合数        11*11        22=2*11        不规则短循环周期0.0082644628099173553719
123        合数        3*41        5=［1,5］        短循环周期0.02439
127        质数                42=（127-1）/3        短循环周期
129        合数        3*43        21=［1,21］        短循环周期0.007751937984496124031
131        质数                130=131-1        长循环周期
133        合数        7*19        18=［6,18］        短循环周期0.007518796992481203
137        质数                8=(137-1)/17        短循环周期0.00729927
139        质数                46=(139-1)/3        短循环周期
2261        合数        7*17*19        144=［6,16,18］        短循环周期
可以总结出不同类型奇数的循环周期长度规律如下。
1 奇数N的循环周期不大于(N-1)
我们已知，任意一个奇数N的循环周期长度有大有小，但最长不会超过（N-1）。例如7，17，19，它们的循环周期分别为6，16，18，本文称其为长循环周期质数；其余则称为短或不规则短循环周期（含有多次方因子）。本文将在第三章中，对循环周期长度的复杂度，专门进行讨论。
2 如果奇数N的循环周期为（N-1）则必然是个质数
如果发现某个奇数N，循环周期的长度为（N-1），就可以判定它必然是个质数；这是一种新型的质数判定标准。合数的循环周期都要小于（N-1），尚没有发现循环周期等于（N-1）的合数。这也可以从规律4，有关合数循环周期规律的讨论中进一步得到证实。
但是，如果单纯地应用除法来获取某个整数N的循环周期数，最多时需要进行（N-1）次，n位长度的减法计算。因此，对于具有长循环周期的质数（甚至也包括很多合数），计算复杂度为O(N*n)的等级，计算效率并不高。因此，当数值N比较大时，想要根据这种规律，仅仅依靠除法计算，就识别出一个具有长或较长循环周期的质数，不是一件容易事。
假如将来能够找到一种更高效率的方法，那么根据规律2，则意味着找到了寻找出任意大质数的好算法。
3 质数P的循环周期必然可以整除（P-1）
有超过一半的质数，它们的循环周期要小于（P-1），可被称为短循环周期质数，其循环周期的长度既有偶数，也有奇数，但不论周期数或大或小，全部能够整除（P-1）。
例如，质数11的循环周期长度为，2 =（11-1）/6；质数13的循环周期是，6 =（13-1）/2；质数53的循环周期是，13 =（53-1）/4。其中既有奇数也有偶数，但都能整除（P-1）。
目前尚不能够明确指出，什么样的质数具有长循环周期，什么样的质数循环周期却又比较短，以及循环周期数是奇还是偶。
4 合数C的循环周期
合数的循环周期长度，为它的所有质因数a，b，c，…，各自循环周期之间的最小公倍数,记为［a,b,c,…］。
例如，因为7的循环周期为6，标记为7（6）；又因为有11（2），那么合数7*11的循环周期为，［6,2］= 6，即1/77 = 0.012987…。又例如，假如已知7（6），17（16），7*17 = 119，那么合数119的循环周期长度则为，［6,16］= 48。如果合数是，2261 = 7*17*19，无需复杂计算即可知，循环周期长度必然为，［6,16,18］= 144。
在绝大多数的情况下，合数C的循环周期数c,不能整除（C-1），这是由于它们的循环周期规律所决定的。即，大多数合数C的质因数循环周期长度的最小公倍数，不能整除（C-1）。例如，119（48）,循环周期数48就不能够整除（119-1）。这就是说，如果获知某个奇数C的循环周期数c,若它不能整除（C-1），就可以判定它一定是个合数。
但也有少数合数，因为其中某个质因数具有短循环周期，且多个质因数的循环周期数能够相互整除或者相等，使得质因数之间循环周期的最小公倍数也能够整除(C-1)。例如，3*11 = 33(2)，循环周期数2，就能够整除（33-1）。又例如，10001（8） = 73*137，循环周期数8，也能够整除（10001-1）；这也是因为质数为73（8）和137（8），它们的循环周期长度仍然较短且相等。不过，我们在后面还会讨论到，具有极短循环周期或者周期数相等的质数均很少，所以这种合数同样很少且易被识别。
不过，目前已有的算法，要识别出某个奇数是，或者不是合数的难度不算太大，计算复杂度大约在O(n3)的等级，这已是一种效率较高的多项式时间算法；只是当数值极大时，计算量仍然很大。
5 质因数多次方的循环周期
如果某个合数（Pk）的因数为质数P的k次方，称其为不规则短循环周期合数。所谓的不规则，不是没规律，而是循环周期长度与其它类型的合数有所差别。这种合数的循环周期，就等于质因数P本身的循环周期乘以P的(k-1)次方。例如，已知7的循环周期长度为6，那么72的循环周期为6*72-1 = 42，而73的循环周期则为6*73-1 = 6*49。又例如，11的循环周期为2，那么112的循环周期为2*112-1，即1/121 = 0.0082644628099173553719…，113的循环周期长度必然为2*113-1 = 2*121。其余以此类推。
只有3k稍微有点例外（因为3和32均属个位数，因此循环周期长度相同），但仍具有类似的规律,循环周期长度为1*3k-2。例如，32的循环周期同样为1，但33的循环周期为1*33-2 = 1*3，34的循环周期则为1*34-2=1*9，即1/81 = 0.012345679…。
6 质数和合数的循环周期可以相同
质数或者合数，有时它们的循环周期是相同的。原因与规律4有关，仍然是因为合数中含有短循环周期质因数，循环周期数能够相互整除的缘故。例如，77 = 7*11，就是因为其中既有7（6），也含有11（2），两个质因数循环周期的最小公倍数，仍然为［6,2］= 6；但是周期数6不能整除（77-1）。
7 少数质数具有相同的循环周期长度
大多数情况下，质数越大，循环周期就会越长。况且，有较大比例的质数P，具有长循环周期(P-1),它们是不可能相同的。
不过，发现少数不同的质数可以具有相同的循环周期。例如，质数7，13和41，它们的循环周期都是6。但是，随着数值的增大，具有相同循环周期长度的质数，将会越来越稀疏（详见第三章第三节）。例如，循环周期长度为6的质数，目前只发现有7，13和41；作者计算到10001，质数循环周期长度的总体趋势是越来越长，未再发现循环周期为6的质数，预计大概率也不会再有（太多）了。

二、整数之间的除法对于循环周期的影响
讨论整数之间除法的目的，是试图根据商的循环周期的变化，来获得两个整数之间的最大公约数。
1 互质的奇数相除后不改变小数点后面的循环周期长度
无论两个整数的循环周期是多少，只要它们互质，相除后循环周期的长度不会改变。
例如，已知7（6），17（16），两者相除，7/17 = 0.4117647058823529…，循环周期仍然是16。
又例如，已知7（6），13（6），虽然两个整数的循环周期长度相同，但是因为它们互质，7/13 = 0.538461…，相除后循环周期仍然不变。
2 不互质的奇数相除后循环周期可以变小
例如，119 = 7*17，循环周期长度为［6,16］= 48。如果用21除以119以后,即21/119 = 0.1764705882352941…，循环周期只有三分之一，变为16，说明21和119之间存在着一个公约数。要么这个公约数就是3（含有多次方因子）；要么这个公约数应该是3的某个倍数再加上一。据此，不难计算出公约数是7。
又例如，49 = 7*7，循环周期为，6*7 = 42。如果发现用整数21除以49以后，21/49 = 0.428571…，循环周期只有七分之一，变为6，则说明它们之间存在着一个公约数。要么这个公约数应该是7的某个倍数再加上一，要么这个公约数就是7。
这就是说，只要两个整数a*g和b*g之间存在着公约数g，是可以根据循环周期的变化情况来找到它的。尤其是当a和b的数值比较小，而g的数值相对来说比较大时，这种算法的计算效率较高。
3 不互质的奇数相除后循环周期也可以不变
例如，已知91 = 7*13，其中7（6），13（6）；而119 = 7*17，c =［6,16］= 48。虽然91和119不互质，它们之间有公约数7，但是，119/91 = 17/13 = 1.307692…，循环周期仍然是6，没有变化。究其原因，是因为91中含有两个循环周期长度为6的因数。
不过，如果把它们颠倒过来，91/119 = 0.7647058823529411…，循环周期的长度为16，仅为119（48）原有的三分之一，要么这个公约数就是3，要么这个公约数应该是3的某个倍数再加上一。
具有相同循环周期的质数非常少，所以本节讨论的情况也可被识别出。

三、循环周期复杂度
此前，没有文献讨论过有理数循环周期长度的复杂度问题。本章讨论这个问题的目的，是想为从新的角度来寻找极大质数的路径，打下一个基础。
显然，奇数N若具有长循环周期（N-1），其循环周期复杂度是指数时间等级的。但本文不准备就此展开讨论，因为尚无法明确地指出，哪些整数一定会具有长循环周期；若能如此，根据第一章中的规律2，这将等同于可以给出一个确定性的质数公式或者算法。
本章主要讨论循环周期为多项式时间等级，具有短或极短循环周期的奇数。
1 多项式时间等级循环周期定义
设某一类(个)奇数N的二进制长度为n，如果它（们）的循环周期长度c，要始终小于或等于nk，其中k是一个常数，那么它的循环周期为多项式时间等级O（nk)；其中既有合数，也可有质数。
例如，11（2），因为n = 4，而c=2，所以它是一个多项式时间等级循环周期的质数，仅为O（n)。但是，讨论单个数值的循环周期长度等级并没有太多意义，只是知道了而已。
关键是要能够指出某一类的数值或者函数，其中可以包含有任意多、也任意大的数值，无论它们是合数还是质数，循环周期都是某一个多项式时间等级的；并且能够从中可以找出一些有价值的规律，帮助我们用较少的计算量，寻找出极大的质数。
2 某类多项式时间等级循环周期的数值
具备多项式时间等级循环周期的数值，种类应该不止一个。本文给出并详细讨论一种具有特殊结构特征的数值，10…01，其最高和最低位数是1，中间全是0；为了讨论方便，称其为“101”数。无论“101”数中间有多少个0，数值变得多么大，它的循环周期复杂度始终都是O（n）。这类数值的特点非常有味道，在作者将要提出的一个数论新分支中占有重要地位，请有缘的读者禅悟。请看下表。
表2 10…01类型数值循环周期长度及因数分解列表
“101”数        数性        因数分解        循环周期数c以及质因数的循环周期
11        质数                2   1/11=0.09…
101        质数                4   1/101=0.0099…
1001        合数        11*7*13        6 其中:11（2）7（6）13（6）
10001        合数        73*137        8 其中:73（8）137（8）
100001        合数        11*9091        10 其中:9091（10）
1000001        合数        101*9901        12 其中:101（4）9901（12）
10000001        合数        11*909091        14 其中:909091（14）
100000001        合数        17*5882353        16 其中:17（16）5882353（16）
1000000001        合数        11*7*13*19*52579        18 其中:19（18）52579（18）
10000000001        合数        101*3541*27961        20 其中:3541（20）27961（20）
100000000001        合数        112*23*4093*8779        22 其中:23（22）4093（22）8779（22）
1000000000001        合数        73*137*99990001        24 其中:99990001（24）
10000000000001        合数        11*859*1058313049        26 其中：859（26）1058313049（26）
100000000000001        合数        29*101*281*121499449        28 其中：29（28）281（28）121499449（28）
1000000000000001        合数        11*7*13*211*241*2161*9091        30其中：211（30）241（30）2161（30）
10000000000000001        合数        353*449*641*1409*69857        32 其中：353（32）449（32）641（32）1409（32）69857（32）
100000000000000001        合数        11*103*4013*21993833369        34 其中：103（34）4013（34）21993833369（34）
1000000000000000001        合数        101*9901*999999000001        36 其中：999999000001（36）
作者一共计算到了具有这种数值结构特点的一百二十八位（十进制）长的数值，可以证实“101”数具有如下的规律：
1.        无论“101”数中间有多少个0，数值有多么大，循环周期长度c与0的个数，始终成正比例增长。假设其中0的个数为k，那么，c = 2*k+2，这样循环周期复杂度就会始终保持在O（n）的等级，即c ≤ n。
2.        当0的个数为偶数时，其中必有一个因数为11。例如，1001 = 11*7*13。
3.        无论其中0的个数有多少，除去一些较小的因数以外，较大因数的循环周期都是相等的，并且与合数循环周期的长度相同，即使这些质因数本身的循环周期是指数时间等级的。
4.        只有具有偶循环周期的质数，才有可能成为其中的因子。例如，1000000000001（24）= 73*137*9999001，其中的因数为73（8），137（8），9999001（24）。
5.        无论数值有多么大，当10…01＞101以后，始终都是合数，循环周期随之同步地增长，将覆盖每一个偶数数值。这样就可以间接地证实，所有的偶数数值，都至少对应有一个具有同样循环周期长度的质数。
综上所述，从“101”数的循环周期始终较小，而循环周期与之相等的质因数并不多见的角度，来看待此类数值，其中有一种具有特殊结构特点的质数就令作者非常感兴趣（将另文进行探讨）。
3 循环周期长度为O（n）的质数密度
既然“101”数大多都是合数，循环周期复杂度始终为O（n），而它们的质因数相对较小，且循环周期都要小于或等于合数的循环周期，那么我们不妨换个角度来看看，循环周期为O（n）的这类质数到底多不多？
小于101的奇质数有24个，其中有：3（1），11（2），37（3），41（5），共四个，均为c ≤ n。
大于99小于201的质数有21个，其中有：101（4），137（8），共二个。
大于199小于301的质数有16个，其中有：239（7），271（5），共二个。
大于299小于10001的质数中，只有4649（7），9091（10），9901（12），共三个。
在小于10001的一千多个质数中，只有上述十一个具有极短循环周期的质数；而且随着数值的增大，这种质数的分布将会越来越稀疏，要远低于质数的稀疏度。
其中循环周期长度为偶数的质数，例如11（2），101（4），137（8），9091（10），9901（12），全部都在“101”数的因数中出现过。
初步计算结果还表明，任意一个偶数值，不一定都会有多个具有相同循环周期的质数与之对应。例如，只发现有质数11的循环周期长度是2，质数101的循环周期长度是4，质数9091的循环周期长度是10，质数9901的循环周期长度是12，…。至于将来能否发现更多具有相同循环周期的质数是另外一回事，起码我们现在知道，具有相同循环周期的质数并不多；尤其是数值相差并不太大，但是循环周期却相同的质数并不多。
作者认为所有的奇数数值，也会有某个质数的循环周期与之相对应，例如，3（1），37（3），41（5），239（7）等等。有兴趣的读者，可以自行计算另外一种结构上具有特点的数值，1…1，它们每一位上的数字都是1。这种“全1数”的循环周期数更短，只与位长相等，分别呈奇、偶数同步地增长。例如，11(2)；111 = 3*37，其中37（3）；1111 = 11*101，其中101（4）；11111 = 41*271，其中41(5)，271（5）；111111 = 3*7*11*13，其中13(6)；1111111 = 239*4649，其中239(7)，4649（7）；…。只有位长为二、十九、二十三时是质数，其余都是合数。

四、展望
想要寻找出极大、更大或者任意大的质数，一直是学者们持之以恒的工作方向，但目前仍然没有太好的方法。
有了本文在第一章，规律2和规律3中对于长循环周期质数的讨论，再结合“101”数的一些特点，作者有一个看法：借助具有某种结构特点的数值，在具有短或极短循环周期的奇数中，来寻找极大甚至是任意大的质数，或许是一个突破的方向。本文先做一些基础性的研究，首先找出哪类数值具有极短循环周期，在下一篇论文中再进一步展开讨论。