47 lines
1.5 KiB
Python
47 lines
1.5 KiB
Python
from lib_prime import is_prime_rabin_miller as is_prime
|
|
|
|
|
|
def get_permutations(number: str, number_permutations: int, start_index = 0):
|
|
""" Returns number permutated at number_permutations locations. """
|
|
if number_permutations == 0:
|
|
yield int(number)
|
|
else:
|
|
numbers = list("0123456789")
|
|
base = list(str(number))
|
|
for i in range(start_index, len(base)):
|
|
digit_stored = base[i]
|
|
for n in numbers:
|
|
if n == digit_stored:
|
|
continue
|
|
base[i] = n
|
|
if base[0] == "0":
|
|
continue
|
|
for p in get_permutations("".join(base), number_permutations - 1, i):
|
|
yield p
|
|
base[i] = digit_stored
|
|
|
|
|
|
def euler_111():
|
|
result = 0
|
|
n = 10
|
|
for d in range(10):
|
|
subresult = 0
|
|
base = "".join([str(d) for _ in range(n)])
|
|
for p in get_permutations(base, 1):
|
|
if is_prime(p):
|
|
subresult += p
|
|
if subresult == 0:
|
|
# d in [0, 2, 8] requires two permutations to yield at least one prime
|
|
for p in get_permutations(base, 2):
|
|
if is_prime(p):
|
|
subresult += p
|
|
assert subresult > 0, "More than two permutations required to yield prime"
|
|
result += subresult
|
|
return result
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_111()
|
|
print("e111.py: " + str(solution))
|
|
assert(solution == 612407567715)
|