111. 素数游程(Primes with Runs)
考察包含重复数位的n位素数。对于4位素数，它们不能所有数位都相同：1111能被11整除，2222能被22整除，以此类推。然而，有9个4位素数包含三个1：1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111。
定义M(n,d)为n位素数中数位d的最大重复次数，N(n,d)为这样的素数的个数，S(n,d)为这些素数的和。
当d=1时：M(4,1)=3, N(4,1)=9, S(4,1)=22275。当d=0时：M(4,0)=2, N(4,0)=13。
对于4位素数，各数位d的结果如下表所示。所有S(4,d)的和为273700。
d M N S 0 2 13 67061 1 3 9 22275 2 3 1 2221 3 3 12 46214 4 3 2 8888 5 3 1 5557 6 3 1 6661 7 3 9 57863 8 3 1 8887 9 3 7 48073 求所有S(10,d)的和（d=0..9）。
一、数学背景
本题的核心是搜索具有特定数位重复模式的10位素数。对于每个数位d（0-9），我们需要找到一个10位素数，使得d在其中出现的次数最大化，然后对所有满足条件的素数求和。
关键观察： - 对于非零数位d，最大重复次数不可能达到10（全相同的10位数必然被11整除，因为\(1111111111 = 11 \times 101010101\)） - 对于d=0，最大重复次数不可能达到10（首位不能为0，且全0不可行） - 因此最大重复次数M(10,d)最多为9
二、算法设计
采用贪心递减策略：对于每个d，从k=10开始向下尝试，生成所有恰好有k个d的10位数，检测素数。第一个产生素数的k即为M(10,d)，对应素数之和即为S(10,d)。
候选数生成： - 从10个位置中选择k个位置放置d - 对剩余位置填充其他数位（0-9中除d以外的数位） - 使用笛卡尔积生成所有填充组合 - 特别处理：d=0时，首位（位置0）必须是1-9；d≠0时，首位可以是d但不能是0
素数检测： - 使用确定性Miller-Rabin测试，基数为[2,3,5,7,11,13] - 该组基数对于\(n < 3.5 \times 10^{12}\)范围内的所有整数具有100%确定性 - 快速预过滤：末位为偶数或5的数直接跳过
搜索空间分析： - k=9: 最多\(\binom{10}{9} \times 9 = 90\)个候选（d≠0） - k=8: 最多\(\binom{10}{8} \times 9^2 = 3645\)个候选 - k=7: 最多\(\binom{10}{7} \times 9^3 = 87480\)个候选 - 实际运行中M(10,d)在7-9之间，总搜索量极小
三、复杂度分析
- 时间复杂度：最坏情况\(O(10 \times \sum_{k} \binom{10}{k} \times 9^{10-k} \times \log n)\)，但实测仅需约0.005秒
- 空间复杂度：\(O(1)\)，仅需存储当前候选集
- 实际搜索空间远小于理论上限，因为大多数d的M值在8或9
四、代码实现与说明
#!/usr/bin/env python3
"""
Project Euler Problem 111: Primes with Runs
"""
import time
from itertools import combinations, product
MR_BASES = [2, 3, 5, 7, 11, 13]
def is_prime(n):
"""Deterministic Miller-Rabin primality test valid for n < 3.5e12."""
if n < 2:
return False
if n in (2, 3, 5, 7, 11, 13):
return True
if n % 2 == 0:
return False
d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1
for a in MR_BASES:
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
常量区
MR_BASES：Miller-Rabin确定性测试的基数列表，对于\(n < 3.5 \times 10^{12}\)范围内的所有整数，使用这6个基数可以得到确定性的素数判定结果
is_prime函数
- 处理边界情况：\(n < 2\)返回
False，小素数直接返回True，偶数返回False - 将\(n-1\)分解为\(d \times 2^s\)的形式
- 对每个基数\(a\)计算\(a^d \bmod n\)，若结果为1或\(n-1\)则通过本轮测试
- 否则反复平方，检查是否得到\(n-1\)；若循环结束仍未得到\(n-1\)，则\(n\)为合数
- 所有基数通过则\(n\)为素数
def s_for_digit(d, num_digits=10):
"""Compute S(num_digits, d) for digit d."""
for k in range(num_digits, 0, -1):
primes_set = set()
other_count = num_digits - k
if d == 0:
non_leading = list(range(1, num_digits))
if k > len(non_leading):
continue
for zero_pos in combinations(non_leading, k):
zero_set = set(zero_pos)
other_pos = [p for p in range(num_digits) if p not in zero_set]
iterables = []
for p in other_pos:
if p == 0:
iterables.append(range(1, 10))
else:
iterables.append([dig for dig in range(10) if dig != d])
for values in product(*iterables):
last_pos = num_digits - 1
if last_pos in zero_set:
last_digit = 0
else:
last_idx = other_pos.index(last_pos)
last_digit = values[last_idx]
if last_digit % 2 == 0 or last_digit == 5:
continue
val_idx = 0
n = 0
for pos in range(num_digits):
if pos in zero_set:
n = n * 10
else:
n = n * 10 + values[val_idx]
val_idx += 1
if is_prime(n):
primes_set.add(n)
s_for_digit函数（d=0分支）
- 从\(k = 10\)开始向下递减，尝试每个可能的重复次数
- 对于d=0，重复的0不能出现在首位（位置0），因此从位置1-9中选择k个位置
other_pos：需填充其他数位的位置列表- 构建
iterables：首位（位置0）的取值范围为1-9，其余位置的取值范围为0-9中除了d以外的数位 - 使用
itertools.product生成所有填充组合的笛卡尔积 - 快速过滤：末位为偶数或5的数不可能是素数（除了2和5本身，但10位数的末位不可能是2或5）
- 按位置构建整数：若位置在
zero_set中则填入0，否则从当前填充值中取下一个数位 - 通过素数检测的数加入结果集合
else:
all_pos = list(range(num_digits))
if k > num_digits:
continue
for d_pos in combinations(all_pos, k):
d_set = set(d_pos)
other_pos = [p for p in range(num_digits) if p not in d_set]
iterables = []
for p in other_pos:
if p == 0:
iterables.append([dig for dig in range(1, 10) if dig != d])
else:
iterables.append([dig for dig in range(10) if dig != d])
for values in product(*iterables):
last_pos = num_digits - 1
if last_pos in d_set:
last_digit = d
else:
last_idx = other_pos.index(last_pos)
last_digit = values[last_idx]
if last_digit % 2 == 0 or last_digit == 5:
continue
val_idx = 0
n = 0
for pos in range(num_digits):
if pos in d_set:
n = n * 10 + d
else:
n = n * 10 + values[val_idx]
val_idx += 1
if is_prime(n):
primes_set.add(n)
if primes_set:
return sum(primes_set)
return 0
s_for_digit函数（d≠0分支）
- 从位置0-9中选择k个位置放置d
other_pos：需填充其他数位的位置- 首位（位置0）的取值范围为1-9中除了d以外的数位（确保10位数）；其他位置为0-9中除了d以外的数位
- 使用
itertools.product生成所有组合 - 快速过滤末位为偶数或5的数
- 按位置构建整数：若位置在
d_set中填入d，否则从填充值中取值 - 第一个产生素数的k即为\(M(10,d)\)，对应素数之和为\(S(10,d)\)
def solve():
"""Compute sum of S(10,d) for d = 0..9."""
total = 0
for d in range(10):
s_d = s_for_digit(d, 10)
total += s_d
return total
def main():
start = time.time()
answer = solve()
elapsed = time.time() - start
print(f"Sum of S(10,d) for d=0..9: {answer}")
print(f"Time: {elapsed:.3f}s")
if __name__ == "__main__":
main()
solve和main函数
solve：对d=0..9依次调用s_for_digit，累加得到最终结果main：计时并输出答案- 程序入口为标准Python格式