Код на пятиугольных числах выполняется слишком долго

Question

Я пытаюсь решить задачу 44 из Project Euler (https://projecteuler.net/problem=44), которая гласит

Пентагональные числа генерируются по формуле Pn = n (3n − 1) / 2Первые десять пятиугольных чисел:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

Видно, что P4 +P7 = 22 + 70 = 92 = P8. Однако их разность, 70 - 22 = 48, не является пятиугольной.

Найдите пару пятиугольных чисел Pj и Pk, для которых их сумма и разность являются пятиугольными.и D = | Pk - Pj | сводится к минимуму; каково значение D?

Это мой подход, но он занимает слишком много времени. Выполнение заняло более 15 минут, прежде чем я его убил.Я не знаю ответа, это метод «попробуйте», где я проверяю каждое число ниже 10000.

pentagonal = []
for i in range (1,10001):
    x = (i*(3*i - 1))/2
    pentagonal.append(x)

for i in pentagonal:
    for j in pentagonal:
        x = i - j
        y = i + j
        if x in pentagonal and y in pentagonal:
            print("(",i,":",j,")")

Answer 1

Поиск больших списков не эффективен с помощью команды в . Лучше всего использовать модуль bisect .

from bisect import bisect_left

pentagonal = []
for n in range(1, 10000):
    p = int((n*(3*n - 1))/2)
    pentagonal.append(p)


def bisect_search(lst, item):
    ''' it is used for sorted lists'''
    return (item <= lst[-1]) and (lst[bisect_left(lst, item)] == item)


for i in pentagonal:
    for j in pentagonal:
        diff = abs(i - j)
        sam = i + j
        if bisect_search(pentagonal, sam) and bisect_search(pentagonal, diff):
            print("(", i, ":", j, ")")

Наименьшая разница происходит от Pk = 7042750 и Pj = 1560090, и это D = 5482600