---

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≥3$
and let $r_n=t_n \text{ 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_{12n-11}-r_{12n-10},v_2=r_{12n-9}+r_{12n-8},v_3=r_{12n-7}·r_{12n-6}$ and
$w_1=r_{12n-5}-r_{12n-4},w_2=r_{12n-3}+r_{12n-2},w_3=r_{12n-1}·r_{12n}$
we define $S(n)$ as the minimal value of the manhattan length of the vector $D=k·V_n+l·W_n$ measured as
$|k·v_1+l·w_1|+|k·v_2+l·w_2|+|k·v_3+l·w_3|$
for any integers $k$ and $l$ with $(k,l)≠(0,0)$.

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

Find $\Sigma^{20000000}_{n=1}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≥3$
并记$r_n=t_n \text{ mod } 10^7$。

向量$V_n=(v_1,v_2,v_3)$和$W_n=(w_1,w_2,w_3)$分别满足
$v_1=r_{12n-11}-r_{12n-10},v_2=r_{12n-9}+r_{12n-8},v_3=r_{12n-7}·r_{12n-6}$和
$w_1=r_{12n-5}-r_{12n-4},w_2=r_{12n-3}+r_{12n-2},w_3=r_{12n-1}·r_{12n}$。
向量$D=k·V_n+l·W_n$的曼哈顿长度的计算方式为
$|k·v_1+l·w_1|+|k·v_2+l·w_2|+|k·v_3+l·w_3|$。
对于所有的整数$k$和$l$且$(k,l)≠(0,0)$，我们记$S(n)$为向量$D$的最小曼哈顿长度。

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

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

---