Problem 507 「最短の格子ベクトル」

以下のように定義される トリボナッチ数t&sub{n}; としよう:

t&sub{0}; = t&sub{1}; = 0;
t&sub{2}; = 1;
t&sub{n}; = t&sub{n-1}; + t&sub{n-2}; + t&sub{n-3}; (n ≥ 3 のとき)
そして r&sub{n}; = t&sub{n}; mod 10&sup{7}; としよう.

一組のベクトル V&sub{n}; = (v&sub{1};,v&sub{2};,v&sub{3};) と W&sub{n}; = (w&sub{1};,w&sub{2};,w&sub{3};) それぞれに対し、

v&sub{1}; = r&sub{12n−11}; − r&sub{12n−10};, v&sub{2}; = r&sub{12n−9}; + r&sub{12n−8};, v&sub{3}; = r&sub{12n−7};⋅r&sub{12n−6};
w&sub{1}; = r&sub{12n−5}; − r&sub{12n−4};, w&sub{2}; = r&sub{12n−3}; + r&sub{12n−2};, w&sub{3}; = r&sub{12n−1};⋅r&sub{12n};

(k,l) ≠ (0,0) となるような任意の整数 kl に対し, |kv&sub{1}; + lw&sub{1};| + |kv&sub{2}; + lw&sub{2};| + |kv&sub{3}; + lw&sub{3};| で計算されるベクトル D = kV&sub{n}; + lW&sub{n}; のマンハッタン距離の最小値を S(n) としよう.
最初のベクトルの組は (-1, 3, 28), (-11, 125, 40826) になる.
S(1) = 32, そして &ref(): File not found: "p507_eq1.png" at page "Problem 507"; 130762273722 が与えられている.
&ref(): File not found: "p507_eq2.png" at page "Problem 507"; を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2015-03-16 (月) 00:57:51