project euler 454 diophantine recipricols

Question

The question is: In the following equation x, y, and n are positive integers.

1/x + 1/y = 1/n

For a limit L we define F(L) as the number of solutions which satisfy x < y ≤ L.

We can verify that F(15) = 4 and F(1000) = 1069. Find F(1012).

I decided to test if I could find 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)

But nothing is stored in the list.

Answer 1

You are modifying x inside the y loop. The x += 1 belongs before the y loop. You could eliminate the increment altogether by using range() effectively. range(1,limit+1) will start at 1.

You are also not comparing y and limit correctly. y <= limit.

A slightly modified version of your program:

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

Even trying to calculate this at 10^5, you'll have one hell of a time with a brute force approach. I've been trying to figure this one out too.

Here's what I know:

1/x + 1/y = 1/n can be rewritten as

1/(n+a) + 1/(n+b) = 1/n This can be reduced to ab = n^2

(which is the method I used to solve for problems 108 and 110) By getting all of the divisors of n^2 you can solve for 'a' and 'b', but that only really helps if n is a fixed integer.

I have not figured out how this will help me with 454 yet.