def prime_concat_partners(list_, primes, failure_point):
    result = {}

    length = len(list_)
    for first in range(length - 1):
        n1 = list_[first]
        for second in range(first + 1, length):
            n2 = list_[second]
            cand1 = int(str(n1) + str(n2))
            cand2 = int(str(n2) + str(n1))
            if is_prime(cand1, primes=primes, failure_point=failure_point):
                if is_prime(cand2, primes=primes, failure_point=failure_point):
                # sets value to [] if not set, returns value at key
                result.setdefault(n1, []).append(n2)
                result.setdefault(n2, []).append(n1)
    return result

def possible_pairings(partner_hash, length):
    # length = 1
    result = [[key] for key in partner_hash]
    for size in range(2, length + 1):
        next_iteration = []
        for subset in result:
            possible_additions = partner_hash[subset[0]]
            for val in subset:
                possible_additions = [entry for entry in possible_additions
                                      if entry in partner_hash[val]]
            next_iteration.extend([subset[:] + [candidate]
                                   for candidate in possible_additions])
        result = next_iteration
    return result


def main(verbose=False):
    MAX_n = 10**4
    PRIMES = sieve(MAX_n)
    partner_hash = prime_concat_partners(PRIMES, PRIMES, MAX_n**2)
    valid = possible_pairings(partner_hash, 5)

    min_sum = 10**10
    min_set = None
    for subset in valid:
        if sum(subset) < min_sum:
            min_sum = sum(subset)
            min_set = subset

    min_set = [str(prime) for prime in sorted(min_set)]
    if verbose:
        return '%s.\nThis is obtained with the primes %s.' % (
            min_sum, ', '.join(min_set))
    else:
        return min_sum

if __name__ == '__main__':
    print euler_timer(60)(main)(verbose=True)

    return [x ** 3 for x in range(m, M + 1)]


def has_k_perms(digits, k, cubes):
    sorted_cubes = {}
    for cube in cubes:
        sorted_digs = ''.join(sorted(str(cube)))
        # sets value to [] if not set, returns value at key
        sorted_cubes.setdefault(sorted_digs, []).append(cube)

    possible_matches = [value for value in sorted_cubes.values()
                        if len(value) == 5]

    possible_matches.sort(key=lambda list_: min(list_))
    if possible_matches:
        return min(possible_matches[0])
    else:
        return -1


def main(verbose=False):
    digits = len(str(41063625))
    cubes = all_cubes(digits)
    while has_k_perms(digits, 5, cubes) == -1:
        digits += 1
        cubes = all_cubes(digits)
    return has_k_perms(digits, 5, cubes)

if __name__ == '__main__':
    print euler_timer(62)(main)(verbose=True)