0127 abc匹配
* * * *
拉格朗日计划
* * * *
abc匹配

自然数n的根基$\mathrm{rad}(n)$,即该数的所有质因数之积,如 $$\mathrm{rad}(504)=\mathrm{rad}(2^3\times 3^2\times 7)=2\times 3\times 7=42.$$ 规定$\mathrm{rad}(1)=1$。若三元自然数组$(a,b,c)$满足以下条件,就称其为abc匹配:

1. $\gcd(a,b)=\gcd(b,c)=\gcd(a,c)=1$。

2. $a < b$且$a+b=c$。

3. $\mathrm{rad}(abc) < c$。

例如,$(5,27,32)$是一个abc匹配,因为:

1. $\gcd(5,27)=\gcd(27,32)=\gcd(5,32)=1$。

2. $5 < 27$且$5+27=32$。

3. $\mathrm{rad}(5\times 27\times 32)=\mathrm{rad}(5\times 3^3\times 2^5)=30 < 32$。

事实上abc匹配颇为罕见,在c小于1000的所有三元数组中,只有31组abc匹配,这些匹配中的c之和为12523。

考虑c小于120000的所有abc匹配,求这些匹配中的c之和。

本题难度:



解答

根据OEIS A130510的数据(在整理在该文件中),共有456组满足条件的abc匹配,这些匹配中的c之和是$18407904$。

d=[]
with open("127_c.txt") as f:
    for line in f:
        d.append(int(line.split()[1]))
print sum(d[:456])