Project Euler 454 диофантовых рециприолов

Question

Вопрос заключается в следующем: в следующем уравнении x, y и n являются натуральными числами.

1 / х + 1/ у = 1/ н

Для предела L определим F(L) как число решений, удовлетворяющих x

Мы можем проверить, что F(15) = 4 и F(1000) = 1069. Найти F(1012).

Я решил проверить, смогу ли я найти F (15)

count = 0
limit = 15
storage = []
x = 1
y = 1

for x in range(limit + 1):
    for y in range(limit + 1):
        x += 1
        y += 1
        n = x*y/(x+y)
        condition = x*y%(x+y)

        if (condition == 0 and x<y and y<limit):
            count += 1
            storage.append(x)
            storage.append(y)
            storage.append(n)

print (storage)
print (count)

Но ничего не хранится в списке.

Answer 1

Вы модифицируете x внутри y петля. x += 1 принадлежит до y петля. Вы можете полностью исключить приращение, используя range() эффективно. range(1,limit+1) начнется с 1.

Вы тоже не сравниваете y а также limit правильно. y <= limit,

Немного модифицированная версия вашей программы:

count = 0
limit = 15
storage = []
x = 1
y = 1

for x in range(1,limit + 1):
    for y in range(1,limit + 1):
        n = x*y/(x+y)
        condition = x*y%(x+y)

        if (condition == 0 and x<y and y<=limit):
            count += 1
            storage.append(x)
            storage.append(y)
            storage.append(n)

print (storage)
print (count)

Answer 2

Даже пытаясь вычислить это в 10^5, у вас будет один ад с подходом грубой силы. Я тоже пытался понять это.

Вот что я знаю:

1 / x + 1 / y = 1 / n можно переписать как

1/(n+a) + 1/(n+b) = 1/n Это можно уменьшить до ab = n^2

(это метод, который я использовал для решения задач 108 и 110) Получив все делители n^2, вы можете решить для "a" и "b", но это действительно помогает, только если n является фиксированным целым числом.

Я еще не понял, как это поможет мне с 454.