Generating Seeds
Public  07/16/17  8xp  Math  100.0% 
Let $D$ be a positive integer.
Suppose that we would like to find all nonnegative integer solutions $(x, y, z)$ of $$ x^2 + D = y \cdot z. $$
Let's assume that $(x, y, z)$ is a solution of the above equation. Then, it can be verified that $(x+y, y, 2x + y + z)$ and $(x + z, 2x + y + z, z)$ are also solutions of the equation. Let's define this generating process as the evolution of $(x, y, z)$.
Surprisingly, we can find all solutions uniquely by choosing some seeds $S_D = \{ (x_1, y_1, z_1), \ldots, (x_k, y_k, z_k)\}$ and evolving them repeatedly. [a seed is a solution of the equation.]
For example, when $D = 2$, we can choose $S_2$ as $S_2 = \{(0, 1, 2), (0, 2, 1)\}$.
Let $C(D)$ be the minimum number of seeds needed to enumerate all nonnegative integer solutions of the equation.
It can be verified that $C(2) = 2$, $C(3) = 3$ and $C(100) = 18$.
Let $S(n) := \sum_{D=1}^{n} C(D)$. You are given $S(10) = 40$ and $S(100) = 1714$.
Find $S(3 \cdot 10^7)$.
[My Timing: 14.8 seconds (PyPy)]
New Members
 choiyd 4d:12h
 phacks 5d:7h
 MemorySlices 5d:12h
 n3chto 1w
 2997ms 1w:1d
Fresh Problems

Special Squares 4d:19h
solved by 8 
Sum of phi 1w:1d
solved by 4 
Decomposable Triangles 1w:4d
solved by 6 
A cubic form 1w:6d
solved by 4 
Automatic typewriter 2w:1d
solved by 5