Let the Tribonacci sequence be defined by
$$t_1=0,\qquad t_2=t_3=1,\qquad t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
For each \(n\ge 1\), take the 12 consecutive values
$$r_k=t_{12n-12+k}\qquad (1\le k\le 12),$$
and form two vectors in \(\mathbb{Z}^3\):
$$v_n=(r_1-r_2,\ r_3+r_4,\ r_5r_6),\qquad w_n=(r_7-r_8,\ r_9+r_{10},\ r_{11}r_{12}).$$
We must compute
$$s(n)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|a v_n+b w_n\right\|_1,$$
where
$$\left\|(x,y,z)\right\|_1=|x|+|y|+|z|,$$
and then sum these values:
$$S(N)=\sum_{n=1}^{N} s(n).$$
The target computation uses \(N=20{,}000{,}000\), so the solution has to generate the sequence and solve each rank-2 lattice problem without storing huge tables.
The lattice generated by \(v_n\) and \(w_n\) is
$$L_n=\{a v_n+b w_n:\ a,b\in\mathbb{Z}\}.$$
Because the lattice has rank 2, the implementations use an \(L_1\)-analogue of two-vector reduction: repeatedly shorten the longer generator by subtracting an integer multiple of the shorter one. The critical point is that the best multiple can be found by checking only a handful of integer candidates.
Each lattice instance uses exactly 12 consecutive Tribonacci values. There is no need to materialize the whole sequence up to index \(12N\); we only need a rolling state for three consecutive terms.
Once the current state \((t_k,t_{k+1},t_{k+2})\) is known, the next term is
$$t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
After every 12 streamed values, we obtain one pair \((v_n,w_n)\). This turns the outer problem into a sequence of independent shortest-vector queries in lattices of the form \(\mathbb{Z}v+\mathbb{Z}w\subseteq \mathbb{Z}^3\).
For fixed vectors \(v,w\), we want
$$m(v,w)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|av+bw\right\|_1.$$
If we replace \(w\) by
$$w'=w-tv\qquad (t\in\mathbb{Z}),$$
then the lattice does not change, because
$$\mathbb{Z}v+\mathbb{Z}w=\mathbb{Z}v+\mathbb{Z}(w-tv).$$
This is the same unimodular basis change used in Gauss reduction. Therefore we are free to shear one generator by an integer multiple of the other whenever that makes the basis shorter in the \(L_1\) norm.
Suppose \(v\) is the shorter current vector and we want the best replacement for \(w\). Define
$$f(t)=\left\|w-tv\right\|_1=\sum_{i=1}^{3}\left|w_i-t v_i\right|,\qquad t\in\mathbb{Z}.$$
Each summand \(\left|w_i-t v_i\right|\) is a convex piecewise-linear function of \(t\). Its slope changes only when \(t=w_i/v_i\) for a coordinate with \(v_i\ne 0\). Therefore \(f(t)\) is also convex and piecewise linear, with all breakpoints coming from those coordinate ratios.
Over the integers, a minimizer of a convex piecewise-linear function must occur at an integer adjacent to one of the breakpoints, so it is enough to test
$$\left\lfloor\frac{w_i}{v_i}\right\rfloor,\qquad \left\lfloor\frac{w_i}{v_i}\right\rfloor+1$$
for every coordinate with \(v_i\ne 0\), together with \(t=0\). In three dimensions this gives at most seven candidates.
That is why the implementations can find the best integer shear in constant time per reduction step instead of searching over all integers.
The reduction loop always keeps the shorter vector first. It computes the best integer \(t\), forms \(w-tv\), and accepts the change only if the \(L_1\) norm strictly decreases:
$$\left\|w-tv\right\|_1<\left\|w\right\|_1.$$
Every accepted step preserves the lattice and strictly lowers the norm of one basis vector, so the process must terminate. When no tested integer multiple makes the longer vector shorter, the pair is locally reduced for this \(L_1\) shear operation.
The implementations then return the shorter nonzero vector of the reduced pair. For the rank-2 lattices arising here, this is the quantity used throughout the computation of \(s(n)\).
The C++ and Java implementations do not restart the Tribonacci sequence from the beginning whenever they need a later index. Instead they use the companion matrix
$$A=\begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}.$$
This matrix advances the state vector by one step:
$$A\begin{pmatrix}t_{k+2}\\ t_{k+1}\\ t_k\end{pmatrix}=\begin{pmatrix}t_{k+3}\\ t_{k+2}\\ t_{k+1}\end{pmatrix}.$$
So exponentiation by squaring gives any required starting state in \(O(\log k)\) time. After that jump, the next terms are streamed linearly.
The first 12 Tribonacci values are
$$0,1,1,2,4,7,13,24,44,81,149,274.$$
Hence
$$v=(-1,3,28),\qquad w=(-11,125,40826).$$
The initial norms are
$$\|v\|_1=|-1|+|3|+|28|=32,$$
$$\|w\|_1=|-11|+|125|+|40826|=40962.$$
To reduce \(w\), examine the coordinate ratios
$$\frac{-11}{-1}=11,\qquad \frac{125}{3}\approx 41.67,\qquad \frac{40826}{28}\approx 1458.07.$$
The best tested integer is \(t=1458\), giving
$$w-1458v=(1447,-4249,2),$$
with
$$\|w-1458v\|_1=1447+4249+2=5698.$$
This is a major improvement over \(40962\), but it is still larger than \(\|v\|_1=32\). No further integer shear shortens the second vector, so the shortest nonzero lattice vector has \(L_1\) length
$$s(1)=32.$$
This matches the first checkpoint used by the implementation. A second checkpoint verifies
$$S(10)=130762273722.$$
The C++ and Java implementations share the same numerical method. They compute the Tribonacci values on the fly, buffer 12 consecutive terms, build the two 3-dimensional generators, run the reduction loop described above, and add the resulting shortest \(L_1\) length to a running total.
Because the third coordinate is a product of two Tribonacci values, intermediate vector norms can become large. The C++ implementation therefore uses 128-bit integer arithmetic for norm calculations and final accumulation, while the Java implementation uses arbitrary-precision integers for the same reason.
The C++ implementation also splits the range \(1\le n\le N\) into contiguous chunks when multiple hardware threads are available. Each chunk computes its own starting Tribonacci state via matrix exponentiation, then streams its local terms independently and returns a partial sum. Those partial sums are added at the end.
The Python implementation is intentionally thin: it ensures that the C++ solver is available, runs that compiled program, and returns the printed decimal answer. In other words, the mathematical work is the same, while Python serves as a bridge layer.
Before the full target run, the implementation checks the first generated vector pair, confirms \(s(1)=32\), and confirms \(S(10)=130762273722\). Those checkpoints protect against indexing mistakes in the sequence stream and against incorrect reduction behavior.
Generating the 12 Tribonacci values for one lattice instance costs \(O(1)\) time and \(O(1)\) memory. Each reduction iteration evaluates at most seven candidate integers, so one iteration is also \(O(1)\). In practice the number of accepted reductions is small for these 3-dimensional rank-2 bases, which makes the average cost per \(n\) effectively constant.
As a result, the total sequential running time is linear in the number of instances:
$$O(N).$$
If the work is split across \(P\) independent chunks, each chunk pays an additional \(O(\log N)\) initialization cost for the matrix jump, so the total work stays linear and the wall-clock time is close to
$$O\!\left(\frac{N}{P}+\log N\right)$$
per chunk, with \(O(1)\) memory per chunk.
Die Tribonacci-Folge sei definiert durch
$$t_1=0,\qquad t_2=t_3=1,\qquad t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
Für jedes \(n\ge 1\) werden die 12 aufeinanderfolgenden Werte
$$r_k=t_{12n-12+k}\qquad (1\le k\le 12)$$
verwendet, um zwei Vektoren in \(\mathbb{Z}^3\) zu bilden:
$$v_n=(r_1-r_2,\ r_3+r_4,\ r_5r_6),\qquad w_n=(r_7-r_8,\ r_9+r_{10},\ r_{11}r_{12}).$$
Gesucht ist
$$s(n)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|a v_n+b w_n\right\|_1,$$
wobei
$$\left\|(x,y,z)\right\|_1=|x|+|y|+|z|$$
gilt, und schließlich
$$S(N)=\sum_{n=1}^{N} s(n).$$
Für den eigentlichen Lauf ist \(N=20{,}000{,}000\). Man braucht also eine Methode, die sowohl die Folge als auch jedes Gitterproblem ohne teure Vollsuche verarbeitet.
Das von \(v_n\) und \(w_n\) erzeugte Gitter ist
$$L_n=\{a v_n+b w_n:\ a,b\in\mathbb{Z}\}.$$
Da dieses Gitter Rang 2 hat, verwenden die Implementierungen eine \(L_1\)-Variante der Zwei-Vektor-Reduktion: Der längere Generator wird wiederholt durch Subtraktion eines ganzzahligen Vielfachen des kürzeren verkürzt. Entscheidend ist, dass man das beste Vielfache mit nur wenigen Kandidaten findet.
Jeder Gitterfall benötigt genau 12 aufeinanderfolgende Tribonacci-Werte. Die gesamte Folge bis Index \(12N\) muss nicht gespeichert werden; ein rollender Zustand aus drei aufeinanderfolgenden Werten genügt.
Ist \((t_k,t_{k+1},t_{k+2})\) bekannt, so gilt
$$t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
Nach jeweils 12 gestreamten Werten erhält man genau ein Paar \((v_n,w_n)\). Das Gesamtproblem zerfällt damit in viele unabhängige Kürzestvektor-Anfragen in Gittern der Form \(\mathbb{Z}v+\mathbb{Z}w\subseteq\mathbb{Z}^3\).
Für feste Vektoren \(v,w\) suchen wir
$$m(v,w)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|av+bw\right\|_1.$$
Ersetzt man \(w\) durch
$$w'=w-tv\qquad (t\in\mathbb{Z}),$$
dann bleibt das Gitter unverändert, denn
$$\mathbb{Z}v+\mathbb{Z}w=\mathbb{Z}v+\mathbb{Z}(w-tv).$$
Das ist dieselbe unimodulare Basisänderung wie bei der Gauß-Reduktion. Daher darf man einen Generator um ein ganzzahliges Vielfaches des anderen scheren, solange dadurch die \(L_1\)-Länge kleiner wird.
Sei \(v\) der aktuell kürzere Vektor. Dann definieren wir
$$f(t)=\left\|w-tv\right\|_1=\sum_{i=1}^{3}\left|w_i-t v_i\right|,\qquad t\in\mathbb{Z}.$$
Jeder Summand \(\left|w_i-t v_i\right|\) ist als Funktion von \(t\) konvex und stückweise linear. Die Steigung ändert sich nur an der Stelle \(t=w_i/v_i\), sofern \(v_i\ne 0\) ist. Also ist auch \(f(t)\) konvex und stückweise linear, mit Knickstellen genau bei diesen Koordinatenverhältnissen.
Für ganzzahlige \(t\) muss ein Minimum daher an einer Ganzzahl direkt neben einer solchen Knickstelle liegen. Es genügt also, für jede Koordinate mit \(v_i\ne 0\) die Werte
$$\left\lfloor\frac{w_i}{v_i}\right\rfloor,\qquad \left\lfloor\frac{w_i}{v_i}\right\rfloor+1$$
sowie zusätzlich \(t=0\) zu testen. In drei Dimensionen sind das höchstens sieben Kandidaten.
Die Reduktionsschleife hält stets den kürzeren Vektor an erster Stelle. Sie bestimmt das beste ganzzahlige \(t\), bildet \(w-tv\) und übernimmt diesen Ersatz nur dann, wenn die \(L_1\)-Norm strikt sinkt:
$$\left\|w-tv\right\|_1<\left\|w\right\|_1.$$
Jeder akzeptierte Schritt erhält das Gitter und verkleinert die Norm eines Basisvektors strikt, also muss der Prozess terminieren. Wenn kein getestetes ganzzahliges Vielfaches den längeren Vektor weiter verkürzt, ist das Paar für diese \(L_1\)-Scherung lokal reduziert.
Die Implementierungen geben dann den kürzeren nichtnulligen Vektor des reduzierten Paares zurück. Genau dieser Wert wird hier als \(s(n)\) verwendet.
Die C++- und Java-Implementierungen beginnen für späte Indizes nicht jedes Mal wieder bei \(t_1\). Stattdessen benutzen sie die Begleitmatrix
$$A=\begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}.$$
Sie verschiebt den Zustandsvektor um einen Schritt:
$$A\begin{pmatrix}t_{k+2}\\ t_{k+1}\\ t_k\end{pmatrix}=\begin{pmatrix}t_{k+3}\\ t_{k+2}\\ t_{k+1}\end{pmatrix}.$$
Mit binärer Exponentiation erhält man so jeden gewünschten Startzustand in \(O(\log k)\) Zeit und kann danach linear weiterstreamen.
Die ersten 12 Tribonacci-Werte lauten
$$0,1,1,2,4,7,13,24,44,81,149,274.$$
Daraus folgen
$$v=(-1,3,28),\qquad w=(-11,125,40826).$$
Die Anfangsnormen sind
$$\|v\|_1=|-1|+|3|+|28|=32,$$
$$\|w\|_1=|-11|+|125|+|40826|=40962.$$
Für die Reduktion von \(w\) betrachtet man die Verhältnisse
$$\frac{-11}{-1}=11,\qquad \frac{125}{3}\approx 41.67,\qquad \frac{40826}{28}\approx 1458.07.$$
Der beste getestete Wert ist \(t=1458\). Dann gilt
$$w-1458v=(1447,-4249,2),$$
und somit
$$\|w-1458v\|_1=1447+4249+2=5698.$$
Das ist viel kleiner als \(40962\), aber immer noch größer als \(\|v\|_1=32\). Weitere ganzzahlige Scherungen verkürzen den zweiten Vektor nicht mehr, also ist
$$s(1)=32.$$
Genau dieser Kontrollwert wird auch von der Implementierung geprüft. Ein zweiter Kontrollwert ist
$$S(10)=130762273722.$$
Die C++- und Java-Implementierungen benutzen denselben numerischen Kern. Sie erzeugen die Tribonacci-Werte fortlaufend, puffern jeweils 12 Werte, bauen daraus die beiden 3-dimensionalen Generatoren, führen die oben beschriebene Reduktionsschleife aus und addieren die resultierende kürzeste \(L_1\)-Länge zu einer laufenden Summe.
Da die dritte Koordinate ein Produkt zweier Tribonacci-Werte ist, können Zwischenwerte groß werden. Deshalb verwendet die C++-Implementierung 128-Bit-Ganzzahlen für Normen und Summen, während die Java-Implementierung dafür Ganzzahlen beliebiger Länge verwendet.
Die C++-Implementierung kann den Bereich \(1\le n\le N\) außerdem in zusammenhängende Teilintervalle aufteilen, wenn mehrere Hardware-Threads verfügbar sind. Jedes Teilintervall bestimmt seinen Anfangszustand per Matrixpotenz, verarbeitet seine lokalen Werte unabhängig und liefert eine Teilsumme zurück.
Die Python-Implementierung ist bewusst schlank: Sie stellt sicher, dass der C++-Solver verfügbar ist, führt das kompilierte Programm aus und gibt die gedruckte Dezimalzahl zurück. Die eigentliche Mathematik bleibt also dieselbe; Python fungiert hier nur als Brücke.
Vor dem vollständigen Ziellauf prüft die Implementierung das erste erzeugte Vektorpaar, bestätigt \(s(1)=32\) und bestätigt \(S(10)=130762273722\). Diese Kontrollpunkte fangen Indexierungsfehler in der Folge und Fehler in der Reduktion früh ab.
Die Erzeugung der 12 Tribonacci-Werte für einen Gitterfall kostet \(O(1)\) Zeit und \(O(1)\) Speicher. Jede Reduktionsiteration testet höchstens sieben ganzzahlige Kandidaten und ist daher ebenfalls \(O(1)\). In der Praxis ist die Anzahl akzeptierter Reduktionsschritte für diese 3-dimensionalen Rang-2-Basen klein, sodass die mittleren Kosten pro \(n\) effektiv konstant sind.
Damit ist die gesamte sequentielle Laufzeit linear in der Anzahl der Fälle:
$$O(N).$$
Wird die Arbeit auf \(P\) unabhängige Blöcke verteilt, so kommt pro Block eine Initialisierung von \(O(\log N)\) für den Matrixsprung hinzu. Die Gesamtarbeit bleibt linear, und die Wandzeit pro Block liegt nahe bei
$$O\!\left(\frac{N}{P}+\log N\right),$$
wobei jeder Block nur \(O(1)\) Speicher benötigt.
Tribonacci dizisi
$$t_1=0,\qquad t_2=t_3=1,\qquad t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}$$
şeklinde tanımlansın. Her \(n\ge 1\) için ardışık 12 değer
$$r_k=t_{12n-12+k}\qquad (1\le k\le 12)$$
alınır ve \(\mathbb{Z}^3\) içinde iki vektör oluşturulur:
$$v_n=(r_1-r_2,\ r_3+r_4,\ r_5r_6),\qquad w_n=(r_7-r_8,\ r_9+r_{10},\ r_{11}r_{12}).$$
Aranan değer
$$s(n)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|a v_n+b w_n\right\|_1,$$
burada
$$\left\|(x,y,z)\right\|_1=|x|+|y|+|z|$$
olur. Sonra
$$S(N)=\sum_{n=1}^{N} s(n)$$
hesaplanır. Hedef durumda \(N=20{,}000{,}000\) olduğundan, çözüm hem diziyi hem de her kafes problemini çok düşük maliyetle işlemelidir.
\(v_n\) ve \(w_n\) tarafından üretilen kafes
$$L_n=\{a v_n+b w_n:\ a,b\in\mathbb{Z}\}$$
şeklindedir. Kafesin rütbesi 2 olduğu için uygulamalar, iki vektörlü \(L_1\) indirgemesinin bir çeşidini kullanır: daha uzun üreteç, daha kısa olanın tam sayı katı çıkarılarak tekrar tekrar kısaltılır. Önemli nokta, en iyi katsayının çok az sayıda aday denenerek bulunabilmesidir.
Her kafes örneği tam olarak 12 ardışık Tribonacci değeri kullanır. Bu yüzden \(12N\) indeksine kadar tüm diziyi saklamak gerekmez; üç ardışık terimden oluşan kayan bir durum yeterlidir.
\((t_k,t_{k+1},t_{k+2})\) biliniyorsa bir sonraki değer
$$t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}$$
ile bulunur. Her 12 terimde bir yeni \((v_n,w_n)\) çifti oluşur. Böylece dış problem, \(\mathbb{Z}v+\mathbb{Z}w\subseteq\mathbb{Z}^3\) biçimindeki bağımsız kısa vektör sorgularına ayrılır.
Sabit \(v,w\) için amaç
$$m(v,w)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|av+bw\right\|_1$$
değerini bulmaktır. Eğer \(w\) yerine
$$w'=w-tv\qquad (t\in\mathbb{Z})$$
yazarsak kafes değişmez, çünkü
$$\mathbb{Z}v+\mathbb{Z}w=\mathbb{Z}v+\mathbb{Z}(w-tv).$$
Bu, Gauss indirgemesindeki aynı unimodüler taban dönüşümüdür. Dolayısıyla bir üreteci diğerinin tam sayı katıyla kaydırmak serbesttir; yeter ki \(L_1\) normu küçülsün.
\(v\) mevcut durumda daha kısa olsun. O zaman
$$f(t)=\left\|w-tv\right\|_1=\sum_{i=1}^{3}\left|w_i-t v_i\right|,\qquad t\in\mathbb{Z}$$
tanımlanır. Her \(\left|w_i-t v_i\right|\) terimi \(t\)'ye göre konveks ve parçalı doğrusaldır. Eğimin değiştiği yer yalnızca \(v_i\ne 0\) ise \(t=w_i/v_i\) noktasıdır. Bu yüzden \(f(t)\) de aynı tiptedir ve bütün kırılma noktaları koordinat oranlarından gelir.
Tam sayılar üzerinde minimum, bu kırılma noktalarına komşu tam sayılardan birinde gerçekleşir. Bu nedenle her \(v_i\ne 0\) için
$$\left\lfloor\frac{w_i}{v_i}\right\rfloor,\qquad \left\lfloor\frac{w_i}{v_i}\right\rfloor+1$$
ve ayrıca \(t=0\) denenmesi yeterlidir. Üç boyutta en fazla yedi aday vardır.
Döngü her zaman daha kısa vektörü öne alır. En iyi tam sayı \(t\) bulunur, \(w-tv\) hesaplanır ve yalnızca
$$\left\|w-tv\right\|_1<\left\|w\right\|_1$$
olduğunda güncelleme kabul edilir. Her kabul edilen adım kafesi korur ve bir taban vektörünün normunu kesin olarak azaltır; dolayısıyla süreç sonlu adımda durur.
Test edilen hiçbir tam sayı katı daha uzun vektörü kısaltmıyorsa çift, bu \(L_1\) kaydırma işlemi açısından yerel olarak indirgenmiştir. Uygulamalar da bu durumda indirgenmiş çiftteki daha kısa sıfır-olmayan vektörün normunu döndürür.
C++ ve Java uygulamaları geç indeksler için her seferinde başa dönmez. Bunun yerine şu companion matrisi kullanır:
$$A=\begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}.$$
Bu matris durum vektörünü bir adım ileri taşır:
$$A\begin{pmatrix}t_{k+2}\\ t_{k+1}\\ t_k\end{pmatrix}=\begin{pmatrix}t_{k+3}\\ t_{k+2}\\ t_{k+1}\end{pmatrix}.$$
Böylece hızlı üs alma ile gereken başlangıç durumu \(O(\log k)\) zamanda elde edilir; sonra terimler doğrusal olarak akıtılır.
İlk 12 Tribonacci değeri
$$0,1,1,2,4,7,13,24,44,81,149,274$$
olur. Buradan
$$v=(-1,3,28),\qquad w=(-11,125,40826)$$
elde edilir. Başlangıç normları
$$\|v\|_1=|-1|+|3|+|28|=32,$$
$$\|w\|_1=|-11|+|125|+|40826|=40962$$
şeklindedir. \(w\)'yi indirgemek için oranlar
$$\frac{-11}{-1}=11,\qquad \frac{125}{3}\approx 41.67,\qquad \frac{40826}{28}\approx 1458.07$$
incelenir. En iyi aday \(t=1458\) olur ve
$$w-1458v=(1447,-4249,2)$$
çıkar. Bunun normu
$$\|w-1458v\|_1=1447+4249+2=5698$$
olur. Bu değer \(40962\)'den çok küçüktür ama hâlâ \(\|v\|_1=32\)'den büyüktür. Daha ileri tam sayı kaydırmaları ikinci vektörü azaltmadığı için en kısa sıfır-olmayan kafes vektörü uzunluğu
$$s(1)=32$$
olur. Bu, uygulamanın kullandığı ilk kontrol değeridir. İkinci kontrol ise
$$S(10)=130762273722$$
eşitliğidir.
C++ ve Java uygulamaları aynı sayısal yöntemi paylaşır. Tribonacci değerleri akış halinde üretilir, 12 değer tamponlanır, bu değerlerden iki 3 boyutlu üreteç kurulup yukarıdaki indirgeme döngüsü çalıştırılır ve bulunan en kısa \(L_1\) uzunluğu toplama eklenir.
Üçüncü koordinat iki Tribonacci değerinin çarpımı olduğundan ara büyüklükler yüksek olabilir. Bu yüzden C++ normlar ve toplam için 128 bit tamsayılar kullanır; Java ise aynı nedenle keyfi uzunluklu tamsayı aritmetiğine başvurur.
C++ uygulaması ayrıca, birden fazla donanım iş parçacığı varsa \(1\le n\le N\) aralığını bitişik parçalara ayırabilir. Her parça başlangıç Tribonacci durumunu matris üs alma ile bulur, kendi terimlerini bağımsız işler ve kısmi toplam döndürür.
Python uygulaması ise bilerek ince tutulmuştur: C++ çözücüsünün derlenmiş halde bulunduğundan emin olur, bu programı çalıştırır ve yazdırılan onluk cevabı geri döndürür. Yani matematiksel yöntem aynıdır; Python burada köprü katmanı görevindedir.
Tam hedef çalıştırılmadan önce ilk vektör çifti, \(s(1)=32\) ve \(S(10)=130762273722\) kontrol edilir. Böylece hem dizideki indeksleme hataları hem de indirgeme mantığındaki sapmalar erkenden yakalanır.
Bir kafes örneği için gerekli 12 Tribonacci değerini üretmek \(O(1)\) zaman ve \(O(1)\) bellek gerektirir. Her indirgeme iterasyonu en fazla yedi tam sayı adayını dener; bu yüzden tek iterasyon da \(O(1)\)'dir. Bu 3 boyutlu rütbe-2 tabanlarda kabul edilen indirgeme adımlarının sayısı pratikte küçüktür, dolayısıyla \(n\) başına ortalama maliyet fiilen sabittir.
Bunun sonucu olarak toplam sıralı çalışma süresi
$$O(N)$$
olur. İş \(P\) bağımsız parçaya bölündüğünde, her parça matris sıçraması için ek \(O(\log N)\) başlangıç maliyeti öder. Toplam iş yine lineer kalır ve parça başına duvar saati yaklaşık
$$O\!\left(\frac{N}{P}+\log N\right)$$
düzeyindedir; bellek kullanımı parça başına \(O(1)\)'dir.
La sucesión Tribonacci se define por
$$t_1=0,\qquad t_2=t_3=1,\qquad t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
Para cada \(n\ge 1\), se toman los 12 valores consecutivos
$$r_k=t_{12n-12+k}\qquad (1\le k\le 12)$$
y se construyen dos vectores de \(\mathbb{Z}^3\):
$$v_n=(r_1-r_2,\ r_3+r_4,\ r_5r_6),\qquad w_n=(r_7-r_8,\ r_9+r_{10},\ r_{11}r_{12}).$$
Hay que calcular
$$s(n)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|a v_n+b w_n\right\|_1,$$
donde
$$\left\|(x,y,z)\right\|_1=|x|+|y|+|z|,$$
y después sumar:
$$S(N)=\sum_{n=1}^{N} s(n).$$
El objetivo final usa \(N=20{,}000{,}000\), así que la solución debe generar la sucesión y resolver cada problema de retículo con coste esencialmente constante.
El retículo generado por \(v_n\) y \(w_n\) es
$$L_n=\{a v_n+b w_n:\ a,b\in\mathbb{Z}\}.$$
Como este retículo tiene rango 2, las implementaciones usan una versión en norma \(L_1\) de la reducción con dos vectores: se acorta repetidamente el generador más largo restándole un múltiplo entero del más corto. La clave es que el mejor múltiplo se encuentra probando muy pocos enteros.
Cada instancia del retículo consume exactamente 12 términos consecutivos de la sucesión. No hace falta guardar toda la secuencia hasta el índice \(12N\); basta con mantener un estado rodante de tres términos consecutivos.
Si ya conocemos \((t_k,t_{k+1},t_{k+2})\), el siguiente valor es
$$t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
Cada vez que se emiten 12 valores se forma un nuevo par \((v_n,w_n)\). Así, el problema global se convierte en una secuencia de consultas independientes sobre retículos del tipo \(\mathbb{Z}v+\mathbb{Z}w\subseteq\mathbb{Z}^3\).
Para vectores fijos \(v,w\), queremos
$$m(v,w)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|av+bw\right\|_1.$$
Si sustituimos \(w\) por
$$w'=w-tv\qquad (t\in\mathbb{Z}),$$
el retículo no cambia, porque
$$\mathbb{Z}v+\mathbb{Z}w=\mathbb{Z}v+\mathbb{Z}(w-tv).$$
Se trata de la misma transformación unimodular de base que aparece en la reducción de Gauss. Por tanto, podemos “cizallar” un generador mediante múltiplos enteros del otro siempre que eso reduzca la longitud en norma \(L_1\).
Supongamos que \(v\) es el vector actual más corto. Definimos
$$f(t)=\left\|w-tv\right\|_1=\sum_{i=1}^{3}\left|w_i-t v_i\right|,\qquad t\in\mathbb{Z}.$$
Cada término \(\left|w_i-t v_i\right|\) es convexo y lineal por tramos respecto de \(t\). Su pendiente solo cambia cuando \(t=w_i/v_i\) para una coordenada con \(v_i\ne 0\). En consecuencia, \(f(t)\) también es convexa y lineal por tramos, y todos sus puntos de quiebre provienen de esas razones coordenada a coordenada.
Sobre los enteros, un mínimo de una función convexa de este tipo debe aparecer en un entero adyacente a un punto de quiebre. Por eso basta con probar
$$\left\lfloor\frac{w_i}{v_i}\right\rfloor,\qquad \left\lfloor\frac{w_i}{v_i}\right\rfloor+1$$
para cada coordenada con \(v_i\ne 0\), además de \(t=0\). En dimensión 3 eso produce como máximo siete candidatos.
El bucle mantiene siempre primero al vector más corto. Calcula el mejor entero \(t\), forma \(w-tv\) y acepta el cambio solo si la norma \(L_1\) disminuye estrictamente:
$$\left\|w-tv\right\|_1<\left\|w\right\|_1.$$
Cada paso aceptado conserva el retículo y reduce estrictamente la norma de uno de los vectores de la base, así que el proceso necesariamente termina. Cuando ningún múltiplo entero probado acorta más al vector largo, la base queda reducida localmente para esta operación de cizallamiento en norma \(L_1\).
Las implementaciones devuelven entonces el vector no nulo más corto de la pareja reducida. Ese es el valor usado para \(s(n)\).
Las implementaciones en C++ y Java no reinician la sucesión desde el principio cuando necesitan índices grandes. En su lugar usan la matriz compañera
$$A=\begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}.$$
Dicha matriz adelanta el vector de estado un paso:
$$A\begin{pmatrix}t_{k+2}\\ t_{k+1}\\ t_k\end{pmatrix}=\begin{pmatrix}t_{k+3}\\ t_{k+2}\\ t_{k+1}\end{pmatrix}.$$
Así, la exponenciación binaria permite obtener cualquier estado inicial en \(O(\log k)\), y después la secuencia se sigue de manera lineal.
Los primeros 12 valores Tribonacci son
$$0,1,1,2,4,7,13,24,44,81,149,274.$$
De ahí salen
$$v=(-1,3,28),\qquad w=(-11,125,40826).$$
Las normas iniciales valen
$$\|v\|_1=|-1|+|3|+|28|=32,$$
$$\|w\|_1=|-11|+|125|+|40826|=40962.$$
Para reducir \(w\), miramos las razones
$$\frac{-11}{-1}=11,\qquad \frac{125}{3}\approx 41.67,\qquad \frac{40826}{28}\approx 1458.07.$$
El mejor entero probado es \(t=1458\), y entonces
$$w-1458v=(1447,-4249,2),$$
con norma
$$\|w-1458v\|_1=1447+4249+2=5698.$$
Es una mejora enorme respecto a \(40962\), pero sigue siendo mayor que \(\|v\|_1=32\). Ningún cizallamiento entero adicional acorta el segundo vector, así que la longitud del vector no nulo más corto es
$$s(1)=32.$$
Ese es precisamente el primer punto de control del programa. Un segundo control verifica que
$$S(10)=130762273722.$$
Las implementaciones en C++ y Java comparten el mismo núcleo numérico. Generan los valores Tribonacci sobre la marcha, almacenan 12 términos consecutivos, construyen los dos generadores tridimensionales, ejecutan el bucle de reducción descrito antes y añaden la longitud mínima en norma \(L_1\) al total acumulado.
Como la tercera coordenada es el producto de dos términos Tribonacci, los valores intermedios pueden crecer bastante. Por eso la implementación en C++ usa enteros de 128 bits para normas y sumas, mientras que la implementación en Java usa enteros de precisión arbitraria para el mismo propósito.
La implementación en C++ también puede dividir el intervalo \(1\le n\le N\) en bloques contiguos cuando hay varios hilos disponibles. Cada bloque calcula su estado Tribonacci inicial mediante potencia de matrices, procesa sus términos de forma independiente y devuelve una suma parcial.
La implementación en Python es deliberadamente ligera: se asegura de que el solucionador en C++ esté disponible, ejecuta ese binario compilado y devuelve la respuesta decimal impresa. En otras palabras, el método matemático es el mismo y Python actúa solo como capa de enlace.
Antes de la ejecución completa, la implementación comprueba el primer par de vectores generado, confirma \(s(1)=32\) y confirma \(S(10)=130762273722\). Esas comprobaciones ayudan a detectar errores de indexado y fallos en la reducción.
Generar los 12 valores Tribonacci de una instancia cuesta \(O(1)\) tiempo y \(O(1)\) memoria. Cada iteración de reducción evalúa como mucho siete enteros candidatos, así que también es \(O(1)\). En la práctica, el número de reducciones aceptadas es pequeño para estas bases de rango 2 en dimensión 3, de modo que el coste medio por \(n\) es efectivamente constante.
Por tanto, el tiempo secuencial total es lineal en el número de instancias:
$$O(N).$$
Si el trabajo se reparte en \(P\) bloques independientes, cada bloque paga además una inicialización de \(O(\log N)\) por el salto matricial. El trabajo total sigue siendo lineal y el tiempo de reloj por bloque queda cerca de
$$O\!\left(\frac{N}{P}+\log N\right),$$
con \(O(1)\) memoria por bloque.
设 Tribonacci 数列满足
$$t_1=0,\qquad t_2=t_3=1,\qquad t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
对每个 \(n\ge 1\)，取连续 12 项
$$r_k=t_{12n-12+k}\qquad (1\le k\le 12),$$
并构造两个 \(\mathbb{Z}^3\) 向量：
$$v_n=(r_1-r_2,\ r_3+r_4,\ r_5r_6),\qquad w_n=(r_7-r_8,\ r_9+r_{10},\ r_{11}r_{12}).$$
我们要求
$$s(n)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|a v_n+b w_n\right\|_1,$$
其中
$$\left\|(x,y,z)\right\|_1=|x|+|y|+|z|,$$
然后再求总和
$$S(N)=\sum_{n=1}^{N} s(n).$$
最终目标取 \(N=20{,}000{,}000\)。因此算法必须一边在线生成数列，一边快速求出每个秩 2 格在 \(L_1\) 范数下的最短非零向量长度。
由 \(v_n\) 和 \(w_n\) 生成的格为
$$L_n=\{a v_n+b w_n:\ a,b\in\mathbb{Z}\}.$$
由于这里始终是两个生成向量，所以实现采用的是一种适用于 \(L_1\) 范数的二向量约化思想：不断用“长向量减去短向量的整数倍”来缩短基。关键在于，最佳整数倍并不需要暴力搜索，而是只需检查极少数候选值。
每个格实例只用到连续 12 个 Tribonacci 值，因此完全没有必要把直到 \(12N\) 的整个数列表全部存下来。维护三个连续项组成的滚动状态就足够了。
如果当前已知 \((t_k,t_{k+1},t_{k+2})\)，那么下一项满足
$$t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
每输出 12 项，就恰好得到一个新的向量对 \((v_n,w_n)\)。这样原问题就被拆成了一串彼此独立的格最短向量问题，每个格都形如 \(\mathbb{Z}v+\mathbb{Z}w\subseteq\mathbb{Z}^3\)。
对固定的 \(v,w\)，我们要找的是
$$m(v,w)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|av+bw\right\|_1.$$
如果把 \(w\) 改写为
$$w'=w-tv\qquad (t\in\mathbb{Z}),$$
那么格本身并不会改变，因为
$$\mathbb{Z}v+\mathbb{Z}w=\mathbb{Z}v+\mathbb{Z}(w-tv).$$
这与 Gauss 约化中常见的 unimodular 基变换完全同型。也就是说，只要某个整数倍能让向量在 \(L_1\) 范数下更短，就可以放心地进行这种“剪切”操作，而不会改变格中的可达点集。
设当前较短的向量是 \(v\)，希望缩短较长的 \(w\)。定义
$$f(t)=\left\|w-tv\right\|_1=\sum_{i=1}^{3}\left|w_i-t v_i\right|,\qquad t\in\mathbb{Z}.$$
每一项 \(\left|w_i-t v_i\right|\) 对 \(t\) 来说都是凸的分段线性函数；只有在 \(v_i\ne 0\) 时，斜率才会在 \(t=w_i/v_i\) 处发生变化。因此整个 \(f(t)\) 也是凸的分段线性函数，而且所有拐点都来自这些坐标比值。
对整数 \(t\) 而言，这种函数的最小值一定出现在某个拐点相邻的整数位置上。因此只需要检查每个非零坐标对应的
$$\left\lfloor\frac{w_i}{v_i}\right\rfloor,\qquad \left\lfloor\frac{w_i}{v_i}\right\rfloor+1$$
以及额外的 \(t=0\) 即可。因为只有 3 个坐标，所以最多只需评估 7 个整数候选值。
这就是实现能够在常数时间内找出最佳整数剪切，而不必在所有整数上枚举的原因。
约化循环始终把较短向量放在前面。它先求出最佳整数 \(t\)，然后计算 \(w-tv\)，仅当
$$\left\|w-tv\right\|_1<\left\|w\right\|_1$$
时才接受这次替换。每一次被接受的更新都会保持格不变，同时严格减小某个基向量的 \(L_1\) 长度，所以过程必定在有限步内终止。
当所有候选整数倍都不能进一步缩短较长向量时，这一对基向量就对当前的 \(L_1\) 剪切操作而言已经局部约化。实现随后返回这对约化后基向量中较短的非零向量长度，并把它作为该实例的 \(s(n)\)。
C++ 与 Java 实现都不会为了处理后面的区间而从头重新生成 Tribonacci 数列。它们使用的是三阶递推的伴随矩阵
$$A=\begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}.$$
该矩阵把状态向量向前推进一步：
$$A\begin{pmatrix}t_{k+2}\\ t_{k+1}\\ t_k\end{pmatrix}=\begin{pmatrix}t_{k+3}\\ t_{k+2}\\ t_{k+1}\end{pmatrix}.$$
因此可以利用二分快速幂在 \(O(\log k)\) 时间内直接跳到任意所需起点，之后再线性流式生成后续项。这一点对大规模分段计算尤其重要。
前 12 个 Tribonacci 值为
$$0,1,1,2,4,7,13,24,44,81,149,274.$$
于是得到
$$v=(-1,3,28),\qquad w=(-11,125,40826).$$
它们的初始 \(L_1\) 范数分别是
$$\|v\|_1=|-1|+|3|+|28|=32,$$
$$\|w\|_1=|-11|+|125|+|40826|=40962.$$
为了缩短 \(w\)，考察三个坐标比值
$$\frac{-11}{-1}=11,\qquad \frac{125}{3}\approx 41.67,\qquad \frac{40826}{28}\approx 1458.07.$$
在对应整数候选中，最佳选择是 \(t=1458\)。这时
$$w-1458v=(1447,-4249,2),$$
其范数为
$$\|w-1458v\|_1=1447+4249+2=5698.$$
虽然这比 \(40962\) 小得多，但仍明显大于 \(\|v\|_1=32\)。继续尝试整数剪切后，第二个向量无法再被缩短，因此该格中最短非零向量长度就是
$$s(1)=32.$$
这正好对应实现里的第一个校验点。实现还额外验证了
$$S(10)=130762273722,$$
用来检查前 10 个实例的累计结果。
C++ 与 Java 实现共享同一套数值流程。它们在线生成 Tribonacci 值，每次缓冲 12 项，用这 12 项构造两个三维生成向量，执行上面的约化循环，然后把得到的最短 \(L_1\) 长度累加到总和中。
由于第三个坐标是两个 Tribonacci 项的乘积，中间值可能相当大。因此 C++ 在向量范数和总和上使用 128 位整数，而 Java 用任意精度整数来承担同样的工作，避免累计阶段溢出。
C++ 实现还可以在有多个硬件线程时把区间 \(1\le n\le N\) 切成若干连续块。每一块先用矩阵快速幂求出自己的起始 Tribonacci 状态，再独立流式处理本块中的所有实例，最后把部分和汇总起来。
Python 实现本身不重复实现数学算法，而是作为一个很薄的桥接层：它确保 C++ 求解器可用，运行编译后的程序，并提取输出中的十进制答案。因此三种语言版本在数学上是一致的，只是职责分工不同。
在正式计算完整目标之前，实现会先检查第一个生成出的向量对，确认 \(s(1)=32\)，并确认 \(S(10)=130762273722\)。这些检查可以及时发现数列索引或约化逻辑中的偏差。
生成一个实例所需的 12 个 Tribonacci 值需要 \(O(1)\) 时间和 \(O(1)\) 额外空间。每次约化迭代只会评估至多 7 个整数候选，因此单次迭代也是 \(O(1)\)。对于这里的三维秩 2 基，实际被接受的约化步数很少，所以平均到每个 \(n\) 的代价可以视为常数。
因此顺序版本的总时间复杂度是
$$O(N).$$
如果把工作拆成 \(P\) 个彼此独立的区间块，那么每个块都需要一次 \(O(\log N)\) 的矩阵跳转初始化。总工作量仍然保持线性，而单块的墙钟时间接近
$$O\!\left(\frac{N}{P}+\log N\right),$$
每个块所需的额外空间仍然只是 \(O(1)\)。
Последовательность Трибоначчи задаётся формулами
$$t_1=0,\qquad t_2=t_3=1,\qquad t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
Для каждого \(n\ge 1\) берутся 12 подряд идущих значений
$$r_k=t_{12n-12+k}\qquad (1\le k\le 12),$$
из которых строятся два вектора в \(\mathbb{Z}^3\):
$$v_n=(r_1-r_2,\ r_3+r_4,\ r_5r_6),\qquad w_n=(r_7-r_8,\ r_9+r_{10},\ r_{11}r_{12}).$$
Нужно вычислить
$$s(n)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|a v_n+b w_n\right\|_1,$$
где
$$\left\|(x,y,z)\right\|_1=|x|+|y|+|z|,$$
а затем просуммировать:
$$S(N)=\sum_{n=1}^{N} s(n).$$
В целевой задаче \(N=20{,}000{,}000\), поэтому решение должно одновременно эффективно порождать последовательность и быстро находить кратчайший ненулевой вектор в каждом решёточном случае ранга 2.
Решётка, порождённая \(v_n\) и \(w_n\), имеет вид
$$L_n=\{a v_n+b w_n:\ a,b\in\mathbb{Z}\}.$$
Поскольку в каждом случае есть только два порождающих вектора, реализации используют \(L_1\)-аналог двухвекторной редукции: более длинный вектор многократно заменяется на себя минус целое кратное более короткого. Ключевой факт в том, что лучшее кратное можно найти, проверив лишь несколько целых кандидатов.
Каждому экземпляру решётки соответствуют ровно 12 подряд идущих значений последовательности. Хранить всю последовательность до индекса \(12N\) не нужно; достаточно поддерживать скользящее состояние из трёх последовательных членов.
Если известны \((t_k,t_{k+1},t_{k+2})\), то следующий член равен
$$t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
После каждых 12 сгенерированных значений получается одна пара \((v_n,w_n)\). Тем самым исходная задача распадается на последовательность независимых запросов о кратчайшем векторе в решётках вида \(\mathbb{Z}v+\mathbb{Z}w\subseteq\mathbb{Z}^3\).
Для фиксированных \(v,w\) требуется найти
$$m(v,w)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|av+bw\right\|_1.$$
Если заменить \(w\) на
$$w'=w-tv\qquad (t\in\mathbb{Z}),$$
то решётка не изменится, потому что
$$\mathbb{Z}v+\mathbb{Z}w=\mathbb{Z}v+\mathbb{Z}(w-tv).$$
Это тот же unimodular-переход базиса, который используется в редукции Гаусса. Значит, можно свободно «сдвигать» один генератор на целое кратное другого, если это уменьшает длину в норме \(L_1\).
Пусть \(v\) сейчас короче, и мы хотим уменьшить \(w\). Рассмотрим функцию
$$f(t)=\left\|w-tv\right\|_1=\sum_{i=1}^{3}\left|w_i-t v_i\right|,\qquad t\in\mathbb{Z}.$$
Каждое слагаемое \(\left|w_i-t v_i\right|\) является выпуклой кусочно-линейной функцией от \(t\). Наклон меняется только в точке \(t=w_i/v_i\), если \(v_i\ne 0\). Поэтому и вся функция \(f(t)\) выпукла и кусочно-линейна, а все точки излома определяются этими отношениями координат.
На целых числах минимум такой функции достигается на целом числе, соседнем с какой-либо точкой излома. Значит, достаточно проверять
$$\left\lfloor\frac{w_i}{v_i}\right\rfloor,\qquad \left\lfloor\frac{w_i}{v_i}\right\rfloor+1$$
для каждой координаты с \(v_i\ne 0\), а также \(t=0\). В размерности 3 это даёт не более семи кандидатов.
Цикл всегда ставит более короткий вектор первым. Затем выбирается лучшее целое \(t\), вычисляется \(w-tv\), и замена принимается только если новая норма строго меньше прежней:
$$\left\|w-tv\right\|_1<\left\|w\right\|_1.$$
Каждый принятый шаг сохраняет решётку и строго уменьшает норму одного из векторов базиса, поэтому процесс обязательно заканчивается. Если ни одно из проверенных целых кратных уже не укорачивает длинный вектор, пара считается локально редуцированной относительно этой \(L_1\)-операции.
После этого реализации возвращают более короткий ненулевой вектор из полученной пары. Именно его длина и используется как \(s(n)\).
Реализации на C++ и Java не запускают последовательность заново с самого начала для каждого позднего диапазона. Вместо этого используется сопровождающая матрица
$$A=\begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}.$$
Она продвигает вектор состояния на один шаг:
$$A\begin{pmatrix}t_{k+2}\\ t_{k+1}\\ t_k\end{pmatrix}=\begin{pmatrix}t_{k+3}\\ t_{k+2}\\ t_{k+1}\end{pmatrix}.$$
Поэтому возведение в степень за \(O(\log k)\) позволяет сразу получить нужное начальное состояние, а затем продолжить линейный поток вычислений.
Первые 12 значений Трибоначчи таковы:
$$0,1,1,2,4,7,13,24,44,81,149,274.$$
Следовательно,
$$v=(-1,3,28),\qquad w=(-11,125,40826).$$
Начальные \(L_1\)-нормы равны
$$\|v\|_1=|-1|+|3|+|28|=32,$$
$$\|w\|_1=|-11|+|125|+|40826|=40962.$$
Чтобы укоротить \(w\), рассматриваем отношения координат
$$\frac{-11}{-1}=11,\qquad \frac{125}{3}\approx 41.67,\qquad \frac{40826}{28}\approx 1458.07.$$
Лучшим проверенным значением оказывается \(t=1458\), после чего
$$w-1458v=(1447,-4249,2),$$
и
$$\|w-1458v\|_1=1447+4249+2=5698.$$
Это намного меньше \(40962\), но всё ещё больше, чем \(\|v\|_1=32\). Дальнейшие целочисленные сдвиги второй вектор уже не укорачивают, поэтому
$$s(1)=32.$$
Именно это значение служит первым контрольным тестом реализации. Второй контрольный тест проверяет
$$S(10)=130762273722.$$
Реализации на C++ и Java используют один и тот же вычислительный каркас. Они порождают значения Трибоначчи на лету, буферизуют 12 последовательных членов, строят два трёхмерных генератора, запускают описанный выше цикл редукции и прибавляют найденную кратчайшую \(L_1\)-длину к общей сумме.
Поскольку третья координата представляет собой произведение двух значений Трибоначчи, промежуточные величины могут быть большими. Поэтому C++ использует 128-битную целочисленную арифметику для норм и накопленной суммы, а Java применяет целые числа произвольной длины.
В реализации на C++ диапазон \(1\le n\le N\) при наличии нескольких аппаратных потоков может делиться на непрерывные блоки. Каждый блок независимо вычисляет своё начальное состояние Трибоначчи с помощью степени матрицы, затем обрабатывает свой поддиапазон и возвращает частичную сумму.
Реализация на Python преднамеренно очень тонкая: она следит за наличием готового C++-решателя, запускает скомпилированную программу и извлекает напечатанный десятичный ответ. То есть математический метод остаётся тем же, а Python выступает только как мост.
Перед полным запуском выполняются проверки первого сгенерированного векторного набора, равенства \(s(1)=32\) и равенства \(S(10)=130762273722\). Эти контрольные точки помогают поймать ошибки индексации и ошибки редукции.
Порождение 12 значений Трибоначчи для одного экземпляра требует \(O(1)\) времени и \(O(1)\) памяти. Каждая итерация редукции проверяет не более семи целых кандидатов, так что одна итерация тоже стоит \(O(1)\). На практике число принятых редукций для этих баз ранга 2 в размерности 3 мало, поэтому средняя цена на одно \(n\) фактически постоянна.
Следовательно, полное последовательное время работы линейно по числу экземпляров:
$$O(N).$$
Если вычисления разбиваются на \(P\) независимых блоков, каждый блок дополнительно платит \(O(\log N)\) за матричный прыжок к своему старту. Суммарная работа остаётся линейной, а реальное время на блок близко к
$$O\!\left(\frac{N}{P}+\log N\right),$$
при \(O(1)\) памяти на блок.
تُعرَّف متتالية تريبوناتشي بالعلاقة
$$t_1=0,\qquad t_2=t_3=1,\qquad t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
ولكل \(n\ge 1\) نأخذ القيم الاثنتي عشرة المتتالية
$$r_k=t_{12n-12+k}\qquad (1\le k\le 12),$$
ثم نبني متجهين في \(\mathbb{Z}^3\):
$$v_n=(r_1-r_2,\ r_3+r_4,\ r_5r_6),\qquad w_n=(r_7-r_8,\ r_9+r_{10},\ r_{11}r_{12}).$$
المطلوب هو حساب
$$s(n)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|a v_n+b w_n\right\|_1,$$
حيث
$$\left\|(x,y,z)\right\|_1=|x|+|y|+|z|,$$
ثم جمع هذه القيم:
$$S(N)=\sum_{n=1}^{N} s(n).$$
في الحساب النهائي يكون \(N=20{,}000{,}000\)، ولذلك يجب أن تكون الطريقة قادرة على توليد المتتالية ومعالجة كل شبكة من الرتبة 2 بكلفة شبه ثابتة.
الشبكة المتولدة من \(v_n\) و\(w_n\) هي
$$L_n=\{a v_n+b w_n:\ a,b\in\mathbb{Z}\}.$$
ولأن لدينا دائمًا مولدين فقط، فإن التنفيذات تستخدم نظيرًا لاختزال متجهين لكن وفق معيار \(L_1\): نأخذ المتجه الأطول ونطرح منه مرارًا مضاعفًا صحيحًا للمتجه الأقصر. الفكرة الأساسية هي أن أفضل مضاعف صحيح لا يحتاج إلى بحث واسع، بل يكفي فحص عدد صغير جدًا من المرشحين.
كل حالة من حالات الشبكة تستخدم 12 حدًا متتاليًا فقط من المتتالية. لذلك لا حاجة لتخزين كل القيم حتى الفهرس \(12N\)؛ يكفي الاحتفاظ بحالة متحركة من ثلاثة حدود متتالية.
إذا كانت الحالة الحالية هي \((t_k,t_{k+1},t_{k+2})\)، فإن الحد التالي يُحسب من
$$t_{k+3}\equiv t_{k+2}+t_{k+1}+t_k \pmod{10^7}.$$
وبعد كل 12 قيمة متدفقة نحصل على زوج جديد \((v_n,w_n)\). وبهذا يتحول السؤال الكلي إلى سلسلة من مسائل المتجه الأقصر في شبكات من الشكل \(\mathbb{Z}v+\mathbb{Z}w\subseteq\mathbb{Z}^3\).
لزوج ثابت \(v,w\) نريد القيمة
$$m(v,w)=\min_{(a,b)\in \mathbb{Z}^2\setminus\{(0,0)\}} \left\|av+bw\right\|_1.$$
إذا استبدلنا \(w\) بالمتجه
$$w'=w-tv\qquad (t\in\mathbb{Z}),$$
فإن الشبكة نفسها لا تتغير، لأن
$$\mathbb{Z}v+\mathbb{Z}w=\mathbb{Z}v+\mathbb{Z}(w-tv).$$
وهذا هو نفس التحويل الأحادي المحدد الذي يظهر في اختزال غاوس. لذلك يمكننا قصّ أحد المولدين بمضاعف صحيح من الآخر من دون أن نغير نقاط الشبكة، ما دام ذلك يُقصِّر الطول وفق معيار \(L_1\).
لنفترض أن \(v\) هو المتجه الأقصر حاليًا ونريد اختزال \(w\). نعرّف
$$f(t)=\left\|w-tv\right\|_1=\sum_{i=1}^{3}\left|w_i-t v_i\right|,\qquad t\in\mathbb{Z}.$$
كل حد من الشكل \(\left|w_i-t v_i\right|\) هو دالة محدبة وخطية على مقاطع بالنسبة إلى \(t\)، ولا يتغير ميله إلا عندما \(t=w_i/v_i\) إذا كان \(v_i\ne 0\). ومن ثم فإن \(f(t)\) نفسها محدبة وخطية على مقاطع، وجميع نقاط الانكسار تأتي من نسب الإحداثيات هذه.
عند القيم الصحيحة، يتحقق الحد الأدنى لدالة من هذا النوع عند عدد صحيح مجاور لإحدى نقاط الانكسار. لذلك يكفي فحص
$$\left\lfloor\frac{w_i}{v_i}\right\rfloor,\qquad \left\lfloor\frac{w_i}{v_i}\right\rfloor+1$$
لكل إحداثي يحقق \(v_i\ne 0\)، مع إضافة المرشح \(t=0\). وفي ثلاثة أبعاد لا يزيد عدد المرشحين على سبعة.
تحافظ الحلقة دائمًا على وضع المتجه الأقصر أولًا. ثم تختار أفضل عدد صحيح \(t\)، وتكوّن \(w-tv\)، ولا تقبل الاستبدال إلا إذا تحسن معيار \(L_1\) تحسنًا صارمًا:
$$\left\|w-tv\right\|_1<\left\|w\right\|_1.$$
كل خطوة مقبولة تحفظ الشبكة وتُنقص طول أحد متجهي الأساس إنقاصًا صارمًا، ولذلك لا بد أن تنتهي العملية بعد عدد محدود من الخطوات. وعندما لا يعود أي مضاعف صحيح مُجرَّب قادرًا على تقصير المتجه الأطول، نعدّ الزوج مختزَلًا محليًا بالنسبة إلى عملية القص هذه في معيار \(L_1\).
بعد ذلك تعيد التنفيذات طول المتجه غير الصفري الأقصر في الزوج المختزل، وهو القيمة المستخدمة هنا على أنها \(s(n)\).
لا تعيد تنفيذات C++ وJava توليد المتتالية من البداية عند الحاجة إلى فهارس كبيرة. بدلًا من ذلك تستخدم مصفوفة الرفيق
$$A=\begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}.$$
وهذه المصفوفة تنقل متجه الحالة خطوة واحدة إلى الأمام:
$$A\begin{pmatrix}t_{k+2}\\ t_{k+1}\\ t_k\end{pmatrix}=\begin{pmatrix}t_{k+3}\\ t_{k+2}\\ t_{k+1}\end{pmatrix}.$$
وبالتالي يتيح الأس السريع الوصول إلى أي حالة ابتدائية مطلوبة خلال \(O(\log k)\)، ثم تُستكمل القيم التالية بصورة خطية.
أول 12 قيمة من متتالية تريبوناتشي هي
$$0,1,1,2,4,7,13,24,44,81,149,274.$$
ومنها نحصل على
$$v=(-1,3,28),\qquad w=(-11,125,40826).$$
المعياران الابتدائيان هما
$$\|v\|_1=|-1|+|3|+|28|=32,$$
$$\|w\|_1=|-11|+|125|+|40826|=40962.$$
ولاختزال \(w\) ننظر إلى النسب
$$\frac{-11}{-1}=11,\qquad \frac{125}{3}\approx 41.67,\qquad \frac{40826}{28}\approx 1458.07.$$
أفضل عدد صحيح مُجرَّب هو \(t=1458\)، وعندها
$$w-1458v=(1447,-4249,2),$$
ويكون المعيار
$$\|w-1458v\|_1=1447+4249+2=5698.$$
وهذا أفضل بكثير من \(40962\)، لكنه ما زال أكبر من \(\|v\|_1=32\). وبعد متابعة المحاولات لا يظهر قصّ صحيح إضافي يُقصِّر المتجه الثاني، ولذلك يكون طول أقصر متجه غير صفري في هذه الشبكة
$$s(1)=32.$$
وهذه هي قيمة التحقق الأولى في التنفيذ. كما يتحقق التنفيذ أيضًا من أن
$$S(10)=130762273722.$$
تتشابه التنفيذات في C++ وJava في الجوهر العددي. فهي تولد قيم تريبوناتشي أثناء التشغيل، وتخزن 12 قيمة متتالية، وتبني منهما المتجهين الثلاثيين، ثم تطبق حلقة الاختزال السابقة، وتضيف طول المتجه الأقصر وفق معيار \(L_1\) إلى المجموع التراكمي.
ولأن الإحداثي الثالث هو حاصل ضرب حدين من تريبوناتشي، فقد تكبر القيم الوسيطة بسرعة. لذلك تستخدم نسخة C++ أعدادًا صحيحة بعرض 128 بت لحساب المعايير والمجاميع، بينما تستخدم نسخة Java أعدادًا صحيحة ذات دقة غير محدودة للغرض نفسه.
وتستطيع نسخة C++ أيضًا تقسيم المجال \(1\le n\le N\) إلى مقاطع متجاورة عند توفر عدة خيوط عتادية. كل مقطع يحسب حالته الابتدائية في تريبوناتشي بواسطة أس المصفوفة، ثم يعالج حدوده محليًا بصورة مستقلة ويعيد مجموعًا جزئيًا.
أما تنفيذ Python فهو رقيق عمدًا: يتأكد من توافر المحلل المكتوب بـ C++، ثم يشغّل البرنامج المترجم ويعيد الجواب العشري المطبوع. أي إن العمل الرياضي نفسه يبقى موحدًا، بينما تعمل Python هنا كطبقة وصل.
قبل تشغيل الهدف الكامل، يجري التنفيذ فحوصًا على أول زوج متجهات مولَّد، ويتحقق من \(s(1)=32\) ومن \(S(10)=130762273722\). وهذه الفحوص تلتقط أخطاء الفهرسة أو أخطاء الاختزال مبكرًا.
توليد القيم الاثنتي عشرة اللازمة لحالة واحدة يحتاج إلى \(O(1)\) زمنًا و\(O(1)\) ذاكرةً إضافية. وكل تكرار من تكرارات الاختزال يفحص في أقصى حد سبعة أعداد صحيحة مرشحة، ولذلك فهو أيضًا \(O(1)\). وفي التطبيق العملي يكون عدد خطوات الاختزال المقبولة صغيرًا لهذه القواعد ذات الرتبة 2 في ثلاثة أبعاد، فيصبح متوسط الكلفة لكل \(n\) ثابتًا فعليًا.
لذلك يكون الزمن الكلي في التنفيذ التسلسلي
$$O(N).$$
وإذا قُسِّم العمل إلى \(P\) مقاطع مستقلة، فإن كل مقطع يدفع كلفة تهيئة إضافية مقدارها \(O(\log N)\) بسبب القفزة المصفوفية. يبقى مجموع العمل خطيًا، ويصبح زمن الجدار لكل مقطع قريبًا من
$$O\!\left(\frac{N}{P}+\log N\right),$$
مع ذاكرة مقدارها \(O(1)\) لكل مقطع.