Diophantine reciprocals I
Problem 108
In the following equation x, y, and n are positive integers.
For n = 4 there are exactly three distinct solutions:
What is the least value of n for which the number of distinct solutions exceeds one-thousand?
NOTE: This problem is an easier version of Problem 110; it is strongly advised that you solve this one first.
def factor(n):
result = {}
while n % 2 == 0:
result[2] = result.get(2, 0) + 1
n = n / 2
i = 3
while i**2 <= n:
while n % i == 0:
result[i] = result.get(i, 0) + 1
n = n / i
i += 2
if n > 1:
result[n] = result.get(n, 0) + 1
return result
def solve(n):
s = 1
for i in factor(n).values():
s *= (2 * i + 1)
return (s / 2) + 1
def run(limit=1000):
n = 2
while solve(n) < limit:
n += 1
return n