0141 累进平方数
* * * *
拉格朗日计划
* * * *
累进平方数

设n模d得商q和余数r,n、d、q、r均为自然数。

若d、q、r按一定顺序排列后能构成等比数列,则称n为累进数。例如$58=6\times 9+4$,而4、6、9可以构成公比为$3/2$的等比数列,因此58是累进数。

有些累进数,例如9或$10404=102^2$,恰好也是完全平方数。所有小于十万的累进平方数之和是124657。

求所有小于一万亿($10^{12}$)的累进平方数之和。

本题难度:



解答

按题意$n=dq+r$,且r小于d,因此若三者构成等比数列,则有$d^2=qr$或$q^2=dr$,显然两者只是记号上的差异,因此不妨设d小于q。

不妨再设公比大于1(否则将数列反转即可),并将其记作$a/b$,且$\gcd(a,b)=1$,如此则有 $$d=\frac{a}{b}\cdot r, \quad q=\frac{a^2}{b^2}\cdot r, $$ 因此$b^2$能整除r。令$r=b^2c$,则有$n=a^3bc^2+b^2c$,枚举$a,b,c$可得结果$878454337159$。

import math
r=set([])
for a in range(2,10000):
    b=1
    while b < a and a*a*a*b+b*b < 1000000000000:
        if math.gcd(a,b)==1:
            c=1
            n=a*a*a*b*c*c+b*b*c
            while n < 1000000000000:
                if math.sqrt(n).is_integer():
                    r.add(n)
                c+=1
                n=a*a*a*b*c*c+b*b*c
        b+=1
print(sum(r))