Problem 507

Shortest Lattice Vector

Let $t_{n}$ be the tribonacci numbers defined as:
$t_{0} = t_{1} = 0$ ;
$t_{2} = 1$ ;
$t_{n} = t_{n - 1} + t_{n - 2} + t_{n - 3}$ for $n \geq 3$
and let $r_{n} = t_{n} mod 10^{7}$ .

For each pair of Vectors $V_{n} = (v_{1}, v_{2}, v_{3})$ and $W_{n} = (w_{1}, w_{2}, w_{3})$ with
$v_{1} = r_{12 n - 11} - r_{12 n - 10}, v_{2} = r_{12 n - 9} + r_{12 n - 8}, v_{3} = r_{12 n - 7} \cdot r_{12 n - 6}$ and
$w_{1} = r_{12 n - 5} - r_{12 n - 4}, w_{2} = r_{12 n - 3} + r_{12 n - 2}, w_{3} = r_{12 n - 1} \cdot r_{12 n}$
we define $S (n)$ as the minimal value of the manhattan length of the vector $D = k \cdot V_{n} + l \cdot W_{n}$ measured as
$| k \cdot v_{1} + l \cdot w_{1} | + | k \cdot v_{2} + l \cdot w_{2} | + | k \cdot v_{3} + l \cdot w_{3} |$
for any integers $k$ and $l$ with $(k, l) \neq (0, 0)$ .

The first vector pair is (-1, 3, 28), (-11, 125, 40826).
You are given that $S (1) = 32$ and $Σ_{n = 1}^{10} S (n) = 130762273722$ .

Find $Σ_{n = 1}^{20000000} S (n)$ .

最短向量

记如下数列 $t_{n}$ 为三阶斐波那契数列：
$t_{0} = t_{1} = 0$ ；
$t_{2} = 1$ ；
$t_{n} = t_{n - 1} + t_{n - 2} + t_{n - 3}$ for $n \geq 3$
并记 $r_{n} = t_{n} mod 10^{7}$ 。

向量 $V_{n} = (v_{1}, v_{2}, v_{3})$ 和 $W_{n} = (w_{1}, w_{2}, w_{3})$ 分别满足
$v_{1} = r_{12 n - 11} - r_{12 n - 10}, v_{2} = r_{12 n - 9} + r_{12 n - 8}, v_{3} = r_{12 n - 7} \cdot r_{12 n - 6}$ 和
$w_{1} = r_{12 n - 5} - r_{12 n - 4}, w_{2} = r_{12 n - 3} + r_{12 n - 2}, w_{3} = r_{12 n - 1} \cdot r_{12 n}$ 。
向量 $D = k \cdot V_{n} + l \cdot W_{n}$ 的曼哈顿长度的计算方式为
$| k \cdot v_{1} + l \cdot w_{1} | + | k \cdot v_{2} + l \cdot w_{2} | + | k \cdot v_{3} + l \cdot w_{3} |$ 。
对于所有的整数 $k$ 和 $l$ 且 $(k, l) \neq (0, 0)$ ，我们记 $S (n)$ 为向量 $D$ 的最小曼哈顿长度。

第一对向量 $V_{1}$ 和 $W_{1}$ 分别是(-1, 3, 28)和(-11, 125, 40826)。
已知 $S (1) = 32$ ，以及 $Σ_{n = 1}^{10} S (n) = 130762273722$ 。

求 $Σ_{n = 1}^{20000000} S (n)$ 。