The required quantity is
$$S=\sum_{a=1}^{7}\sum_{b=1}^{19} F\!\left(a^b,b^a,a^b+b^a\right).$$
Every summand begins from a positive triple
$$ (A,B,C)=\left(a^b,b^a,a^b+b^a\right), $$
so initially \(C=A+B\). The crucial task is therefore not the outer double sum itself, but understanding how the function \(F(A,B,C)\) is determined for triples in which one coordinate equals the sum of the other two.
The three implementations all reveal the same structure. A triple is reduced by a subtraction-style Euclidean step, while we record which coordinate currently plays the role of the sum. Once that forward trace is known, the value of \(F\) is reconstructed backward by a simple rule modulo \(3\).
Consider any positive triple \((A,B,C)\) satisfying exactly one of
$$A=B+C,\qquad B=A+C,\qquad C=A+B.$$
Because all entries are positive, the coordinate on the left-hand side is automatically the largest one. The reduction rule replaces that largest coordinate by the absolute difference of the other two.
If the current state satisfies \(C=A+B\), the next state is
$$ (A,B,C)\mapsto (A,B,|A-B|). $$
If \(A\ge B\), this becomes \((A,B,A-B)\), and then \(A=B+(A-B)\). If \(B>A\), it becomes \((A,B,B-A)\), and then \(B=A+(B-A)\). So after one step we still have a positive triple in which one coordinate is the sum of the other two; only the identity of that coordinate may change.
The same reasoning works cyclically in the other two cases. In other words, the process is a subtraction-based Euclidean algorithm applied to the two smaller numbers, with the coordinate labels \(A\), \(B\), and \(C\) remembering where the sum sits at each stage.
Two facts are immediate.
First, the common divisor is preserved. For example, when \(C=A+B\),
$$ \gcd(A,B,C)=\gcd(A,B)=\gcd(A,B,|A-B|), $$
and the same identity holds in the other two cases after relabeling.
Second, as long as the two smaller numbers are different, the largest number strictly decreases. Hence the reduction must terminate.
Termination occurs exactly when the two smaller numbers become equal. If those equal values are \(g\), then the third coordinate must be \(2g\). Therefore the only terminal forms are
$$ (2g,g,g),\qquad (g,2g,g),\qquad (g,g,2g), $$
where \(g=\gcd(A,B,C)\). The scale \(g\) survives all the way to the end, but the implementations show that \(F\) depends only on which coordinate carries the factor \(2\), not on the actual magnitude of \(g\).
During the forward reduction, record a symbol \(r_i\in\{A,B,C\}\) at each step to indicate which coordinate is currently equal to the sum of the other two. If the reduction ends after \(k\) steps, we obtain a trace
$$ r_1,r_2,\dots,r_k, $$
where \(r_k\) is also the role of the terminal form. Once this trace is known, the actual intermediate numbers are no longer needed for the second half of the computation.
The terminal states anchor the reconstruction through the base values
$$ F(2g,g,g)=1,\qquad F(g,2g,g)=2,\qquad F(g,g,2g)=3. $$
To propagate the answer backward through the trace, introduce the residue map
$$ \rho(A)=1,\qquad \rho(B)=2,\qquad \rho(C)=0. $$
If the later state already has value \(t\) and the preceding role is \(r\), then the earlier state receives the smallest integer larger than \(t\) that lies in the required residue class:
$$ N(t,r)=\min\{n>t:\ n\equiv \rho(r)\pmod 3\}. $$
The minimization above can be written directly, so the backward pass needs no search:
$$ N(t,r)=t+1+\left(\rho(r)-((t+1)\bmod 3)\right)\bmod 3. $$
This gives a compact recurrence for the whole function. The forward phase computes the role trace, the terminal role selects the starting value \(1\), \(2\), or \(3\), and the backward phase repeatedly applies the closed formula. That separation is the central idea of the solution.
Here
$$ A=2^3=8,\qquad B=3^2=9,\qquad C=8+9=17. $$
So we start from \((8,9,17)\), which already has role \(C\). The forward reduction is
$$ (8,9,17)\to(8,9,1)\to(8,7,1)\to(6,7,1)\to(6,5,1)\to(4,5,1)\to(4,3,1)\to(2,3,1)\to(2,1,1). $$
The corresponding role trace is
$$ C,\ B,\ A,\ B,\ A,\ B,\ A,\ B,\ A. $$
The terminal state is of the form \((2g,g,g)\), so the starting value for backward reconstruction is \(1\). Now discard the last role \(A\), reverse the rest, and force the required residues \(2,1,2,1,2,1,2,0\):
$$ 1\to 2\to 4\to 5\to 7\to 8\to 10\to 11\to 12. $$
Therefore
$$ F(8,9,17)=12. $$
This example comes directly from one term of the outer sum and shows both halves of the algorithm in action: forward Euclidean reduction, then backward residue reconstruction.
The C++, Python, and Java implementations iterate over all \(7\cdot 19=133\) pairs \((a,b)\). For each pair they compute \(A=a^b\), \(B=b^a\), form \(C=A+B\), evaluate \(F(A,B,C)\), and add the result to the running total.
The largest value that appears is still well within 64-bit range, so the implementations can stay entirely in integer arithmetic.
For one triple, the implementation repeatedly determines whether the current role is \(A\), \(B\), or \(C\), appends that role to a short list, and replaces the sum coordinate by the absolute difference of the remaining two values. The loop stops as soon as the two smaller numbers are equal, because the state has then reached one of the three terminal shapes.
After termination, the implementation converts the terminal role into the base value \(1\), \(2\), or \(3\). It then scans the stored trace backward, excluding the terminal role itself, and at each step jumps to the next larger integer in the residue class prescribed by that role. The closed formula above is exactly what the three implementations apply.
Let \(L(A,B,C)\) denote the number of forward reduction steps for one triple. Computing that triple takes \(O(L(A,B,C))\) time: the forward pass is linear in the trace length, and the backward reconstruction is another linear pass over the same trace.
If the trace is stored explicitly, the auxiliary memory is \(O(L(A,B,C))\) for that triple. Since the full program evaluates only 133 triples, the total running time is
$$ O\!\left(\sum_{a=1}^{7}\sum_{b=1}^{19} L\!\left(a^b,b^a,a^b+b^a\right)\right), $$
with working memory \(O(L_{\max})\) for the longest single trace. That is easily fast enough here because the outer search space is tiny and each inner step uses only comparisons, subtraction, and a modulo-\(3\) adjustment.
Gesucht ist die Summe
$$S=\sum_{a=1}^{7}\sum_{b=1}^{19} F\!\left(a^b,b^a,a^b+b^a\right).$$
Jeder Summand startet also mit einem positiven Tripel
$$ (A,B,C)=\left(a^b,b^a,a^b+b^a\right), $$
weshalb anfangs immer \(C=A+B\) gilt. Der eigentliche Kern der Aufgabe ist daher das Verständnis von \(F(A,B,C)\) für Tripel, bei denen genau eine Koordinate die Summe der beiden anderen ist.
Alle drei Implementierungen zeigen dieselbe Struktur. Ein solches Tripel wird mit einem subtraktionsbasierten euklidischen Schritt reduziert, während man speichert, welche Koordinate gerade die Summenrolle trägt. Ist diese Vorwärtsspur bekannt, wird der Wert von \(F\) rückwärts mit einer einfachen Modulo-\(3\)-Regel rekonstruiert.
Betrachte ein beliebiges positives Tripel \((A,B,C)\), das genau eine der Beziehungen
$$A=B+C,\qquad B=A+C,\qquad C=A+B$$
erfüllt. Wegen der Positivität ist die linke Seite jeweils automatisch die größte Koordinate. Der Reduktionsschritt ersetzt genau diese größte Koordinate durch die Betragsdifferenz der beiden anderen.
Falls aktuell \(C=A+B\) gilt, lautet der nächste Zustand
$$ (A,B,C)\mapsto (A,B,|A-B|). $$
Ist \(A\ge B\), dann erhält man \((A,B,A-B)\), und daraus folgt sofort \(A=B+(A-B)\). Ist stattdessen \(B>A\), dann wird daraus \((A,B,B-A)\), und nun gilt \(B=A+(B-A)\). Nach einem Schritt liegt also wieder ein positives Tripel vor, in dem eine Koordinate die Summe der beiden anderen ist; nur die Identität dieser Koordinate kann wechseln.
Dasselbe Argument funktioniert zyklisch in den beiden anderen Fällen. Anders gesagt: Auf den beiden kleineren Zahlen läuft eine subtraktionsbasierte Variante des euklidischen Algorithmus, während die Beschriftungen \(A\), \(B\) und \(C\) festhalten, wo die Summenrolle jeweils liegt.
Zwei Eigenschaften springen sofort ins Auge.
Erstens bleibt der größte gemeinsame Teiler erhalten. Im Fall \(C=A+B\) gilt etwa
$$ \gcd(A,B,C)=\gcd(A,B)=\gcd(A,B,|A-B|), $$
und nach Umbenennung gilt dieselbe Identität auch in den anderen beiden Fällen.
Zweitens wird die größte Zahl strikt kleiner, solange die beiden kleineren Zahlen verschieden sind. Deshalb muss der Prozess terminieren.
Der Endzustand tritt genau dann ein, wenn die beiden kleineren Zahlen gleich geworden sind. Sind diese beiden Werte gleich \(g\), dann muss die dritte Koordinate \(2g\) sein. Somit gibt es nur die drei Endformen
$$ (2g,g,g),\qquad (g,2g,g),\qquad (g,g,2g), $$
wobei \(g=\gcd(A,B,C)\) ist. Die Skala \(g\) bleibt also bis zum Ende sichtbar, doch die Implementierungen zeigen, dass \(F\) nur davon abhängt, welche Koordinate den Faktor \(2\) trägt, nicht vom tatsächlichen Zahlenwert von \(g\).
Während der Vorwärtsreduktion wird in jedem Schritt ein Symbol \(r_i\in\{A,B,C\}\) notiert, das angibt, welche Koordinate aktuell der Summe der beiden anderen entspricht. Endet die Reduktion nach \(k\) Schritten, so erhält man die Spur
$$ r_1,r_2,\dots,r_k, $$
wobei \(r_k\) zugleich die Rolle des Endzustands ist. Sobald diese Spur bekannt ist, werden die konkreten Zwischenzahlen für die zweite Hälfte der Berechnung nicht mehr benötigt.
Die Endformen verankern die Rekonstruktion über die Basiswerte
$$ F(2g,g,g)=1,\qquad F(g,2g,g)=2,\qquad F(g,g,2g)=3. $$
Für den Rückwärtsschritt führt man die Restklassenabbildung
$$ \rho(A)=1,\qquad \rho(B)=2,\qquad \rho(C)=0 $$
ein. Hat der spätere Zustand bereits den Wert \(t\) und lautet die frühere Rolle \(r\), dann bekommt der frühere Zustand die kleinste ganze Zahl größer als \(t\), die in der geforderten Restklasse liegt:
$$ N(t,r)=\min\{n>t:\ n\equiv \rho(r)\pmod 3\}. $$
Die obige Minimierung lässt sich direkt auswerten; eine Suche ist nicht nötig:
$$ N(t,r)=t+1+\left(\rho(r)-((t+1)\bmod 3)\right)\bmod 3. $$
Damit erhält man eine kompakte Rekurrenz für die ganze Funktion. Die Vorwärtsphase erzeugt die Rollenspur, die Endrolle liefert den Startwert \(1\), \(2\) oder \(3\), und die Rückwärtsphase wendet immer wieder dieselbe geschlossene Modulo-\(3\)-Formel an. Genau diese Trennung ist die zentrale Idee der Lösung.
Hier gilt
$$ A=2^3=8,\qquad B=3^2=9,\qquad C=8+9=17. $$
Man startet also mit \((8,9,17)\), also zunächst mit Rolle \(C\). Die Vorwärtsreduktion lautet
$$ (8,9,17)\to(8,9,1)\to(8,7,1)\to(6,7,1)\to(6,5,1)\to(4,5,1)\to(4,3,1)\to(2,3,1)\to(2,1,1). $$
Die zugehörige Rollenspur ist
$$ C,\ B,\ A,\ B,\ A,\ B,\ A,\ B,\ A. $$
Der Endzustand hat die Form \((2g,g,g)\), also beginnt die Rückwärtsrekonstruktion mit dem Wert \(1\). Nun lässt man die letzte Rolle \(A\) weg, kehrt die übrigen Rollen um und erzwingt die Restklassen \(2,1,2,1,2,1,2,0\):
$$ 1\to 2\to 4\to 5\to 7\to 8\to 10\to 11\to 12. $$
Daher folgt
$$ F(8,9,17)=12. $$
Das Beispiel stammt direkt aus einem Summanden der äußeren Summe und zeigt beide Hälften des Verfahrens: Vorwärtsreduktion im Stil des euklidischen Algorithmus und rückwärtige Rekonstruktion über Restklassen.
Die C++-, Python- und Java-Implementierungen durchlaufen alle \(7\cdot 19=133\) Paare \((a,b)\). Für jedes Paar werden \(A=a^b\), \(B=b^a\) und dann \(C=A+B\) berechnet; anschließend wird \(F(A,B,C)\) ausgewertet und zur Gesamtsumme addiert.
Selbst der größte auftretende Wert liegt noch bequem im 64-Bit-Bereich, daher bleibt die gesamte Rechnung reine Ganzzahlarithmetik.
Für ein einzelnes Tripel bestimmt die Implementierung wiederholt, ob die aktuelle Summenrolle von \(A\), \(B\) oder \(C\) getragen wird, hängt diese Rolle an eine kurze Liste an und ersetzt die Summenkoordinate durch die Betragsdifferenz der beiden verbleibenden Werte. Sobald die beiden kleineren Zahlen gleich sind, endet die Schleife, denn dann liegt eine der drei Endformen vor.
Nach dem Abbruch übersetzt die Implementierung die Endrolle in den Basiswert \(1\), \(2\) oder \(3\). Danach liest sie die gespeicherte Spur rückwärts, ohne die terminale Rolle selbst, und springt in jedem Schritt zur nächsten größeren Zahl in der von dieser Rolle verlangten Restklasse. Genau die oben angegebene geschlossene Formel wird dabei angewendet.
Sei \(L(A,B,C)\) die Anzahl der Vorwärtsschritte für ein einzelnes Tripel. Dann kostet die Auswertung dieses Tripels \(O(L(A,B,C))\) Zeit: einmal linear vorwärts über die Spur und danach noch einmal linear rückwärts über dieselbe Spur.
Wenn die Spur explizit gespeichert wird, beträgt der Zusatzspeicher \(O(L(A,B,C))\) für dieses Tripel. Da das vollständige Programm nur 133 Tripel verarbeitet, ist die Gesamtlaufzeit
$$ O\!\left(\sum_{a=1}^{7}\sum_{b=1}^{19} L\!\left(a^b,b^a,a^b+b^a\right)\right), $$
und der Arbeitspeicher liegt bei \(O(L_{\max})\) für die längste Einzelspur. Das ist hier völlig ausreichend, weil der äußere Suchraum klein ist und jeder innere Schritt nur aus Vergleichen, Subtraktion und einer Modulo-\(3\)-Korrektur besteht.
İstenen toplam
$$S=\sum_{a=1}^{7}\sum_{b=1}^{19} F\!\left(a^b,b^a,a^b+b^a\right).$$
Yani her terim şu pozitif üçlüyle başlıyor:
$$ (A,B,C)=\left(a^b,b^a,a^b+b^a\right). $$
Başlangıçta her zaman \(C=A+B\) olduğundan asıl mesele dıştaki çift toplam değil, bir bileşeni diğer ikisinin toplamı olan üçlüler için \(F(A,B,C)\) değerinin nasıl belirlendiğini anlamaktır.
Üç uygulamanın ortak yapısı şudur: Üçlü, çıkarma tabanlı bir Öklid adımıyla küçültülürken o anda hangi koordinatın toplam rolünde olduğu kaydedilir. Bu ileri iz oluşturulduktan sonra \(F\) değeri mod \(3\) kullanan basit bir geri kurma kuralıyla bulunur.
Şu üç ilişkiden tam birini sağlayan herhangi bir pozitif \((A,B,C)\) üçlüsünü ele alalım:
$$A=B+C,\qquad B=A+C,\qquad C=A+B.$$
Tüm sayılar pozitif olduğu için sol taraftaki koordinat otomatik olarak en büyük olandır. İndirgeme adımı tam olarak bu en büyük koordinatı, diğer iki sayının mutlak farkıyla değiştirir.
Eğer mevcut durumda \(C=A+B\) ise bir sonraki durum
$$ (A,B,C)\mapsto (A,B,|A-B|) $$
olur. \(A\ge B\) ise yeni durum \((A,B,A-B)\) olur ve hemen \(A=B+(A-B)\) yazılır. \(B>A\) ise \((A,B,B-A)\) elde edilir ve bu kez \(B=A+(B-A)\) olur. Yani bir adım sonra yine pozitif bir üçlü içindeyiz ve yine bir koordinat diğer ikisinin toplamı durumundadır; sadece bu rolün sahibi değişebilir.
Aynı akıl yürütme döngüsel olarak diğer iki durum için de geçerlidir. Başka bir deyişle süreç, iki küçük sayı üzerinde çalışan çıkarma tabanlı bir Öklid algoritmasıdır; \(A\), \(B\) ve \(C\) etiketleri ise toplamın hangi koordinatta bulunduğunu kaydeder.
İki temel özellik hemen görülür.
Birincisi, ortak bölen korunur. Örneğin \(C=A+B\) iken
$$ \gcd(A,B,C)=\gcd(A,B)=\gcd(A,B,|A-B|) $$
olur; diğer iki durumda da yalnızca etiketler değişir.
İkincisi, küçük iki sayı eşit olmadığı sürece en büyük sayı kesin olarak küçülür. Dolayısıyla süreç mutlaka sonlanır.
Sonlanma tam olarak iki küçük sayı eşit olduğunda gerçekleşir. Bu ortak değer \(g\) ise üçüncü koordinat zorunlu olarak \(2g\) olur. Bu yüzden son durumlar yalnızca
$$ (2g,g,g),\qquad (g,2g,g),\qquad (g,g,2g) $$
biçimleridir; burada \(g=\gcd(A,B,C)\) olur. Ortak çarpan \(g\) sonuna kadar taşınır, fakat uygulamalar \(F\)'nin \(g\)'nin büyüklüğüne değil, yalnızca hangi koordinatın \(2\) katsayısını taşıdığına bağlı olduğunu gösterir.
İleri indirgeme sırasında her adımda \(r_i\in\{A,B,C\}\) biçiminde bir sembol kaydedelim; bu sembol o anda hangi koordinatın diğer ikisinin toplamı olduğunu göstersin. Süreç \(k\) adımda bitiyorsa elimizde
$$ r_1,r_2,\dots,r_k $$
izi vardır ve \(r_k\) aynı zamanda terminal durumun rolüdür. Bu iz bir kez bilindikten sonra ikinci aşamada ara değerlerin kendilerine artık ihtiyaç kalmaz.
Terminal durumlar geri kurmayı şu taban değerlerle başlatır:
$$ F(2g,g,g)=1,\qquad F(g,2g,g)=2,\qquad F(g,g,2g)=3. $$
Geri doğru ilerlemek için
$$ \rho(A)=1,\qquad \rho(B)=2,\qquad \rho(C)=0 $$
artık sınıfı eşlemesini tanımlayalım. Eğer daha sonraki durumun değeri \(t\) ise ve bir önceki rol \(r\) ise, daha erken durumun değeri \(t\)'den büyük olup istenen artık sınıfına düşen en küçük tam sayıdır:
$$ N(t,r)=\min\{n>t:\ n\equiv \rho(r)\pmod 3\}. $$
Yukarıdaki minimizasyon doğrudan hesaplanabilir; arama yapmaya gerek yoktur:
$$ N(t,r)=t+1+\left(\rho(r)-((t+1)\bmod 3)\right)\bmod 3. $$
Böylece tüm fonksiyon için özlü bir yineleme elde edilir. İleri faz rol izini üretir, terminal rol başlangıç değeri olarak \(1\), \(2\) ya da \(3\)'ü seçer, geri faz ise aynı mod \(3\) formülünü tekrar tekrar uygular. Çözümün ana fikri tam olarak bu ayrımdır.
Bu durumda
$$ A=2^3=8,\qquad B=3^2=9,\qquad C=8+9=17. $$
Yani başlangıç üçlüsü \((8,9,17)\) ve ilk rol \(C\)'dir. İleri indirgeme şu şekildedir:
$$ (8,9,17)\to(8,9,1)\to(8,7,1)\to(6,7,1)\to(6,5,1)\to(4,5,1)\to(4,3,1)\to(2,3,1)\to(2,1,1). $$
Buna karşılık gelen rol izi
$$ C,\ B,\ A,\ B,\ A,\ B,\ A,\ B,\ A $$
olur. Son durum \((2g,g,g)\) biçiminde olduğu için geri kurma \(1\) değeriyle başlar. Son \(A\) rolünü attıktan sonra kalanları ters çevirip \(2,1,2,1,2,1,2,0\) artıklarını uygularız:
$$ 1\to 2\to 4\to 5\to 7\to 8\to 10\to 11\to 12. $$
Demek ki
$$ F(8,9,17)=12. $$
Bu örnek dış toplamın gerçek bir teriminden gelir ve algoritmanın iki katmanını açıkça gösterir: önce Öklid benzeri ileri indirgeme, sonra artık sınıfı kısıtlı geri kurma.
C++, Python ve Java uygulamaları tüm \(7\cdot 19=133\) adet \((a,b)\) çiftini dolaşır. Her çift için \(A=a^b\), \(B=b^a\) hesaplanır, ardından \(C=A+B\) kurulur; sonra \(F(A,B,C)\) bulunup toplam sonuca eklenir.
Karşılaşılan en büyük değerler bile rahatça 64 bit aralığında kaldığından hesaplama boyunca tamsayı aritmetiği yeterlidir.
Tek bir üçlü için uygulama, toplam rolünün \(A\), \(B\) veya \(C\) olup olmadığını tekrar tekrar belirler, bu rolü kısa bir listeye ekler ve toplam koordinatını diğer iki değerin mutlak farkıyla değiştirir. Küçük iki sayı eşit olduğu anda döngü biter; çünkü artık üç terminal biçimden birine ulaşılmıştır.
İndirgeme bittikten sonra terminal rol \(1\), \(2\) veya \(3\) başlangıç değerine çevrilir. Ardından saklanan iz, terminal rol hariç ters yönde okunur ve her adımda o rolün istediği artık sınıfındaki bir sonraki daha büyük sayıya sıçranır. Üç uygulama da tam olarak yukarıdaki kapalı formülü uygular.
Bir üçlü için ileri indirgeme adım sayısı \(L(A,B,C)\) olsun. O zaman bu üçlünün hesaplanması \(O(L(A,B,C))\) zamanda gerçekleşir: önce iz boyunca tek bir ileri geçiş, sonra aynı iz üzerinde tek bir geri geçiş.
İz açıkça saklanıyorsa bu üçlü için ek bellek \(O(L(A,B,C))\) olur. Program toplamda yalnızca 133 üçlü değerlendirdiği için toplam süre
$$ O\!\left(\sum_{a=1}^{7}\sum_{b=1}^{19} L\!\left(a^b,b^a,a^b+b^a\right)\right) $$
ve çalışma belleği de en uzun tekil iz için \(O(L_{\max})\) seviyesindedir. Bu problemde bu maliyet fazlasıyla uygundur; çünkü dış uzay küçüktür ve her iç adım sadece karşılaştırma, çıkarma ve mod \(3\) düzeltmesi içerir.
La suma que se debe calcular es
$$S=\sum_{a=1}^{7}\sum_{b=1}^{19} F\!\left(a^b,b^a,a^b+b^a\right).$$
Cada término parte de la terna positiva
$$ (A,B,C)=\left(a^b,b^a,a^b+b^a\right), $$
de modo que al comienzo siempre se cumple \(C=A+B\). Por eso la dificultad real no está en la suma exterior, sino en entender cómo se determina \(F(A,B,C)\) cuando una coordenada es exactamente la suma de las otras dos.
Las tres implementaciones muestran la misma idea. La terna se reduce con un paso euclidiano por restas mientras se registra cuál coordenada está desempeñando el papel de suma. Una vez conocida esa traza hacia delante, el valor de \(F\) se reconstruye hacia atrás mediante una regla muy pequeña módulo \(3\).
Consideremos una terna positiva \((A,B,C)\) que satisfaga exactamente una de las relaciones
$$A=B+C,\qquad B=A+C,\qquad C=A+B.$$
Como todas las entradas son positivas, la coordenada del lado izquierdo es automáticamente la mayor. La regla de reducción reemplaza precisamente esa coordenada mayor por la diferencia absoluta de las otras dos.
Si el estado actual cumple \(C=A+B\), el siguiente estado es
$$ (A,B,C)\mapsto (A,B,|A-B|). $$
Si \(A\ge B\), esto produce \((A,B,A-B)\), y entonces \(A=B+(A-B)\). Si \(B>A\), produce \((A,B,B-A)\), y entonces \(B=A+(B-A)\). Después de un paso seguimos teniendo una terna positiva en la que una coordenada es la suma de las otras dos; lo único que puede cambiar es cuál coordenada ocupa ese papel.
El mismo razonamiento funciona cíclicamente en los otros dos casos. Dicho de otra manera, el proceso es una versión por restas del algoritmo de Euclides aplicada a los dos números menores, mientras las etiquetas \(A\), \(B\) y \(C\) conservan la información sobre dónde está la suma en cada instante.
Hay dos hechos inmediatos.
Primero, el máximo común divisor se conserva. Por ejemplo, cuando \(C=A+B\),
$$ \gcd(A,B,C)=\gcd(A,B)=\gcd(A,B,|A-B|), $$
y la misma identidad vale en los demás casos tras permutar las etiquetas.
Segundo, mientras los dos números menores sean distintos, el mayor disminuye estrictamente. Por tanto, la reducción necesariamente termina.
La detención ocurre exactamente cuando los dos números pequeños se vuelven iguales. Si ambos valen \(g\), la tercera coordenada debe ser \(2g\). En consecuencia, las únicas formas terminales son
$$ (2g,g,g),\qquad (g,2g,g),\qquad (g,g,2g), $$
donde \(g=\gcd(A,B,C)\). La escala \(g\) sobrevive hasta el final, pero las implementaciones muestran que \(F\) no depende del tamaño de \(g\), sino solo de cuál coordenada lleva el factor \(2\).
Durante la reducción hacia delante, registramos un símbolo \(r_i\in\{A,B,C\}\) en cada paso para indicar qué coordenada es en ese momento la suma de las otras dos. Si el proceso termina tras \(k\) pasos, obtenemos la traza
$$ r_1,r_2,\dots,r_k, $$
donde \(r_k\) también es el rol de la forma terminal. Una vez conocida esta traza, los valores intermedios concretos dejan de ser necesarios para la segunda mitad del cálculo.
Las formas terminales fijan la reconstrucción mediante los valores base
$$ F(2g,g,g)=1,\qquad F(g,2g,g)=2,\qquad F(g,g,2g)=3. $$
Para retroceder por la traza, introducimos la aplicación de residuos
$$ \rho(A)=1,\qquad \rho(B)=2,\qquad \rho(C)=0. $$
Si el estado posterior ya tiene valor \(t\) y el rol anterior es \(r\), entonces el estado más antiguo recibe el menor entero mayor que \(t\) y congruente con \(\rho(r)\pmod 3\):
$$ N(t,r)=\min\{n>t:\ n\equiv \rho(r)\pmod 3\}. $$
Esa minimización puede escribirse de manera explícita, sin búsqueda:
$$ N(t,r)=t+1+\left(\rho(r)-((t+1)\bmod 3)\right)\bmod 3. $$
Con ello se obtiene una recurrencia compacta para toda la función. La fase hacia delante produce la traza de roles, el rol terminal selecciona el valor inicial \(1\), \(2\) o \(3\), y la fase hacia atrás aplica repetidamente la misma fórmula módulo \(3\). Esa separación es la idea central de la solución.
En este caso
$$ A=2^3=8,\qquad B=3^2=9,\qquad C=8+9=17. $$
Se empieza entonces en \((8,9,17)\), con rol inicial \(C\). La reducción hacia delante es
$$ (8,9,17)\to(8,9,1)\to(8,7,1)\to(6,7,1)\to(6,5,1)\to(4,5,1)\to(4,3,1)\to(2,3,1)\to(2,1,1). $$
La traza correspondiente es
$$ C,\ B,\ A,\ B,\ A,\ B,\ A,\ B,\ A. $$
El estado terminal tiene la forma \((2g,g,g)\), así que la reconstrucción arranca en \(1\). Se descarta el último rol \(A\), se invierte el resto y se fuerzan los residuos \(2,1,2,1,2,1,2,0\):
$$ 1\to 2\to 4\to 5\to 7\to 8\to 10\to 11\to 12. $$
Por consiguiente,
$$ F(8,9,17)=12. $$
Este ejemplo sale directamente de un sumando real y deja ver con claridad las dos capas del método: la reducción euclidiana hacia delante y la reconstrucción modular hacia atrás.
Las implementaciones en C++, Python y Java recorren los \(7\cdot 19=133\) pares \((a,b)\). Para cada uno calculan \(A=a^b\), \(B=b^a\), forman \(C=A+B\), evalúan \(F(A,B,C)\) y acumulan el resultado en la suma total.
Incluso el mayor valor que aparece sigue cabiendo holgadamente en 64 bits, de modo que todo el cálculo puede hacerse con aritmética entera.
Para una terna concreta, la implementación determina repetidamente si el rol actual es \(A\), \(B\) o \(C\), añade ese rol a una lista corta y sustituye la coordenada suma por la diferencia absoluta de las otras dos. El bucle termina cuando los dos valores menores coinciden, porque en ese momento ya se ha alcanzado una de las tres formas terminales.
Después de detenerse, la implementación transforma el rol terminal en el valor base \(1\), \(2\) o \(3\). Luego recorre la traza almacenada en sentido inverso, excluyendo el rol terminal, y en cada paso salta al siguiente entero mayor que pertenece a la clase residual impuesta por ese rol. Las tres implementaciones aplican exactamente la fórmula cerrada anterior.
Sea \(L(A,B,C)\) el número de pasos de reducción hacia delante para una terna. Entonces evaluar esa terna cuesta \(O(L(A,B,C))\) tiempo: un recorrido lineal para construir la traza y otro recorrido lineal para reproducirla hacia atrás.
Si la traza se almacena explícitamente, la memoria auxiliar es \(O(L(A,B,C))\) para esa terna. Como el programa completo evalúa solo 133 ternas, el tiempo total es
$$ O\!\left(\sum_{a=1}^{7}\sum_{b=1}^{19} L\!\left(a^b,b^a,a^b+b^a\right)\right), $$
mientras que la memoria de trabajo es \(O(L_{\max})\) para la traza individual más larga. En esta tarea eso es más que suficiente, porque el espacio exterior es muy pequeño y cada paso interior usa solo comparaciones, restas y un ajuste módulo \(3\).
要求计算的总和是
$$S=\sum_{a=1}^{7}\sum_{b=1}^{19} F\!\left(a^b,b^a,a^b+b^a\right).$$
因此每一项都从下面这个正整数三元组出发：
$$ (A,B,C)=\left(a^b,b^a,a^b+b^a\right). $$
一开始总有 \(C=A+B\)。所以真正要解决的不是外层 \(7\times 19\) 个组合本身，而是要先弄清楚：当一个正整数三元组中恰有一个坐标等于另外两个坐标之和时，函数 \(F(A,B,C)\) 到底如何确定。
三份实现给出的结构完全一致。先对三元组做一种减法型的欧几里得化简，同时记录当前到底是 \(A\)、\(B\) 还是 \(C\) 在扮演“和项”的角色；等这条前向轨迹确定之后，再用一个模 \(3\) 的规则把答案从终点反推回来。
先研究任意一个满足以下三种关系之一的正整数状态 \((A,B,C)\)：
$$A=B+C,\qquad B=A+C,\qquad C=A+B.$$
因为三个数都为正，所以左边那个量自动是当前最大的量。化简规则就是把这个最大的“和项”替换成另外两个数的绝对差。
如果当前满足 \(C=A+B\)，下一步就变成
$$ (A,B,C)\mapsto (A,B,|A-B|). $$
若 \(A\ge B\)，新状态是 \((A,B,A-B)\)，于是马上得到 \(A=B+(A-B)\)。若 \(B>A\)，新状态是 \((A,B,B-A)\)，于是有 \(B=A+(B-A)\)。也就是说，做完一步之后，三元组仍然保持“有一个坐标等于另外两个之和”的结构，只是这个角色的归属可能从一个坐标换到另一个坐标。
另外两种情形完全可以循环地作同样分析。换句话说，真正发生的事情是：对两个较小的数执行减法版欧几里得算法，而 \(A\)、\(B\)、\(C\) 这三个标签只负责记录在每一时刻谁是和项。
这里有两个立刻可见的重要事实。
第一，最大公因数保持不变。比如在 \(C=A+B\) 的情况下，
$$ \gcd(A,B,C)=\gcd(A,B)=\gcd(A,B,|A-B|), $$
其他两种情形只是标签互换，结论完全相同。
第二，只要两个较小的数还不相等，最大的那个数就会严格减小，因此这个过程不可能无限进行，必定会停下来。
什么时候停止？恰好是在两个较小的数变成相等的时候。若它们都等于 \(g\)，那么第三个数必须是 \(2g\)。所以终止状态只能是下面三种：
$$ (2g,g,g),\qquad (g,2g,g),\qquad (g,g,2g), $$
其中 \(g=\gcd(A,B,C)\)。也就是说，公共因子 \(g\) 会一直保留到最后；不过实现表明，\(F\) 的取值并不依赖这个 \(g\) 的具体大小，而只依赖于到底是哪一个坐标带着那个系数 \(2\)。
在前向化简过程中，每一步都记下一个符号 \(r_i\in\{A,B,C\}\)，表示当前哪一个坐标等于另外两个坐标之和。如果总共走了 \(k\) 步才停下，那么就得到一条轨迹
$$ r_1,r_2,\dots,r_k, $$
其中最后的 \(r_k\) 同时也是终止形态对应的角色。一旦这条轨迹已经知道，第二阶段计算就不再需要那些中间数字本身了。
终止状态给出反向重建的三个基值：
$$ F(2g,g,g)=1,\qquad F(g,2g,g)=2,\qquad F(g,g,2g)=3. $$
为了沿着轨迹向后回推，再引入一个模 \(3\) 的剩余类映射：
$$ \rho(A)=1,\qquad \rho(B)=2,\qquad \rho(C)=0. $$
如果较后的状态已经拥有值 \(t\)，而再往前一步的角色是 \(r\)，那么更早那个状态的值就是所有大于 \(t\) 的整数中，落在 \(\rho(r)\pmod 3\) 这个剩余类里的最小者：
$$ N(t,r)=\min\{n>t:\ n\equiv \rho(r)\pmod 3\}. $$
上面的最小化并不需要试探，直接有闭式公式：
$$ N(t,r)=t+1+\left(\rho(r)-((t+1)\bmod 3)\right)\bmod 3. $$
于是整个函数就被拆成了非常清晰的两部分。前半段负责生成角色轨迹，终止角色决定初始值 \(1\)、\(2\) 或 \(3\)，后半段则不断套用同一个模 \(3\) 公式把答案往前推回去。这个“前向几何化简 + 后向模运算重建”的分离，正是本题解法的核心。
此时
$$ A=2^3=8,\qquad B=3^2=9,\qquad C=8+9=17. $$
所以起点是 \((8,9,17)\)，最初的和项角色是 \(C\)。前向化简过程为
$$ (8,9,17)\to(8,9,1)\to(8,7,1)\to(6,7,1)\to(6,5,1)\to(4,5,1)\to(4,3,1)\to(2,3,1)\to(2,1,1). $$
相应的角色轨迹是
$$ C,\ B,\ A,\ B,\ A,\ B,\ A,\ B,\ A. $$
终点属于 \((2g,g,g)\) 这一类，所以反向重建从数值 \(1\) 开始。去掉最后那个终止角色 \(A\)，把剩下的角色反过来读，并依次强制余数 \(2,1,2,1,2,1,2,0\)：
$$ 1\to 2\to 4\to 5\to 7\to 8\to 10\to 11\to 12. $$
因此得到
$$ F(8,9,17)=12. $$
这个例子直接来自外层求和中的真实一项，也最清楚地展示了算法的两层结构：先做前向减法化简，再做后向剩余类重建。
C++、Python 和 Java 实现都会遍历全部 \(7\cdot 19=133\) 个 \((a,b)\) 组合。对每一组，先计算 \(A=a^b\)、\(B=b^a\)，再形成 \(C=A+B\)，接着求出 \(F(A,B,C)\)，最后把结果加入总和。
出现的最大数仍然远低于 64 位整数上限，因此整个过程都可以保持纯整数运算。
对单个三元组，程序会不断判断当前是 \(A\)、\(B\) 还是 \(C\) 在担当和项，把这个角色压入一个很短的列表，然后把该和项替换为另外两个值的绝对差。一旦两个较小值相等，循环立即停止，因为此时已经到达三种终止形态之一。
停止之后，程序先根据终止角色把起始值设为 \(1\)、\(2\) 或 \(3\)。然后按逆序扫描刚才保存的轨迹，去掉最后那个终止角色，并在每一步跳到该角色所要求剩余类中的下一个更大整数。三份实现执行的正是上面的闭式公式。
设某个三元组的前向化简步数为 \(L(A,B,C)\)。那么求这个三元组的代价就是 \(O(L(A,B,C))\) 时间：一次线性前向扫描生成轨迹，再加一次线性反向扫描完成重建。
如果轨迹显式保存下来，那么该三元组的额外空间也是 \(O(L(A,B,C))\)。由于完整程序总共只处理 133 个三元组，总时间可以写成
$$ O\!\left(\sum_{a=1}^{7}\sum_{b=1}^{19} L\!\left(a^b,b^a,a^b+b^a\right)\right), $$
而工作内存是最长那条轨迹对应的 \(O(L_{\max})\)。对于本题来说这完全足够，因为外层枚举很小，内层每一步又只是比较、减法和一次模 \(3\) 调整。
Требуется вычислить сумму
$$S=\sum_{a=1}^{7}\sum_{b=1}^{19} F\!\left(a^b,b^a,a^b+b^a\right).$$
Каждое слагаемое начинается с положительной тройки
$$ (A,B,C)=\left(a^b,b^a,a^b+b^a\right), $$
поэтому в начальном состоянии всегда выполнено \(C=A+B\). Значит, главная математическая часть задачи состоит не во внешнем двойном суммировании, а в понимании того, как определяется \(F(A,B,C)\) для троек, где одна координата равна сумме двух других.
Все три реализации используют одну и ту же схему. Тройка последовательно уменьшается вычитательной версией алгоритма Евклида, при этом запоминается, какая координата в данный момент играет роль суммы. После того как эта прямая трасса построена, значение \(F\) восстанавливается назад по простой модульной формуле modulo \(3\).
Рассмотрим произвольную положительную тройку \((A,B,C)\), для которой выполнено ровно одно из соотношений
$$A=B+C,\qquad B=A+C,\qquad C=A+B.$$
Так как все числа положительны, левая часть автоматически является наибольшей координатой. Шаг редукции заменяет именно эту наибольшую координату абсолютной разностью двух остальных.
Если текущее состояние удовлетворяет \(C=A+B\), то следующий шаг имеет вид
$$ (A,B,C)\mapsto (A,B,|A-B|). $$
Когда \(A\ge B\), получаем \((A,B,A-B)\), а значит \(A=B+(A-B)\). Когда \(B>A\), получаем \((A,B,B-A)\), а значит \(B=A+(B-A)\). Следовательно, после одного шага мы снова имеем положительную тройку того же типа; меняется только то, какая именно координата выполняет роль суммы.
Тот же аргумент циклически работает и в двух остальных случаях. Иначе говоря, на двух меньших числах выполняется вычитательный алгоритм Евклида, а метки \(A\), \(B\), \(C\) лишь фиксируют, где в каждый момент находится сумма.
Сразу видны два ключевых свойства.
Во-первых, сохраняется наибольший общий делитель. Например, при \(C=A+B\)
$$ \gcd(A,B,C)=\gcd(A,B)=\gcd(A,B,|A-B|), $$
и после переименования координат та же формула верна в остальных случаях.
Во-вторых, пока два меньших числа различны, наибольшая координата строго убывает. Поэтому процесс обязательно закончится.
Остановка наступает ровно тогда, когда два меньших числа становятся равными. Если оба они равны \(g\), то третья координата обязана быть \(2g\). Значит, возможны только три терминальные формы
$$ (2g,g,g),\qquad (g,2g,g),\qquad (g,g,2g), $$
где \(g=\gcd(A,B,C)\). Общий множитель \(g\) доживает до конца процесса, но реализации показывают, что значение \(F\) зависит не от величины \(g\), а только от того, какая координата несёт коэффициент \(2\).
На каждом шаге прямой редукции записывается символ \(r_i\in\{A,B,C\}\), обозначающий, какая координата сейчас равна сумме двух других. Если редукция завершилась за \(k\) шагов, получается трасса
$$ r_1,r_2,\dots,r_k, $$
где \(r_k\) одновременно является ролью терминальной формы. После того как эта трасса известна, сами промежуточные числа для второй половины вычисления уже не нужны.
Терминальные формы задают базовые значения
$$ F(2g,g,g)=1,\qquad F(g,2g,g)=2,\qquad F(g,g,2g)=3. $$
Для обратного прохода вводится отображение классов вычетов
$$ \rho(A)=1,\qquad \rho(B)=2,\qquad \rho(C)=0. $$
Если более позднее состояние уже имеет значение \(t\), а более ранняя роль равна \(r\), то предыдущее состояние получает наименьшее целое число, большее \(t\), принадлежащее классу \(\rho(r)\pmod 3\):
$$ N(t,r)=\min\{n>t:\ n\equiv \rho(r)\pmod 3\}. $$
Эту минимизацию можно записать сразу в явном виде, без перебора:
$$ N(t,r)=t+1+\left(\rho(r)-((t+1)\bmod 3)\right)\bmod 3. $$
Тем самым вся функция разбивается на две отчётливые стадии. Прямая стадия строит трассу ролей, терминальная роль выбирает стартовое значение \(1\), \(2\) или \(3\), а обратная стадия многократно применяет одну и ту же модульную формулу. Именно это разделение и составляет основную идею решения.
Здесь
$$ A=2^3=8,\qquad B=3^2=9,\qquad C=8+9=17. $$
Стартовая тройка равна \((8,9,17)\), и первая роль - это \(C\). Прямая редукция имеет вид
$$ (8,9,17)\to(8,9,1)\to(8,7,1)\to(6,7,1)\to(6,5,1)\to(4,5,1)\to(4,3,1)\to(2,3,1)\to(2,1,1). $$
Соответствующая трасса ролей:
$$ C,\ B,\ A,\ B,\ A,\ B,\ A,\ B,\ A. $$
Финальное состояние имеет вид \((2g,g,g)\), поэтому обратное восстановление начинается с \(1\). Затем последняя роль \(A\) отбрасывается, оставшиеся роли читаются в обратном порядке, и последовательно навязываются вычеты \(2,1,2,1,2,1,2,0\):
$$ 1\to 2\to 4\to 5\to 7\to 8\to 10\to 11\to 12. $$
Следовательно,
$$ F(8,9,17)=12. $$
Этот пример взят прямо из реального слагаемого внешней суммы и хорошо показывает обе части метода: прямую евклидову редукцию и обратное восстановление по классам вычетов.
Реализации на C++, Python и Java перебирают все \(7\cdot 19=133\) пар \((a,b)\). Для каждой пары вычисляются \(A=a^b\), \(B=b^a\), затем формируется \(C=A+B\), после чего находится \(F(A,B,C)\), и результат добавляется к общей сумме.
Даже наибольшее встречающееся число уверенно помещается в 64-битный диапазон, поэтому всё вычисление остаётся чисто целочисленным.
Для одной тройки программа многократно определяет, принадлежит ли текущая роль координате \(A\), \(B\) или \(C\), добавляет эту роль в короткий список и заменяет координату-сумму абсолютной разностью двух остальных значений. Цикл завершается сразу, как только два меньших числа становятся равными, потому что это означает достижение одной из трёх терминальных форм.
После остановки терминальная роль переводится в базовое значение \(1\), \(2\) или \(3\). Затем сохранённая трасса просматривается в обратном порядке без последней терминальной роли, и на каждом шаге выбирается следующее большее число в классе вычетов, предписанном соответствующей ролью. Именно эту замкнутую формулу используют все три реализации.
Пусть \(L(A,B,C)\) обозначает число шагов прямой редукции для одной тройки. Тогда вычисление этой тройки требует \(O(L(A,B,C))\) времени: один линейный проход для построения трассы и ещё один линейный проход для её обратного воспроизведения.
Если трасса хранится явно, дополнительная память для такой тройки равна \(O(L(A,B,C))\). Так как полная программа рассматривает только 133 тройки, суммарное время равно
$$ O\!\left(\sum_{a=1}^{7}\sum_{b=1}^{19} L\!\left(a^b,b^a,a^b+b^a\right)\right), $$
а рабочая память составляет \(O(L_{\max})\) для самой длинной отдельной трассы. Для этой задачи этого более чем достаточно: внешний перебор мал, а внутренний шаг состоит лишь из сравнений, вычитания и поправки modulo \(3\).
المطلوب حساب المجموع
$$S=\sum_{a=1}^{7}\sum_{b=1}^{19} F\!\left(a^b,b^a,a^b+b^a\right).$$
وكل حد في هذا المجموع يبدأ من الثلاثية الموجبة
$$ (A,B,C)=\left(a^b,b^a,a^b+b^a\right). $$
لذلك تكون العلاقة الابتدائية دائمًا \(C=A+B\). ومن ثم فلب المسألة ليس المجموع الخارجي نفسه، بل فهم كيفية تحديد \(F(A,B,C)\) عندما يكون أحد الإحداثيات مساويًا لمجموع الإحداثيين الآخرين.
توضح التطبيقات الثلاثة البنية نفسها تمامًا. إذ تُختزل الثلاثية بخطوة تشبه خوارزمية إقليدس القائمة على الطرح، مع تسجيل أي إحداثي يحمل دور المجموع في كل مرحلة. وبعد بناء هذا المسار الأمامي، يُعاد تكوين قيمة \(F\) عكسيًا بقاعدة صغيرة تعتمد على البواقي modulo \(3\).
لننظر إلى أي ثلاثية موجبة \((A,B,C)\) تحقق واحدة فقط من العلاقات
$$A=B+C,\qquad B=A+C,\qquad C=A+B.$$
وبما أن جميع القيم موجبة، فإن الطرف الأيسر يكون تلقائيًا هو الأكبر. وقاعدة الاختزال تستبدل هذا الحد الأكبر تحديدًا بالفارق المطلق بين الحدين الآخرين.
إذا كانت الحالة الحالية تحقق \(C=A+B\)، فإن الخطوة التالية هي
$$ (A,B,C)\mapsto (A,B,|A-B|). $$
فإذا كان \(A\ge B\)، نحصل على \((A,B,A-B)\)، وعندئذ تصبح العلاقة \(A=B+(A-B)\). وإذا كان \(B>A\)، نحصل على \((A,B,B-A)\)، وعندئذ تكون العلاقة \(B=A+(B-A)\). أي إننا بعد خطوة واحدة نبقى داخل فضاء ثلاثيات موجبة من النوع نفسه، لكن قد ينتقل دور المجموع من إحداثي إلى آخر.
والبرهان نفسه يعمل بصورة دورية في الحالتين الأخريين. وبصياغة أخرى: ما يجري فعليًا هو خوارزمية إقليدس بالطرح على العددين الأصغر، بينما تحفظ التسميات \(A\) و\(B\) و\(C\) موضع المجموع في كل لحظة.
هناك حقيقتان مهمتان تظهران مباشرة.
الأولى أن القاسم المشترك الأكبر يبقى محفوظًا. ففي حالة \(C=A+B\) مثلًا، لدينا
$$ \gcd(A,B,C)=\gcd(A,B)=\gcd(A,B,|A-B|), $$
وبعد إعادة تسمية الإحداثيات نحصل على الصيغة نفسها في الحالتين الأخريين.
والثانية أن أكبر عدد يتناقص تناقصًا صارمًا ما دامت القيمتان الأصغر غير متساويتين. ولهذا لا يمكن أن تستمر العملية بلا نهاية، بل لا بد أن تنتهي.
ومتى تنتهي؟ تنتهي بالضبط عندما تتساوى القيمتان الأصغر. فإذا كانتا كلتاهما تساويان \(g\)، فلا بد أن يكون الإحداثي الثالث مساويًا لـ \(2g\). إذن الحالات النهائية الوحيدة هي
$$ (2g,g,g),\qquad (g,2g,g),\qquad (g,g,2g), $$
حيث \(g=\gcd(A,B,C)\). أي إن العامل المشترك \(g\) يبقى حتى النهاية، لكن التطبيقات تبين أن \(F\) لا تعتمد على مقدار \(g\) نفسه، بل على أي إحداثي يحمل المعامل \(2\).
أثناء الاختزال الأمامي نسجل في كل خطوة رمزًا \(r_i\in\{A,B,C\}\) يحدد أي إحداثي يساوي مجموع الإحداثيين الآخرين في تلك اللحظة. وإذا انتهت العملية بعد \(k\) خطوات، نحصل على المسار
$$ r_1,r_2,\dots,r_k, $$
حيث يكون \(r_k\) هو أيضًا دور الحالة النهائية. وبعد معرفة هذا المسار، لا نعود بحاجة إلى القيم الوسيطة نفسها في النصف الثاني من الحساب.
الحالات النهائية تثبت نقطة البداية لإعادة البناء عبر القيم الأساسية
$$ F(2g,g,g)=1,\qquad F(g,2g,g)=2,\qquad F(g,g,2g)=3. $$
وللرجوع عكسيًا على طول المسار نعرّف خريطة البواقي
$$ \rho(A)=1,\qquad \rho(B)=2,\qquad \rho(C)=0. $$
فإذا كانت الحالة اللاحقة قد حصلت بالفعل على القيمة \(t\)، وكان الدور الأسبق هو \(r\)، فإن الحالة السابقة يجب أن تأخذ أصغر عدد صحيح أكبر من \(t\) وينتمي إلى فئة الباقي \(\rho(r)\pmod 3\):
$$ N(t,r)=\min\{n>t:\ n\equiv \rho(r)\pmod 3\}. $$
يمكن كتابة هذه القيمة الدنيا مباشرة من غير أي بحث:
$$ N(t,r)=t+1+\left(\rho(r)-((t+1)\bmod 3)\right)\bmod 3. $$
وهكذا تنقسم الدالة كلها إلى مرحلتين واضحتين. المرحلة الأمامية تبني مسار الأدوار، والدور النهائي يحدد قيمة البداية \(1\) أو \(2\) أو \(3\)، ثم تأتي المرحلة العكسية فتطبق الصيغة نفسها modulo \(3\) مرارًا. وهذا الفصل بين الاختزال العددي في الأمام وإعادة البناء بالمخلفات في الخلف هو الفكرة المحورية للحل.
في هذه الحالة
$$ A=2^3=8,\qquad B=3^2=9,\qquad C=8+9=17. $$
إذًا نقطة البداية هي \((8,9,17)\)، ويكون الدور الأول هو \(C\). أما الاختزال الأمامي فيسير كما يلي:
$$ (8,9,17)\to(8,9,1)\to(8,7,1)\to(6,7,1)\to(6,5,1)\to(4,5,1)\to(4,3,1)\to(2,3,1)\to(2,1,1). $$
ومن ثم يكون مسار الأدوار
$$ C,\ B,\ A,\ B,\ A,\ B,\ A,\ B,\ A. $$
الحالة النهائية من النوع \((2g,g,g)\)، لذلك تبدأ إعادة البناء من القيمة \(1\). نحذف الدور الأخير \(A\)، ثم نعكس بقية الأدوار، ونفرض البواقي \(2,1,2,1,2,1,2,0\) بالتتابع:
$$ 1\to 2\to 4\to 5\to 7\to 8\to 10\to 11\to 12. $$
وعليه نحصل على
$$ F(8,9,17)=12. $$
وهذا المثال مأخوذ مباشرة من حد فعلي في المجموع الخارجي، ويُظهر بوضوح طبقتي الخوارزمية: اختزالًا أماميًا شبيهًا بإقليدس، ثم إعادة بناء عكسية عبر فئات البواقي.
تجتاز تطبيقات C++ وPython وJava جميع الأزواج \((a,b)\) وعددها \(7\cdot 19=133\). ولكل زوج تُحسب \(A=a^b\) و\(B=b^a\)، ثم تُبنى \(C=A+B\)، وبعد ذلك تُقيَّم \(F(A,B,C)\) وتُضاف النتيجة إلى المجموع الكلي.
حتى أكبر قيمة تظهر في الحساب تبقى ضمن مجال 64 بت براحة، لذلك تستطيع التطبيقات الاعتماد على الحساب الصحيح بالكامل.
بالنسبة إلى ثلاثية واحدة، تحدد الشيفرة مرارًا ما إذا كان الدور الحالي هو \(A\) أو \(B\) أو \(C\)، ثم تضيف هذا الدور إلى قائمة قصيرة، وتستبدل إحداثي المجموع بالفارق المطلق بين القيمتين الأخريين. وتتوقف الحلقة حالما تتساوى القيمتان الأصغر، لأن الحالة تكون قد وصلت عندئذ إلى إحدى الصور النهائية الثلاث.
بعد التوقف، يُحوَّل الدور النهائي إلى القيمة الأساسية \(1\) أو \(2\) أو \(3\). ثم تُقرأ الأدوار المخزنة في الاتجاه المعاكس بعد حذف الدور النهائي نفسه، وفي كل خطوة تُختار القيمة الأكبر التالية الواقعة في فئة الباقي التي يفرضها ذلك الدور. هذا هو بالضبط ما تنفذه التطبيقات الثلاثة باستخدام الصيغة المغلقة السابقة.
إذا رمزنا بعدد خطوات الاختزال الأمامي لثلاثية واحدة بالرمز \(L(A,B,C)\)، فإن تقييم هذه الثلاثية يحتاج إلى زمن \(O(L(A,B,C))\): مرور خطي لبناء المسار، ثم مرور خطي آخر لإعادة بنائه عكسيًا.
وإذا خُزن المسار صراحة، فإن الذاكرة المساعدة لتلك الثلاثية تكون \(O(L(A,B,C))\). وبما أن البرنامج الكامل يتعامل مع 133 ثلاثية فقط، فإن الزمن الكلي يساوي
$$ O\!\left(\sum_{a=1}^{7}\sum_{b=1}^{19} L\!\left(a^b,b^a,a^b+b^a\right)\right), $$
أما الذاكرة العاملة فهي \(O(L_{\max})\) بالنسبة إلى أطول مسار منفرد. وهذا أكثر من كاف هنا، لأن مجال البحث الخارجي صغير جدًا، وكل خطوة داخلية ليست إلا مقارنات وطرحًا وتصحيحًا modulo \(3\).