Project Euler 111

题目

Primes with runs

Considering $4$-digit primes containing repeated digits it is clear that they cannot all be the same: $1111$ is divisible by $11$, $2222$ is divisible by $22$, and so on. But there are nine $4$-digit primes containing three ones:

$$1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111$$

We shall say that $M(n, d)$ represents the maximum number of repeated digits for an $n$-digit prime where $d$ is the repeated digit, $N(n, d)$ represents the number of such primes, and $S(n, d)$ represents the sum of these primes.

So $M(4, 1) = 3$ is the maximum number of repeated digits for a $4$-digit prime where one is the repeated digit, there are $N(4, 1) = 9$ such primes, and the sum of these primes is $S(4, 1) = 22275$. It turns out that for $d = 0$, it is only possible to have $M(4, 0) = 2$ repeated digits, but there are $N(4, 0) = 13$ such cases.

In the same way we obtain the following results for $4$-digit primes.

$\mathbf{Digit, d}$	$\mathbf{M(4, d)}$	$\mathbf{N(4, d)}$	$\mathbf{S(4, d)}$
$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$

For $d = 0$ to $9$, the sum of all $S(4, d)$ is $273700$.

Find the sum of all $S(10, d)$.

解决方案

本题主要通过位运算的手段来枚举。

这里用一个$N$比特数$mask$表示一个$N$位数的状态。对于某个数位$d(0\leq d\leq 9)$，如果任意一个$N$位数，第$i$位为$d$，那么状态$mask$的第$i$位为$1$，否则为$0$。

以题目中的数字为例，如$d=1,N=4$时，$1117$表示成状态$(1110)_2$，$2111$为状态$(0111)_2$。

将所有的$N$比特状态值枚举出来，将状态按其中比特为$1$的数量$b$进行分类。

按照比特为$1$的数量$b$，从大到小枚举每个分类，遍历分类中所有的状态，然后通过递归生成对应状态$mask$下的所有数。在这些拥有$b$个某数位$d$的数中，如果存在一个数是质数，那么就有$M(N,d)=b$，第一次找到的结果就是最优的。找完其它有$b$个$d$的质数后，那么循环就可以停下来，不用再往后判断$b-1$个$d$的那些数了。

另外，还需要注意最高位不能填$0$这种情况。

代码

from tools import is_prime

N = 10

ls = [[] for i in range(N)]
for s in range(1, (1 << N) - 1):
    ls[bin(s).count('1')].append(s)


def gen(msk: int, f: int, digit: int, num: int, a: list):
    if f == -1:
        if isprime(num):
            a.append(num)
        return
    if msk >> f & 1:
        if digit == 0 and f == N - 1:
            return
        else:
            gen(msk, f - 1, digit, num * 10 + digit, a)
    else:
        # 如果是在最高位任意填，那么必须从1开始填，否则从0开始填。
        for k in range(int(f == N - 1), 10):
            if k != digit:
                gen(msk, f - 1, digit, num * 10 + k, a)


ans = 0
for digit in range(10):
    for bits in range(N - 1, 0, -1):
        a = []
        for v in ls[bits]:
            gen(v, N - 1, digit, 0, a)
        s = sum(a)
        if s:
            ans += s
            break
print(ans)