Diophantine reciprocals II
Problem 110
In the following equation x, y, and n are positive integers.
| 1 x | + | 1 y | = | 1 n |
It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred.
What is the least value of n for which the number of distinct solutions exceeds four million?
NOTE: This problem is a much more difficult version of Problem 108 and as it is well beyond the limitations of a brute force approach it requires a clever implementation.
from tools import primes_to
def next(count, max_count):
i = 0
while i < len(count) and count[i] == max_count:
i += 1
if i < len(count):
n = count[i]
while i >= 0:
count[i] = n + 1
i -= 1
else:
return None
return count
def getn(primes, count):
num = 1
for i in range(len(count)):
num *= pow(primes[i], count[i])
return num
def ways(count_factors):
i = 1
for c in count_factors:
i *= 2 * c + 1
return (i + 1) / 2
def run(limit=4000000):
cmax = 3
primes = primes_to(40)
count = [0] * len(primes)
min_num = float('inf')
while count:
num = getn(primes, count)
if num < min_num:
w = ways(count)
if w > limit:
min_num = num
count = next(count, cmax)
return min_num