题目129：考察被n整除的最小循环整数

欧拉计划

Repunit divisibility

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

The least value of n for which A(n) first exceeds ten is 17.

Find the least value of n for which A(n) first exceeds one-million.

题目：

如果一个数全部由 1 组成，称之为一个循环整数。定义 R(k) 为长度为 k 的循环整数，例如 R(6) = 111111。

已知 n 是正整数以及 GCD(n, 10) = 1，可以证明，总存在一个 k 值使得 R(k) 可以被 n 整除，用 A(n) 表示这些 k 值中最小的，例如 A(7) = 6，A(41) =5。

使得 A(n) 超过 10 的最小的 n 是 17。

找出使得 A(n) 超过一百万的最小的 n 。

jerryxjr1220

from math import gcd
def A(n):
        if gcd(n, 10) != 1: return 0
        x, k = 1, 1
        while x != 0:
                x = (x*10+1) % n
                k += 1
        return k
n = limit = 1000001
while A(n)<limit:
        n += 2
print(n)

1000023