寻找具有某种属性的整数 - 项目欧拉问题221

我最近对Project Euler非常沉迷,我正在努力做到这一点!我已经开始对它进行一些分析,并且已经大大减少了问题.这是我的工作:

A = pqr和

1/A = 1/p + 1/q + 1/r所以pqr/A = pq + pr + qr

由于第一个等式:

pq + pr + qr = 1

由于p,q和r中只有两个必须是负数,我们可以将方程式简化为:

abc,其中ab = ac + bc + 1

解决问题我们得到:

ab-1 =(a + b)c

c =(ab-1)/(a + b)

---

这意味着我们需要找到a和b:

ab = 1(mod a + b)

那么a和b的A值是:

A = abc = ab(ab-1)/(a + b)

对不起,如果这是很多数学!但现在我们所要处理的只是一个条件和两个方程式.既然我需要找到写成ab(ab-1)/(a + b)且ab = 1(mod a + b)的第150,000个最小整数,理想情况下我想搜索(a,b)其中A是尽可能小.

为了方便起见,我假设

我的第一个实现是直接的,甚至可以足够快地找到150,000个解决方案.但是,找到150,000个最小的解决方案需要很长时间.无论如何,这是代码:

n = 150000
seen = set()

a = 3
while len(seen) < n:
    for b in range(2, a):
        if (a*b)%(a+b) != 1: continue

        seen.add(a*b*(a*b-1)//(a+b))
        print(len(seen), (a, b), a*b*(a*b-1)//(a+b))

    a += 1

我的下一个想法是使用Stern-Brocot树,但这太慢,无法找到解决方案.我的最终算法是使用中国余数定理来检查a + b的不同值是否产生解.该代码很复杂,虽然速度更快但速度不够快......

所以我完全没有想法!有人有任何想法吗？