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][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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License