111 lines
3.2 KiB
Python
111 lines
3.2 KiB
Python
"""
|
||
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9
|
||
in some order, but it also has a rather interesting sub-string divisibility property.
|
||
|
||
Let d_1 be the 1st digit, d_2 be the 2nd digit, and so on. In this way, we note the following:
|
||
|
||
d_2d_3d_4 is divisible by 2
|
||
d_3d_4d_5 is divisible by 3
|
||
d_4d_5d_6 is divisible by 5
|
||
d_5d_6d_7 is divisible by 7
|
||
d_6d_7d_8 is divisible by 11
|
||
d_7d_8d_9 is divisible by 13
|
||
d_8d_9d_10 is divisible by 17
|
||
|
||
Find the sum of all 0 to 9 pandigital numbers with this property.
|
||
"""
|
||
|
||
import time
|
||
from itertools import permutations
|
||
from tkinter.constants import TOP
|
||
|
||
|
||
def timer(func):
|
||
def wrapper(*args, **kwargs):
|
||
start_time = time.perf_counter()
|
||
result = func(*args, **kwargs)
|
||
end_time = time.perf_counter()
|
||
print(f"Execution time: {end_time - start_time} seconds")
|
||
return result
|
||
|
||
return wrapper
|
||
|
||
|
||
def get_all_numbers() -> list[int]:
|
||
ori = list(permutations(list(range(10))))
|
||
res = []
|
||
for x in ori:
|
||
if x[3] % 2 != 0:
|
||
continue
|
||
if x[5] not in [0, 5]:
|
||
continue
|
||
for i, d in enumerate([2, 3, 5, 7, 11, 13, 17]):
|
||
if int("".join(map(str, x[i + 1 : i + 4]))) % d != 0:
|
||
break
|
||
else:
|
||
res.append(int("".join(map(str, x))))
|
||
return res
|
||
|
||
|
||
def optimized_solve() -> tuple[int, list[int]]:
|
||
total = 0
|
||
|
||
# 从最后三位开始，这些必须能被17整除
|
||
candidates = []
|
||
for n in range(102, 1000, 17):
|
||
s = str(n).zfill(3)
|
||
if len(set(s)) == 3: # 三位数字必须不同
|
||
candidates.append(s)
|
||
|
||
# 逐步向前添加数字，检查约束
|
||
for i, prime in enumerate([13, 11, 7, 5, 3, 2]):
|
||
new_candidates = []
|
||
for cand in candidates:
|
||
# 获取当前已使用的数字
|
||
used_digits = set(cand)
|
||
|
||
# 尝试添加一个新数字在最前面
|
||
for d in "0123456789":
|
||
if d not in used_digits:
|
||
# 新形成的三位数
|
||
new_triplet = d + cand[:2]
|
||
# 检查是否能被对应的质数整除
|
||
if int(new_triplet) % prime == 0:
|
||
new_candidates.append(d + cand)
|
||
|
||
candidates = new_candidates
|
||
|
||
# 现在candidates中包含的是d_2到d_10（9位数字）
|
||
# 我们需要添加第一个数字d_1
|
||
final_numbers = []
|
||
for cand in candidates:
|
||
used_digits = set(cand)
|
||
# 找出缺失的那个数字
|
||
for d in "0123456789":
|
||
if d not in used_digits and d != "0": # d_1不能为0
|
||
num = d + cand
|
||
# 验证这是一个0-9的pandigital数
|
||
if len(set(num)) == 10:
|
||
final_numbers.append(num)
|
||
|
||
# 计算总和
|
||
total = sum(int(num) for num in final_numbers)
|
||
return total, [int(num) for num in final_numbers]
|
||
|
||
|
||
@timer
|
||
def main():
|
||
numbers = get_all_numbers()
|
||
print(sum(numbers))
|
||
|
||
|
||
@timer
|
||
def main_op():
|
||
total, _ = optimized_solve()
|
||
print(total)
|
||
|
||
|
||
if __name__ == "__main__":
|
||
main()
|
||
main_op()
|