# 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][0] == 0 and t[1][0] == 0: return False if t[0][-1] == n - 1 and (t[1][-1] & 1 == 0 or t[1][-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] == 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 while not found_l: for i in generator(n, d, rep): if not is_prime(i): continue found_l.append(i) rep -= 1 result += sum(found_l) print("The result is:", result)

The Python file is available for download: problem111.py.