Project Euler Problem 111

# Statement

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.

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

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

# Solution

Basically the solution is to bruteforce through all combinations by replacing one digit, if there are no primes in them, then replace 2 and so on until I find primes in them.

The trick consists in generating the combinations efficiently.

```from itertools import product, combinations, zip_longest
from CommonFunctions import find_primes_less_than

primes = find_primes_less_than(350000)

def is_prime(n):
for p in primes:
if p >= n:
return True
if n % p == 0:
return False
return True

def generator(n, d, rep):

def filt_func(t):
if t == 0 and t == 0:
return False
if t[-1] == n - 1 and (t[-1] & 1 == 0 or t[-1] == 5):
return False
return True

others_indexes = combinations(range(n), n - rep)
others_numbers = product(*([tuple(set(range(10)) - set([d]))] * (n - rep)))
joined = filter(filt_func, product(others_indexes, others_numbers))
for tup in joined:
base = [d for i in range(n)]
for ind, val in zip_longest(*tup):
base[ind] = val
if base == 0 or base[-1] & 1 == 0 or base[-1] == 5:
continue
yield int(''.join(map(str, base)))

if __name__ == '__main__':
result = 0
n = 10
for d in range(0, 10):
found_l = []
rep = n - 1