循环数

若一个n位数依次乘以$1, 2, 3, \ldots, n$所得的积分别是原数各位数字的轮转循环，则称其为循环数。

最小的循环数是6位数142857： \begin{align*} 142857 \times 1 &= 142857 \\ 142857 \times 2 &= 285714 \\ 142857 \times 3 &= 428571 \\ 142857 \times 4 &= 571428 \\ 142857 \times 5 &= 714285 \\ 142857 \times 6 &= 857142 \end{align*} 142857之后的下一个循环数是16位数0588235294117647： \begin{align*} 0588235294117647 \times 1 &= 0588235294117647 \\ 0588235294117647 \times 2 &= 1176470588235294 \\ 0588235294117647 \times 3 &= 1764705882352941 \\ \ldots 0588235294117647 \times 16 &= 9411764705882352 \\ \end{align*} 注意循环数的定义是允许引入前导零的。

存在一个唯一的循环数，其最左侧的11位数字是00000000137，最右侧的5位数字是56789。求这个数的各位数字之和。

本题难度:

解答

根据OEIS A180340的信息，只需要找到素数p，使得$1/p$的小数部分循环节长度为$p-1$，那么$1/p$的循环节就是一个循环数。

这样的p在OEIS A001913中给出，它等同于要求10为模p乘法群中的生成元。

根据题面的信息，$1/p$应该在$0.00000000137$和$0.00000000138$之间，由此可得p在724637681和729927007之间。

遍历此范围内的数并检验以上条件很快就能求得最终结果$3284144505$。

注：以下代码使用sympy库的is_primitive_root和isprime函数来分别检验10是否是模p乘法群中的生成元以及p的素性，因此代码为Python 3。

from sympy import is_primitive_root,isprime

for p in range(724637681,729927008,2):
    if 56789*p%100000==99999 and isprime(p) and is_primitive_root(10,p):
        print(f"p={p}, the answer is {(p-1)//2*9}")
        break