题目141：考查渐进的完全平方数

欧拉计划

Investigating progressive numbers, n, which are also square

A positive integer, n, is divided by d and the quotient and remainder are q and r respectively. In addition d, q, and r are consecutive positive integer terms in a geometric sequence, but not necessarily in that order.

For example, 58 divided by 6 has quotient 9 and remainder 4. It can also be seen that 4, 6, 9 are consecutive terms in a geometric sequence (common ratio 3/2).
We will call such numbers, n, progressive.

Some progressive numbers, such as 9 and 10404 = 102², happen to also be perfect squares.
The sum of all progressive perfect squares below one hundred thousand is 124657.

Find the sum of all progressive perfect squares below one trillion (10¹²).

题目：

正整数 n 被 d 除所得的商和余数分别为 q 和 r。此外，d，q 和 r 是一个等比数列中的连续三项，但未必是有序的。

例如，58 除以 6，商为 9，余数为 4。可知 4，6，9 是公比为 3/2 的等比数列中的连续三项。

我们将这样的 n 成为渐近数。

有的渐近数同时也是完全平方数，比如 9 和 10404=102²。

100000 以下所有的完全平方渐近数之和是 124657。

求 10¹² 以下所有完全平方渐近数之和。

jerryxjr1220

由r, d, q是等比数列=>r, cr, c*c*r，由于c必须是有理数，所以令c=a/b，则=>r, a*r/b, a*a*r/b/b，由a和b互质，可以推出r必须要能整除b*b，所以可以写成r=k*b*b，最终得到n=dq+r=a*a*a*b*k*k+b*b*k。
由于n<10**12，可知 2<=a<10000, 1<=b<a，k>=1，a和b互质。

from math import gcd
from numba import jit
@jit
def solve():
        s = 0
        for a in range(2, 10000):
                for b in range(1, a):
                        if a * a * a * b * b + b * b > 10**12:
                                break
                        if gcd(a, b) > 1:
                                continue
                        for c in range(1, 10**9):
                                n = a*a*a*b*c*c+c*b*b
                                if n > 10**12:
                                        break
                                if int(n**0.5)**2 == n:
                                        s += n
        return s
print(solve())

878454337159
[Finished in 9.7s]