130. 具有素数全一数性质的合数(Composites with Prime Repunit Property)
完全由数字 1 组成的数称为全一数（repunit）。定义 \(R(k)\) 为长度为 \(k\) 的全一数；例如 \(R(6)=111111\)。 给定正整数 \(n\) 且 \(\gcd(n,10)=1\)，可以证明总存在某个 \(k\) 使得 \(R(k)\) 能被 \(n\) 整除，记 \(A(n)\) 为满足该条件的最小 \(k\)；例如 \(A(7)=6\)，\(A(41)=5\)。 已知对所有素数 \(p>5\)，\(p-1\) 都能被 \(A(p)\) 整除。例如当 \(p=41\) 时，\(A(41)=5\)，而 \(40\) 能被 \(5\) 整除。 然而，存在少数满足同样性质的合数；前五个例子为 \(91\)、\(259\)、\(451\)、\(481\)、\(703\)。 求满足 \(\gcd(n,10)=1\) 且 \(n-1\) 能被 \(A(n)\) 整除的前二十五个合数的和。
分析：本题的关键在于将 \(A(n)\) 的条件转化为模幂判定，从而避免显式计算 \(A(n)\)。核心是 \(A(n) = \operatorname{ord}_{9n}(10)\)（10 模 \(9n\) 的乘法阶），而 \(A(n) \mid (n-1)\) 当且仅当 \(10^{n-1} \equiv 1 \pmod{9n}\)。由此可将搜索简化为逐一检查模幂条件，配合 Miller-Rabin 素数检测筛除素数。
一、数学背景
全一数 \(R(k)\) 可写作：
\(n\) 整除 \(R(k)\) 等价于 \(9n\) 整除 \(10^k - 1\)，即：
因此 \(A(n)\) 正是 10 在模 \(9n\) 乘法群中的阶：
条件“\(n-1\) 能被 \(A(n)\) 整除”即 \(A(n) \mid (n-1)\)。由乘法阶的基本性质，\(A(n) \mid (n-1)\) 当且仅当 \(10^{n-1} \equiv 1 \pmod{9n}\)。
对于 \(\gcd(n,3)=1\) 的情况，由于 \(10 \equiv 1 \pmod{9}\)，\(10^{n-1} \equiv 1 \pmod{9}\) 自动成立，条件退化为 \(10^{n-1} \equiv 1 \pmod{n}\)——这正是基-10 的 Fermat 伪素数判定条件。
二、算法设计
1) 线性搜索框架
从 \(n=3\) 开始递增遍历奇数（跳过 5 的倍数以保证 \(\gcd(n,10)=1\)），对每个候选 \(n\) 执行两步检查：
- 模幂检验：计算 \(10^{n-1} \bmod (9n)\)，判断是否等于 1。Python 内置
pow(10, n-1, 9*n)使用快速幂，效率极高。 - 合数检验：对通过模幂检验的 \(n\)，用确定性 Miller-Rabin 测试判断是否为合数。基数选取 \(\{2,3,5,7,11,13,17\}\)，对 \(n<2^{64}\) 保证确定性。
2) 搜索终止
累积到目标数量（25 个）时停止。搜索上界设为 \(10^7\)，实际搜索过程中远早于此界即找到全部 25 个数。
三、复杂度分析
- 每个候选 \(n\) 的
pow(10, n-1, 9*n)为 \(O(\log n)\) 次模乘。 - Miller-Rabin 仅对通过模幂检验的极少数候选执行（在 \(10^7\) 内不超过百个），开销可忽略。
- 总搜索至多遍历约 \(4 \times 10^6\) 个候选（\(10^7\) 以内 40% 奇数且跳 5），每次 \(O(\log n)\) 模乘，总时间远小于 1 秒。
四、代码实现与说明
"""Project Euler 130 - Composites with Prime Repunit Property."""
from math import gcd
from time import perf_counter
def is_prime_mr(n: int) -> bool:
"""Deterministic Miller-Rabin primality test for n < 2^64."""
if n < 2:
return False
# small primes
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
if n in small_primes:
return True
for p in small_primes:
if n % p == 0:
return False
# write n-1 = d * 2^s
d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1
# deterministic bases for n < 2^64
for a in [2, 3, 5, 7, 11, 13, 17]:
if a >= n:
continue
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s - 1):
x = (x * x) % n
if x == n - 1:
break
else:
return False
return True
def solve(target_count: int = 25) -> int:
"""Find the sum of the first `target_count` composite n
satisfying gcd(n,10)=1 and (n-1) divisible by A(n).
"""
found = []
n = 3
# search bound - increase if needed
max_n = 10 ** 7
while len(found) < target_count and n < max_n:
n += 2 # only odd numbers (gcd with 2)
if n % 5 == 0:
continue # skip multiples of 5
# Check: 10^(n-1) == 1 (mod 9*n)
if pow(10, n - 1, 9 * n) == 1:
if not is_prime_mr(n):
found.append(n)
if len(found) < target_count:
raise RuntimeError(
f"Only found {len(found)} composites up to {max_n}. "
"Increase search bound."
)
return sum(found)
if __name__ == "__main__":
t0 = perf_counter()
result = solve(25)
elapsed = perf_counter() - t0
print(f"Result: {result}")
print(f"Time: {elapsed:.3f}s")
导入与常量
math.gcd用于显式的 \(\gcd\) 检查（实际代码中通过跳过偶数和 5 的倍数隐式保证 \(\gcd(n,10)=1\)）time.perf_counter测量执行时间
is_prime_mr
- 确定性 Miller-Rabin 素数检测
- 先用小素数试除快速排除大部分合数
- 将 \(n-1\) 分解为 \(d \cdot 2^s\)
- 对基数 \(\{2,3,5,7,11,13,17\}\) 验证二次探测条件，七个基数足以覆盖 \(n<2^{64}\) 范围内的所有情况
solve
- 初始化空列表
found存储找到的合数 - 从 \(n=3\) 开始，每次加 2 保证 \(\gcd(n,2)=1\)
- 跳过 5 的倍数保证 \(\gcd(n,5)=1\)，由此满足 \(\gcd(n,10)=1\)
pow(10, n-1, 9*n) == 1等价于 \(A(n) \mid (n-1)\)- 对满足模幂条件的 \(n\)，调用
is_prime_mr排除素数 - 集齐 25 个后返回其和
主入口
- 计时并输出结果与运行时间