题目129：考察被n整除的最小循环整数
Repunit divisibilityA 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 。
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
页:
[1]