0135 相同的差
* * * *
拉格朗日计划
* * * *
相同的差

已知正整数x、y、z构成等差数列。

能使方程$x^2−y^2−z^2=n$有两个解的最小正整数为$n=27$: $$34^2−27^2−20^2=12^2−9^2−6^2=27.$$ 使得方程有十个解的最小正整数为$n=1155$。

小于一百万的数中,有多少个n能使该方程恰有十个解?

本题难度:



解答

令$x$、$y$、$z$依次为$a-d$、$a$、$a+d$,则有 $$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a).$$ 因此可以先用筛法找出有10个以上约数的n,再对n的每个约数a检验$d=(n/a+a)/4$是否是小于$a$的整数,每对这样的a和d就可以生成一组解,找出恰能生成10组解的n即可。

结果是$4989$。

a=[set([]) for i in range(1000000)]
for i in range(1,1000):
    for j in range(i,1000000,i):
        a[j].add(i)
        a[j].add(j/i)

candidates=[[i,a[i]] for i in range(1000000) if len(a[i])>=10]

r=[n for n,divisors in candidates if sum(b%4==0 and b/4 < a for a in divisors for b in [n/a+a])==10]

print len(r)