pe-0659

根据最大质数p整除相邻两项,有一个模意义的式子.

$$\begin{cases}\begin{aligned} n^2+k^2\equiv &0\mod p\\ (n+1)^2+k^2\equiv &0\mod p \end{aligned}\end{cases}$$

联立一下得到

$$4k^2+1\equiv 0\mod p$$

所以就是对4kk+1取最大质因子就可以了.

# sage
n=10**7
res=0
for i in range(1,n+1):
	# tmp=factor(i).support()
	tmp = [p for p, e in factor(4*i*i+1)]  # 取出所有质因数
	res+=max(tmp)
	# tmp=list(tmp)
	# print(tmp)
	if i%100000==0:
		print(i)
print(res)

查wp发现有一个神秘筛法,不会.