pythondiophantine

project euler 454 diophantine recipricols


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.


Solution

  • 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)