对任意最简分数$a/b$（即$\gcd(a,b)=1$），显然当且仅当b具有$b=2^j5^k$的形式时它才能表示为有限小数。若$b=2^j5^kd$，其中d不能被2或5整除，则可以找到合适的$a_1,a_2$从而将$a/b$写作
$$\frac{a}{b}=\frac{a}{2^j5^kd}=\frac{a_1}{2^j5^k}+\frac{a_2}{d}$$
其中等式右侧的第一项是有限小数。因此不失一般性地，只需考虑b不能被2或5整除的情况。
若$a/b$和$a'/b'$的循环节长度分别是c和c'，则显然$(ab'+a'b)/(bb')=a/b+a'/b'$的循环节长度是$\mathrm{lcm}(c,c')$，因此通过将分母作质因数分解后拆分可以把问题进一步归约为考察b是素幂数的情况。
设d是循环节内的数字所代表的整数（即题中括号内的数字，例如142857），循环节的长度是k，则有
$$\frac{a}{b}=d(10^{-k}+10^{-2k}+\ldots)=d\times 10^{-k}\times \frac{1}{1-10^{-k}}=\frac{d}{10^k-1},$$
即
$$a(10^k-1)=bd.$$
由$\gcd(a,b)=1$可得b能整除$10^k-1$。至此已经可以通过以下程序求得结果$983$。对应循环节的长度是982。
此外，从上述分析还可以看出10在模b的乘法群中具有k阶，因此k能整除$\tau(b)$，其中$\tau$是欧拉totient函数。
d=[10**k-1 for k in range(1000)]
mc=0
mb=0
for b in range(3,1000):
if b%2!=0 and b%5!=0:
k=1
while d[k]%b!=0:
k+=1
if k>mc:
mc=k
mb=b
print mb,mc
|
