ProjectEuler 507 Shortest Lattice Vect - 拼圖

507. Shortest Lattice Vector

https://projecteuler.net/problem=507

令t_n為三階費氏數列，定義如下：

t_0 = t_1 = 0
t_2 = 1
t_n = t_(n-1) + t_(n-2) + t_(n-3) 對所有n≧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_(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)

我們定義S(n)為向量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)。

第一對向量為(-1, 3, 28), (-11, 125, 40826)。

已知S(1) = 32以及Σ(n從1到10)S(n) = 130762273722。

請求出Σ(n從1到20000000)S(n)。

--