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.
