Problem #415

Generating Seeds
Public 4d:14h 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)]




You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]