生成种子

令 $D$ 为正整数。

假设我们想要找到 $(x,y,z)$ 的所有非负整数解 $$x^2+D=y\cdot z.$$

我们假设 $(x,y,z)$ 是上式的解。那么可以验证$(x+y,y,2x+y+z)$和$(x+z,2x+y+z,z)$也是方程的解。我们将这个生成过程定义为 进化论 $(x,y,z)$ 的。

令人惊讶的是，我们可以通过选择一些唯一地找到所有解决方案 种子 $S_D=\{(x_1,y_1,z_1),\dots ,(x_k,y_k,z_k)\}$ 和 不断发展的 他们反复。 [一个 种子 是方程的解。]

例如，当$D=2$时，我们可以选择$S_2$作为$S_2=\{(0,1,2),(0,2,1)\}$。

令 $C(D)$ 为枚举方程的所有非负整数解所需的最小种子数。

可以验证的是$C(2)=2$、$C(3)=3$和$C(100)=18$。

让$S(n):=\sum _{D=1}^{n}C(D)$。您获得了 $S(10)=40$ 和 $S(100)=1714$。

找到$S(3\cdot {10}^7)$。

[我的计时：14.8秒（PyPy）]