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

Question

我最近对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是尽可能小.

为了方便起见,我假设<b,我也注意到gcd(a,b)= 1.

我的第一个实现是直接的,甚至可以足够快地找到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的不同值是否产生解.该代码很复杂,虽然速度更快但速度不够快......

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

Answer 1

与许多欧拉计划问题一样，诀窍是找到一种技术，将蛮力解决方案简化为更直接的解决方案：

\n\n

A = pqr and \n1/A = 1/p + 1/q + 1/r\n

\n\n

所以，

\n\n

pq + qr + rp = 1  or  -r = (pq - 1)/(p + q)\n

\n\n

不失一般性，0 < p < -q < -r

\n\n

存在 k , 1 <= k <= p

\n\n

-q = p + k\n-r = (-p(p + k) \xe2\x80\x93 1) / (p + -p \xe2\x80\x93 k)  = (p^2 + 1)/k + p\n

\n\n

但 r 是整数，所以 k 整除 p^2 + 1

\n\n

pqr = p(p + q)((p^2 + 1)/k + p)\n

\n\n

因此，为了计算 A，我们需要迭代 p，其中 k 只能取 p 平方加 1 的约数。

\n\n

将每个解添加到一个集合中，当我们找到所需的第 150000 个亚历山大整数时，我们就可以停止。

\n