026. 倒数周期(Reciprocal cycles)

一个单位分数就是分子为一的分数,分子从二到十的单位分数的小数表示分别如下:

$$ \begin{aligned} 1/2&=0.5\\ 1/3&=0.(3)\\ 1/4&=0.25\\ 1/5&=0.2\\ 1/6&=0.1(6)\\ 1/7&=0.(142857)\\ 1/8&=0.125\\ 1/9&=0.(1)\\ 1/10&=0.1 \end{aligned} $$
其中\(0.1(6)\)的意思是\(0.166666\cdots\),它的循环节长度是一位,可以看到\(1/7\)的循环节长度是六位。对于\(d<1000\),求使得\(1/d\)包含的循环节长度最长的\(d\)的值。

分析:这道题的解题思路可以大致分为两个部分,第一个部分是如何求任意单位分数的循环节,这需要使用一个简单的迭代计算就可以实现。第二个部分是为了提高算法的效率,我们需要尽可能的减小筛选的单位分数的范围,这需要我们从数论角度来分析单位分数的循环节问题。

首先我们来看第一个部分,要求循环节的长度,我们可以建立一个列表记下每次除法中的被除数,由于都是单位分数,所以第一个被除数为1,如果被除数小于除数,则需要将被除数进一位再去除,所得余数为下一次除法中的被除数。如此循环下去,直到新出现的被除数在我们建立的列表中已经出现过了,之后的计算会重复之前的模式。此时一个循环已经完成,列表的长度就是循环节的长度。如对于\(1/7\)计算循环节长度的过程如下:

$$ 1\ mod\ 7 \qquad \rightarrow \qquad [1]\\ 10\ mod\ 7=3 \qquad \rightarrow \qquad [1,3]\\ 30\ mod\ 7=2 \qquad \rightarrow \qquad [1,3,2]\\ 20\ mod\ 7=6 \qquad \rightarrow \qquad [1,3,2,6]\\ 60\ mod\ 7=4 \qquad \rightarrow \qquad [1,3,2,6,4]\\ 40\ mod\ 7=5 \qquad \rightarrow \qquad [1,3,2,6,4,5]\\ 50\ mod\ 7=1 \qquad \rightarrow \qquad [1,3,2,6,4,5,1]\\ $$

第二个部分我们需要尽量的缩小筛选的范围,排除那些明显不满足题目要求的单位分数。首先我们要排除那些非循环小数,或者说循环节为零的小数。对于分子为一的单位分数,当它的分母为二或者五的倍数时,这个单位分数的小数表示必然是非循环小数,如\(1/2,1/4,1/5,1/10\)等等。一般地,设一个单位分数为\(1/(2^x5^y)\)的形式,其中\(x,y\in N\),则有:

$$ \frac{1}{2^x5^y}=\frac{1}{2^x5^y}\cdot\frac{2^y5^x}{2^y5^x}=\frac{2^y5^x}{(2\cdot5)^{x+y}}=\frac{2^y5^x}{10^{x+y}} $$

如对于\(1/8\),有:

$$ \frac{1}{8}=\frac{1}{2^35^0}=\frac{2^05^3}{10^3}=\frac{125}{1000}=0.125 $$

对于小数表示不是循环小数的单位分数\(1/d\),假设其循环节长度为\(n\),则满足\(10^n\equiv1(mod\ d)\),这里的\(n\)是满足以上等式的最小数,如\(10^6-1=99999=7\times142857\),所以\(1/7\)的循环节长度为7。根据循环节的定义,每次除法中所得余数最大只能为\((d-1)\),所有余数只能在\([1,d-1]\)的范围中取,所以循环节的长度最多为\((d-1)\),否则就会出现两个相同的余数,导致循环节结束。

根据费马小定理,对于素数\(p\),假设\(gcd(a,p)=1\),那么\(a^{p-1}\equiv1(mod\ p)\),则如果素数\(p\)满足\(gcd(10,p)=1\),那么\(10^{p-1}\equiv1(mod\ p)\),根据上面的分析,易知对于某一类素数\(p\),它的循环节长度为\((p-1)\)。为了实现这一点,则对于这一类素数,只有\((p-1)\)使得\(10^{p-1}\equiv1(mod\ p)\)成立以外,其它任何小于\((p-1)\)的数\(k\)都不能使得等式成立,否则循环节长度就是\(k\),而不是\((p-1)\)。因此为了求得1000以内循环节长度最长的单位分数,可从999逐一开始尝试,先判断它是否是质数以及是否和10互质,如果不是则直接排除。如果是,则求它的循环节长度,如果循环节长度不等于该数减去一,则排除,如果等于则为所求。

from math import gcd
from sympy import isprime

def repeat_num(n):
    rem = [1]
    while True:
        rem.append(10*rem[-1]%n)
        if rem[-1] == 0:
            return 0
        elif rem[-1] in rem[:-1]:
            return (len(rem)-1)

def main(n=1000):
    for i in range(n,1,-1):
        if gcd(10,i) == 1 and isprime(i):
            rep_num = repeat_num(i)
            if rep_num == i-1:
                return i