题目133：考察哪个质数永远无法证整除长度为10^n的循环整数

欧拉计划

Repunit nonfactors

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.

Let us consider repunits of the form R(10ⁿ).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10ⁿ) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10ⁿ).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10ⁿ).

题目：

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

让我们考虑形如 R(10ⁿ) 的循环整。

尽管 R(10)，R(100)，和 R(1000) 都无法被 17 整除，但是 R(10000) 可以。但是不存在 n 使得 R(10ⁿ) 能够被 19 整除。事实上，在 100 以下的质数中只有 11，17，41 和 73 这四个能够成为某个 R(10ⁿ) 的因子。

求 100000 以下不能整除任何 R(10ⁿ) 的质数的和。

l910607

抛砖引玉。

import time
import math
t0 = time.time()


MAXPRIME = 100000
max2, max5 = int(math.log(MAXPRIME, 2)), int(math.log(MAXPRIME, 5))   # 2的最高次幂和5的最高次幂
MAXN = int(math.pow(10, max(max2, max5)))


ISPRIME = [True]*MAXPRIME
ISPRIME[0] = ISPRIME[1] = False
for i in range(2, MAXPRIME//2):
    if ISPRIME[i] == False:
        continue
    for j in range(i*i, MAXPRIME, i):
        ISPRIME[j] = False

count, sum = 3, 10     # 10^n一定不能整除2、3和5，不参与循环，计入初始值。
for p in range(7, MAXPRIME, 2):
    if ISPRIME[p]:
        if pow(10, MAXN, 9*p) != 1:
            count += 1
            sum += p
            # print([count, p], end='\t')


print("Answer: ", sum)
print("Running time: ", time.time()-t0, "s")

Answer:  453647705
Running time:  0.10031580924987793 s