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/2,1/4,1/5,1/10\)等等。一般地，设一个单位分数为\(1/(2^x5^y)\)的形式，其中\(x,y\in N\)，则有：

如对于\(1/8\)，有：

对于小数表示不是循环小数的单位分数\(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