For each ordered pair \((a,b)\) with \(2 \le a,b \le 223\) and \(a \ne b\), define the generalized Kolakoski sequence \(K_{a,b}=x_1,x_2,\dots\) on the alphabet \(\{a,b\}\). The first term is \(x_1=a\), the symbols in the runs alternate \(a,b,a,b,\dots\), and the run lengths are the sequence itself. The task is to compute
$$T(a,b;N)=\sum_{i=1}^{N} x_i$$
at the huge index \(N=22332223332233\), then sum \(T(a,b;N)\) over all ordered pairs and report the result modulo \(2233222333\).
A direct construction of the first \(N\) terms is completely infeasible. The solution works because the sequence is self-describing: one level of the sequence tells us how many blocks appear at the next level. The implementations exploit that recursive structure by evaluating large blocks and memoizing complete block summaries.
The central idea is to stop thinking term-by-term and instead summarize recursively generated blocks. For this problem, the right mathematical objects are the run decomposition of \(K_{a,b}\), prefix counts of \(a\) and \(b\), and a state transition that remembers where the alternating run mechanism is currently positioned.
Write \(K_{a,b}=x_1,x_2,\dots\), where every \(x_i\) is either \(a\) or \(b\). By definition, the sequence decomposes into maximal runs as
$$K_{a,b}= \underbrace{a\cdots a}_{x_1} \underbrace{b\cdots b}_{x_2} \underbrace{a\cdots a}_{x_3} \underbrace{b\cdots b}_{x_4}\cdots.$$
So the same symbols play two roles. At the top level they are the values of the sequence, and at the same time they dictate the lengths of the alternating runs. That is the self-describing feature behind the whole algorithm.
Let \(A_{a,b}(n)\) be the number of \(a\)'s among the first \(n\) terms, and let \(B_{a,b}(n)\) be the number of \(b\)'s. Then
$$A_{a,b}(n)+B_{a,b}(n)=n,$$
and the weighted prefix sum we need is
$$T(a,b;n)=a\,A_{a,b}(n)+b\,B_{a,b}(n).$$
Therefore the computational problem is not “generate the whole prefix and add it up”; it is “count how many \(a\)'s and \(b\)'s occur in a huge self-referential prefix.” Once those counts are known, \(T(a,b;n)\) follows immediately.
A depth-0 block is one maximal run. Depending on the current state, it emits either \(a\) or \(b\) copies of the current symbol. A depth-1 block is a concatenation of \(a\) or \(b\) depth-0 blocks. More generally, a depth-\(d\) block is a concatenation of \(a\) or \(b\) depth-\((d-1)\) blocks.
For a state \(s\), let
$$F_d(s;n)=\bigl(\alpha_d(s;n),\beta_d(s;n),\nu_d(s;n)\bigr)$$
denote the summary of the first \(n\) emitted terms of a depth-\(d\) block: \(\alpha_d\) is the number of \(a\)'s produced, \(\beta_d\) is the number of \(b\)'s produced, and \(\nu_d\) is the next state after that prefix. When the whole block is taken, we simply write \(F_d(s)\).
If \(\lambda_d(s)\in\{a,b\}\) is the number of children at depth \(d\), and \(s_1,s_2,\dots\) are the successive child states, then the full block length satisfies
$$L_0(s)=\lambda_0(s),\qquad L_d(s)=\sum_{j=1}^{\lambda_d(s)} L_{d-1}(s_j).$$
The symbol counts obey the same additive rule:
$$\alpha_d(s)=\sum_{j=1}^{\lambda_d(s)} \alpha_{d-1}(s_j),\qquad \beta_d(s)=\sum_{j=1}^{\lambda_d(s)} \beta_{d-1}(s_j).$$
If a requested prefix ends in the middle of the last child, only that last child has to be evaluated partially; all earlier children are complete blocks. This is exactly the recurrence used by the implementations.
The recursive formulas need a compact way to say what kind of block comes next. The implementation state is a bit vector with a clear invariant. Its least significant bit tells us whether the next emitted symbol at the base level is \(a\) or \(b\). For each recursion level \(r \ge 0\), the bit in position \(r+1\) tells us whether the currently active multiplicity at that level is \(a\) or \(b\).
Mathematically, that state records the frontier of all open recursion levels. Once the state \(s\) and the depth \(d\) are fixed, the entire full block is determined: how many \(a\)'s it produces, how many \(b\)'s it produces, and what the next state is after the block closes. This is why a full block summary depends only on \((s,d)\), which makes memoization correct.
Because \(a,b \ge 2\), every block has at least 2 children. Hence full block lengths grow at least exponentially:
$$L_d(s)\ge 2^{d+1}.$$
So some depth \(d=O(\log N)\) must eventually produce a block long enough to cover the first \(N\) terms. The implementations simply increase the depth until the block beginning from the initial state is long enough, then extract the desired prefix from that block.
For \((a,b)=(2,3)\), the sequence begins
$$K_{2,3}=2,2,3,3,2,2,2,3,3,3,\dots$$
Grouping into runs gives
$$22\;33\;222\;333\;\cdots,$$
so the run lengths are again \(2,2,3,3,\dots\), exactly the sequence itself. In the first 10 terms there are five 2's and five 3's, therefore
$$T(2,3;10)=5\cdot 2+5\cdot 3=25.$$
This concrete case appears in the validation logic and is a useful miniature model of the full computation.
Once one pair \((a,b)\) has been handled, the Project Euler quantity is
$$S(N)=\sum_{\substack{2\le a,b\le 223\\ a\ne b}} T(a,b;N)\pmod{2233222333},\qquad N=22332223332233.$$
There are \(222 \times 221 = 49062\) ordered pairs. They are independent, so the same mathematical evaluator can be reused for every pair and the contributions can then be added modulo \(2233222333\).
For fixed \(a\) and \(b\), the C++, Python, and Java implementations create a block evaluator for \(K_{a,b}\). They test increasing recursion depths until the initial block is long enough to cover \(N\). The returned summary already contains the counts of \(a\) and \(b\) needed for the formula \(T(a,b;N)=aA+bB\).
The cache key is the pair “state plus depth”. Each cached entry stores three quantities: the total number of \(a\)'s in the full block, the total number of \(b\)'s in the full block, and the next state after that block ends. A cached entry can be reused only when the remaining prefix budget is large enough to include the whole block. If the budget cuts through the block, the evaluator descends recursively, because a truncated final child changes both the counts and the next state.
After one pair is evaluated, the implementation converts symbol counts into a weighted prefix sum and adds that contribution modulo \(2233222333\). The C++ and Java implementations distribute different \(a\)-values across worker threads, while the Python implementation performs the same pair loop serially. The mathematical core is identical in all three languages.
For a fixed pair \((a,b)\), the running time is controlled by the number of distinct full block states that are actually reached, not by the raw prefix length \(N\). If that number is denoted by \(M_{a,b}\), then the memory usage is \(O(M_{a,b})\), because each reachable memo entry stores one full block summary.
The work attached to each memo entry is bounded by the number of child blocks it needs to inspect, which is at most \(\max(a,b)\le 223\). So a natural description is \(O(\max(a,b)\,M_{a,b})\) time per ordered pair and \(O(M_{a,b})\) memory. The full Euler computation repeats that process for 49062 ordered pairs and accumulates the results modulo \(2233222333\). The essential point is that the algorithm scales with the reachable recursive state space, not with \(N=22332223332233\) itself.
Für jedes geordnete Paar \((a,b)\) mit \(2 \le a,b \le 223\) und \(a \ne b\) wird die verallgemeinerte Kolakoski-Folge \(K_{a,b}=x_1,x_2,\dots\) über dem Alphabet \(\{a,b\}\) betrachtet. Es gilt \(x_1=a\), die Run-Symbole wechseln als \(a,b,a,b,\dots\), und die Run-Längen sind wieder genau die Folgenglieder selbst. Gesucht ist
$$T(a,b;N)=\sum_{i=1}^{N} x_i$$
für den sehr großen Index \(N=22332223332233\); anschließend wird über alle geordneten Paare summiert und das Ergebnis modulo \(2233222333\) ausgegeben.
Ein direktes Erzeugen der ersten \(N\) Glieder ist unmöglich. Die Lösung nutzt deshalb die Selbstbeschreibung der Folge: Eine Ebene der Folge sagt uns, wie viele Blöcke auf der nächsttieferen Ebene erzeugt werden. Die Implementierungen werten also große rekursive Blöcke aus und speichern vollständige Blockzusammenfassungen zwischen.
Der entscheidende Schritt ist, nicht einzelne Terme zu simulieren, sondern rekursiv erzeugte Blöcke zu beschreiben. Für dieses Problem sind die richtigen mathematischen Objekte die Run-Zerlegung von \(K_{a,b}\), die Präfixanzahlen von \(a\) und \(b\) sowie ein Zustandsübergang, der festhält, an welcher Stelle des alternierenden Run-Mechanismus wir gerade stehen.
Schreibe \(K_{a,b}=x_1,x_2,\dots\) mit \(x_i\in\{a,b\}\). Per Definition zerfällt die Folge in maximale Runs der Form
$$K_{a,b}= \underbrace{a\cdots a}_{x_1} \underbrace{b\cdots b}_{x_2} \underbrace{a\cdots a}_{x_3} \underbrace{b\cdots b}_{x_4}\cdots.$$
Die gleichen Symbole spielen also zwei Rollen gleichzeitig: Als Folgenglieder sind sie Werte, und gleichzeitig legen sie die Längen der alternierenden Runs fest. Genau diese Selbstreferenz macht den rekursiven Zugriff möglich.
Sei \(A_{a,b}(n)\) die Anzahl der \(a\)-Symbole in den ersten \(n\) Gliedern und \(B_{a,b}(n)\) die Anzahl der \(b\)-Symbole. Dann gilt
$$A_{a,b}(n)+B_{a,b}(n)=n,$$
und die gesuchte gewichtete Präfixsumme ist
$$T(a,b;n)=a\,A_{a,b}(n)+b\,B_{a,b}(n).$$
Damit reduziert sich die Aufgabe auf das Zählen von \(a\)- und \(b\)-Symbolen in einem riesigen selbstreferenziellen Präfix. Ist diese Zählung bekannt, folgt \(T(a,b;n)\) sofort.
Ein Tiefe-0-Block ist genau ein maximaler Run. Abhängig vom aktuellen Zustand erzeugt er entweder \(a\) oder \(b\) Kopien des aktuellen Symbols. Ein Tiefe-1-Block ist eine Verkettung von \(a\) oder \(b\) Tiefe-0-Blöcken. Allgemein ist ein Tiefe-\(d\)-Block eine Verkettung von \(a\) oder \(b\) Tiefe-\((d-1)\)-Blöcken.
Für einen Zustand \(s\) sei
$$F_d(s;n)=\bigl(\alpha_d(s;n),\beta_d(s;n),\nu_d(s;n)\bigr)$$
die Zusammenfassung der ersten \(n\) ausgegebenen Symbole eines Tiefe-\(d\)-Blocks: \(\alpha_d\) zählt die erzeugten \(a\)'s, \(\beta_d\) die erzeugten \(b\)'s, und \(\nu_d\) ist der Folgezustand nach diesem Präfix. Für einen vollständigen Block schreiben wir kurz \(F_d(s)\).
Ist \(\lambda_d(s)\in\{a,b\}\) die Kinderzahl auf Ebene \(d\) und sind \(s_1,s_2,\dots\) die nacheinander auftretenden Kinderzustände, dann erfüllt die vollständige Blocklänge
$$L_0(s)=\lambda_0(s),\qquad L_d(s)=\sum_{j=1}^{\lambda_d(s)} L_{d-1}(s_j).$$
Die Symbolzahlen erfüllen dieselbe additive Rekursion:
$$\alpha_d(s)=\sum_{j=1}^{\lambda_d(s)} \alpha_{d-1}(s_j),\qquad \beta_d(s)=\sum_{j=1}^{\lambda_d(s)} \beta_{d-1}(s_j).$$
Wenn das verlangte Präfix mitten im letzten Kind endet, muss nur dieses letzte Kind teilweise ausgewertet werden; alle vorherigen Kinder sind vollständige Blöcke. Genau das spiegelt die Rekursion im Code wider.
Die Rekursion braucht eine kompakte Beschreibung dafür, welcher Block als Nächstes kommt. Der Zustand ist im Code als Bitvektor kodiert. Das niederwertigste Bit sagt, ob auf der Basisebene als nächstes \(a\) oder \(b\) ausgegeben wird. Für jede Rekursionsebene \(r \ge 0\) speichert das Bit an Position \(r+1\), ob die aktuell aktive Multiplizität auf dieser Ebene \(a\) oder \(b\) ist.
Mathematisch speichert der Zustand also die gesamte Front aller offenen Rekursionsebenen. Sobald \(s\) und \(d\) feststehen, ist der vollständige Block eindeutig bestimmt: Wie viele \(a\)'s entstehen, wie viele \(b\)'s entstehen und in welchem Zustand der nächste Geschwisterblock beginnt. Daher hängt eine vollständige Blockzusammenfassung nur von \((s,d)\) ab, und genau deshalb ist Memoisierung hier korrekt.
Weil \(a,b \ge 2\) gilt, besitzt jeder Block mindestens 2 Kinder. Also wachsen die vollständigen Blocklängen mindestens exponentiell:
$$L_d(s)\ge 2^{d+1}.$$
Folglich gibt es für jedes feste \(N\) eine Tiefe \(d=O(\log N)\), deren Startblock bereits lang genug ist, um die ersten \(N\) Glieder zu überdecken. Die Implementierungen erhöhen die Tiefe daher schlicht so lange, bis dieser Fall eintritt, und extrahieren dann das gewünschte Präfix aus diesem ausreichend großen Block.
Für \((a,b)=(2,3)\) beginnt die Folge mit
$$K_{2,3}=2,2,3,3,2,2,2,3,3,3,\dots$$
Als Runs geschrieben ist das
$$22\;33\;222\;333\;\cdots,$$
und die Run-Längen sind wieder \(2,2,3,3,\dots\), also erneut die Folge selbst. Unter den ersten 10 Gliedern gibt es fünf 2en und fünf 3en, also
$$T(2,3;10)=5\cdot 2+5\cdot 3=25.$$
Dieser Fall wird in den Implementierungen ausdrücklich als Validierung verwendet und illustriert das Gesamtverfahren im Kleinen.
Ist ein Paar \((a,b)\) ausgewertet, dann verlangt die Aufgabe insgesamt
$$S(N)=\sum_{\substack{2\le a,b\le 223\\ a\ne b}} T(a,b;N)\pmod{2233222333},\qquad N=22332223332233.$$
Es gibt \(222 \times 221 = 49062\) geordnete Paare. Sie sind mathematisch unabhängig, daher kann derselbe Auswerter für jedes Paar wiederverwendet und die Beiträge anschließend modulo \(2233222333\) addiert werden.
Für feste Werte \(a\) und \(b\) erzeugen die C++-, Python- und Java-Implementierungen einen Blockauswerter für \(K_{a,b}\). Die Rekursionstiefe wird schrittweise erhöht, bis der Startblock lang genug ist, um \(N\) zu überdecken. Die zurückgegebene Zusammenfassung enthält bereits die beiden Symbolzahlen, die für \(T(a,b;N)=aA+bB\) benötigt werden.
Der Cache-Schlüssel besteht aus „Zustand plus Tiefe“. Jeder gespeicherte Eintrag enthält drei Größen: die Gesamtzahl der \(a\)'s im vollständigen Block, die Gesamtzahl der \(b\)'s und den Folgezustand nach Ende des Blocks. Wiederverwendet werden darf ein Cache-Eintrag nur dann, wenn das verbleibende Budget groß genug ist, um den ganzen Block aufzunehmen. Schneidet das Budget den Block ab, muss rekursiv tiefer gegangen werden, denn ein abgeschnittener letzter Kindblock ändert sowohl die Symbolzahlen als auch den Folgezustand.
Nach der Auswertung eines Paars werden die Symbolzahlen in die gewichtete Präfixsumme umgerechnet und der Beitrag modulo \(2233222333\) addiert. Die C++- und Java-Implementierungen verteilen verschiedene \(a\)-Werte auf mehrere Threads; die Python-Implementierung durchläuft dieselbe Paarschleife seriell. Der mathematische Kern ist in allen drei Sprachen identisch.
Für ein festes Paar \((a,b)\) wird die Laufzeit nicht durch die rohe Präfixlänge \(N\) bestimmt, sondern durch die Zahl der tatsächlich erreichten vollständigen Blockzustände. Nennt man diese Zahl \(M_{a,b}\), dann ist der Speicherbedarf \(O(M_{a,b})\), weil jeder erreichte Memo-Eintrag genau eine vollständige Blockzusammenfassung speichert.
Die Arbeit pro Memo-Eintrag ist durch die Anzahl der betrachteten Kinder begrenzt, also höchstens durch \(\max(a,b)\le 223\). Eine sinnvolle Beschreibung lautet daher \(O(\max(a,b)\,M_{a,b})\) Zeit pro geordnetem Paar und \(O(M_{a,b})\) Speicher. Die vollständige Euler-Rechnung wiederholt diesen Prozess für 49062 geordnete Paare und akkumuliert die Ergebnisse modulo \(2233222333\). Der entscheidende Punkt ist: Die Methode skaliert mit dem erreichbaren rekursiven Zustandsraum und nicht mit \(N=22332223332233\) selbst.
Her sıralı \((a,b)\) çifti için, \(2 \le a,b \le 223\) ve \(a \ne b\) olmak üzere, \(\{a,b\}\) alfabesi üzerindeki genelleştirilmiş Kolakoski dizisi \(K_{a,b}=x_1,x_2,\dots\) tanımlanır. İlk terim \(x_1=a\) olur; koşuların sembolleri \(a,b,a,b,\dots\) şeklinde sırayla gider ve bu koşuların uzunlukları yine dizinin kendi terimleridir. İstenen nicelik
$$T(a,b;N)=\sum_{i=1}^{N} x_i$$
olup burada \(N=22332223332233\). Sonra bütün sıralı çiftler için bu değerler toplanır ve sonuç \(2233222333\) modunda verilir.
İlk \(N\) terimi doğrudan üretmek pratik değildir. Çözüm, dizinin kendi kendini tarif eden yapısını kullanır: bir seviyedeki bilgiler, bir alt seviyede kaç blok açılacağını söyler. Bu yüzden uygulamalar tek tek terim üretmek yerine büyük rekürsif blokları değerlendirir ve tam blok özetlerini bellekte saklar.
Ana fikir, diziye terim terim bakmayı bırakıp rekürsif olarak oluşan blokları özetlemektir. Bu problemde doğru matematiksel nesneler \(K_{a,b}\)'nin koşu ayrışımı, ön ek içindeki \(a\) ve \(b\) sayıları ve sıradaki koşunun nerede olduğunu tutan durum geçişidir.
\(K_{a,b}=x_1,x_2,\dots\) yazalım; her \(x_i\) ya \(a\) ya da \(b\) olsun. Tanım gereği dizi şu maksimum koşulara ayrılır:
$$K_{a,b}= \underbrace{a\cdots a}_{x_1} \underbrace{b\cdots b}_{x_2} \underbrace{a\cdots a}_{x_3} \underbrace{b\cdots b}_{x_4}\cdots.$$
Burada aynı semboller iki rol birden oynar. Bir yandan dizinin değerleridirler, öte yandan alternatif koşuların uzunluklarını belirlerler. Algoritmanın tamamı bu öz-yineli yapı üzerine kuruludur.
İlk \(n\) terimdeki \(a\) sayısına \(A_{a,b}(n)\), \(b\) sayısına \(B_{a,b}(n)\) diyelim. O zaman
$$A_{a,b}(n)+B_{a,b}(n)=n,$$
ve aranan ağırlıklı ön ek toplamı
$$T(a,b;n)=a\,A_{a,b}(n)+b\,B_{a,b}(n)$$
şeklindedir. Dolayısıyla asıl hesap, devasa bir öz-tanımlı ön ekte kaç tane \(a\) ve kaç tane \(b\) olduğunu bulmaktır. Bu sayılar elde edilince \(T(a,b;n)\) zaten doğrudan gelir.
Derinlik-0 bloğu tek bir maksimum koşudur. Geçerli duruma göre mevcut sembolden \(a\) ya da \(b\) tane üretir. Derinlik-1 bloğu, \(a\) veya \(b\) tane derinlik-0 bloğunun art arda gelmesidir. Genel olarak derinlik-\(d\) bloğu, \(a\) veya \(b\) tane derinlik-\((d-1)\) bloğunun birleşimidir.
Bir durum \(s\) için
$$F_d(s;n)=\bigl(\alpha_d(s;n),\beta_d(s;n),\nu_d(s;n)\bigr)$$
ifadesi, derinlik-\(d\) bloğunun ilk \(n\) çıktı teriminin özetini göstersin: \(\alpha_d\) üretilen \(a\) sayısı, \(\beta_d\) üretilen \(b\) sayısı, \(\nu_d\) ise bu ön ekten sonraki durumdur. Tüm blok alınırsa kısaca \(F_d(s)\) yazarız.
\(\lambda_d(s)\in\{a,b\}\) derinlik \(d\)'deki çocuk sayısı olsun ve \(s_1,s_2,\dots\) ardışık çocuk durumları olsun. Tam blok uzunluğu için
$$L_0(s)=\lambda_0(s),\qquad L_d(s)=\sum_{j=1}^{\lambda_d(s)} L_{d-1}(s_j)$$
elde edilir. Sembol sayıları da aynı şekilde toplanır:
$$\alpha_d(s)=\sum_{j=1}^{\lambda_d(s)} \alpha_{d-1}(s_j),\qquad \beta_d(s)=\sum_{j=1}^{\lambda_d(s)} \beta_{d-1}(s_j).$$
Eğer istenen ön ek son çocuğun ortasında bitiyorsa yalnızca o son çocuk kısmi değerlendirilir; ondan önce gelen çocukların hepsi tam bloktur. Uygulamalardaki rekürsiyon tam olarak bunu yapar.
Bu rekürsiyonun, sıradaki bloğun ne olduğunu kompakt biçimde tutması gerekir. Kodda durum bir bit vektörü ile temsil edilir. En düşük bit, taban seviyede sıradaki çıktı sembolünün \(a\) mı yoksa \(b\) mi olduğunu söyler. Her \(r \ge 0\) seviyesi için \(r+1\). bit ise o seviyede aktif olan çokluk seçiminin \(a\) mı yoksa \(b\) mi olduğunu belirtir.
Matematiksel olarak bu durum, açık olan bütün rekürsiyon seviyelerinin sınır bilgisini taşır. \(s\) ve \(d\) sabitlendiğinde tam blok artık tamamen belirlenmiştir: kaç tane \(a\) üreteceği, kaç tane \(b\) üreteceği ve kapandıktan sonra hangi duruma geçileceği bellidir. Bu nedenle tam blok özeti yalnızca \((s,d)\)'ye bağlıdır; önbelleklemenin doğru olmasının sebebi budur.
\(a,b \ge 2\) olduğundan her blok en az 2 çocuk içerir. Bu yüzden tam blok uzunlukları en az üstel hızla büyür:
$$L_d(s)\ge 2^{d+1}.$$
Dolayısıyla her sabit \(N\) için, ilk durumdan başlayan bir bloğun uzunluğu sonunda \(N\)'yi aşan bir derinlik \(d=O(\log N)\) mutlaka vardır. Uygulamalar derinliği artırarak bu eşiği bulur ve sonra istenen ön eki o büyük blok içinden çıkarır.
\((a,b)=(2,3)\) için dizi
$$K_{2,3}=2,2,3,3,2,2,2,3,3,3,\dots$$
şeklinde başlar. Koşulara ayırınca
$$22\;33\;222\;333\;\cdots$$
elde edilir; yani koşu uzunlukları yeniden \(2,2,3,3,\dots\) olur. İlk 10 terimde beş tane 2 ve beş tane 3 vardır. Bu nedenle
$$T(2,3;10)=5\cdot 2+5\cdot 3=25.$$
Bu, uygulamaların açıkça doğruladığı örneklerden biridir ve tam problemin küçük bir modeli gibi düşünülebilir.
Bir \((a,b)\) çifti çözüldükten sonra Project Euler'ın istediği toplam
$$S(N)=\sum_{\substack{2\le a,b\le 223\\ a\ne b}} T(a,b;N)\pmod{2233222333},\qquad N=22332223332233$$
olur. Toplam \(222 \times 221 = 49062\) sıralı çift vardır. Bunlar birbirinden bağımsız olduğu için aynı matematiksel değerlendirici her çift için yeniden kullanılır ve katkılar en sonda mod altında toplanır.
Sabit \(a\) ve \(b\) için C++, Python ve Java uygulamaları \(K_{a,b}\) için bir blok değerlendirici kurar. Başlangıç bloğu \(N\)'yi kapsayana kadar rekürsiyon derinliği artırılır. Dönen özet zaten \(T(a,b;N)=aA+bB\) formülü için gereken iki sembol sayısını içerir.
Önbellek anahtarı “durum artı derinlik” ikilisidir. Her önbellek girdisi üç değer saklar: tam bloğun ürettiği toplam \(a\) sayısı, toplam \(b\) sayısı ve bloğun bitiminden sonraki durum. Böyle bir kayıt yalnızca kalan bütçe tüm bloğu kapsıyorsa tekrar kullanılabilir. Eğer bütçe bloğun ortasında kesiliyorsa rekürsiyonla aşağı inilmelidir; çünkü kesilen son çocuk hem sayıları hem de sonraki durumu değiştirir.
Bir çift değerlendirildikten sonra sembol sayıları ağırlıklı ön ek toplamına çevrilir ve katkı \(2233222333\) modunda sonuca eklenir. C++ ve Java sürümleri farklı \(a\) değerlerini iş parçacıklarına dağıtır; Python sürümü aynı dış döngüyü seri olarak çalıştırır. Üç dilde de matematiksel çekirdek aynıdır.
Sabit bir \((a,b)\) çifti için çalışma süresi ham \(N\) uzunluğuna değil, gerçekten ulaşılan tam blok durumlarının sayısına bağlıdır. Bu sayıyı \(M_{a,b}\) ile gösterirsek bellek kullanımı \(O(M_{a,b})\) olur; çünkü her erişilen memo girdisi bir tam blok özetidir.
Her memo girdisine düşen iş, incelenen çocuk blok sayısıyla sınırlıdır ve bu sayı en fazla \(\max(a,b)\le 223\) olabilir. Dolayısıyla doğal karmaşıklık ifadesi, her sıralı çift için \(O(\max(a,b)\,M_{a,b})\) zaman ve \(O(M_{a,b})\) bellektir. Tam Euler hesabı bunu 49062 sıralı çift için tekrarlar. Kritik nokta şudur: yöntem \(N=22332223332233\) ile değil, erişilen rekürsif durum uzayının büyüklüğü ile ölçeklenir.
Para cada par ordenado \((a,b)\) con \(2 \le a,b \le 223\) y \(a \ne b\), se define la secuencia de Kolakoski generalizada \(K_{a,b}=x_1,x_2,\dots\) sobre el alfabeto \(\{a,b\}\). El primer término es \(x_1=a\), los símbolos de las rachas alternan \(a,b,a,b,\dots\), y las longitudes de esas rachas vuelven a ser los propios términos de la secuencia. Hay que calcular
$$T(a,b;N)=\sum_{i=1}^{N} x_i$$
para el índice enorme \(N=22332223332233\), sumar el resultado sobre todos los pares ordenados y dar la respuesta módulo \(2233222333\).
Construir explícitamente los primeros \(N\) términos es imposible en la práctica. La solución aprovecha que la secuencia se describe a sí misma: una capa de la secuencia dice cuántos bloques aparecen en la capa inferior. Por eso las implementaciones no expanden término por término, sino que evalúan grandes bloques recursivos y memorizan resúmenes de bloques completos.
La idea central es dejar de pensar en términos individuales y pasar a bloques generados recursivamente. En este problema, los objetos matemáticos correctos son la descomposición en rachas de \(K_{a,b}\), los conteos prefijos de \(a\) y \(b\), y un estado que recuerda en qué punto del mecanismo alternante de rachas se encuentra la expansión.
Escribamos \(K_{a,b}=x_1,x_2,\dots\), con \(x_i\in\{a,b\}\). Por definición, la secuencia se agrupa en rachas máximas como
$$K_{a,b}= \underbrace{a\cdots a}_{x_1} \underbrace{b\cdots b}_{x_2} \underbrace{a\cdots a}_{x_3} \underbrace{b\cdots b}_{x_4}\cdots.$$
Así, los mismos símbolos cumplen dos funciones a la vez: son los valores de la secuencia y también determinan las longitudes de las rachas alternantes. Esa autorreferencia es la razón por la que la recursión funciona.
Sea \(A_{a,b}(n)\) el número de apariciones de \(a\) en los primeros \(n\) términos y \(B_{a,b}(n)\) el número de apariciones de \(b\). Entonces
$$A_{a,b}(n)+B_{a,b}(n)=n,$$
y la cantidad pedida es
$$T(a,b;n)=a\,A_{a,b}(n)+b\,B_{a,b}(n).$$
Por tanto, el problema computacional real consiste en contar cuántos \(a\)'s y cuántos \(b\)'s aparecen en un prefijo enorme y auto-referente. Una vez conocidos esos conteos, \(T(a,b;n)\) sale de inmediato.
Un bloque de profundidad 0 es una sola racha máxima. Según el estado actual, emite \(a\) o \(b\) copias del símbolo actual. Un bloque de profundidad 1 es la concatenación de \(a\) o \(b\) bloques de profundidad 0. En general, un bloque de profundidad \(d\) es la concatenación de \(a\) o \(b\) bloques de profundidad \(d-1\).
Para un estado \(s\), definimos
$$F_d(s;n)=\bigl(\alpha_d(s;n),\beta_d(s;n),\nu_d(s;n)\bigr)$$
como el resumen de los primeros \(n\) términos emitidos por un bloque de profundidad \(d\): \(\alpha_d\) cuenta los \(a\)'s producidos, \(\beta_d\) cuenta los \(b\)'s producidos y \(\nu_d\) es el estado siguiente. Cuando tomamos el bloque completo, escribimos simplemente \(F_d(s)\).
Si \(\lambda_d(s)\in\{a,b\}\) es el número de hijos en la profundidad \(d\), y \(s_1,s_2,\dots\) son los estados sucesivos de esos hijos, la longitud total del bloque satisface
$$L_0(s)=\lambda_0(s),\qquad L_d(s)=\sum_{j=1}^{\lambda_d(s)} L_{d-1}(s_j).$$
Los conteos obedecen la misma regla aditiva:
$$\alpha_d(s)=\sum_{j=1}^{\lambda_d(s)} \alpha_{d-1}(s_j),\qquad \beta_d(s)=\sum_{j=1}^{\lambda_d(s)} \beta_{d-1}(s_j).$$
Si el prefijo solicitado termina en medio del último hijo, solo ese último hijo debe evaluarse de forma parcial; todos los anteriores son bloques completos. Esa es exactamente la estructura recursiva que utilizan las implementaciones.
La recursión necesita una representación compacta de qué bloque viene a continuación. El estado se codifica como un vector de bits. El bit menos significativo indica si el siguiente símbolo emitido en la base es \(a\) o \(b\). Para cada nivel recursivo \(r \ge 0\), el bit en la posición \(r+1\) indica si la multiplicidad activa en ese nivel es \(a\) o \(b\).
Desde un punto de vista matemático, el estado guarda toda la frontera de los niveles recursivos abiertos. Fijados \(s\) y \(d\), el bloque completo queda determinado: cuántos \(a\)'s produce, cuántos \(b\)'s produce y cuál es el siguiente estado cuando el bloque termina. Por eso un resumen de bloque completo depende solo de \((s,d)\), y esa es la razón por la que la memoización es válida.
Como \(a,b \ge 2\), cada bloque tiene al menos 2 hijos. Por lo tanto, las longitudes de bloques completos crecen al menos de forma exponencial:
$$L_d(s)\ge 2^{d+1}.$$
Así, para cualquier \(N\) fijo existe alguna profundidad \(d=O(\log N)\) cuyo bloque inicial ya cubre los primeros \(N\) términos. Las implementaciones aumentan la profundidad hasta que eso ocurre y luego extraen el prefijo deseado desde ese bloque suficientemente grande.
Para \((a,b)=(2,3)\), la secuencia empieza como
$$K_{2,3}=2,2,3,3,2,2,2,3,3,3,\dots$$
Agrupada en rachas, esto es
$$22\;33\;222\;333\;\cdots,$$
de modo que las longitudes de las rachas vuelven a ser \(2,2,3,3,\dots\), es decir, la propia secuencia. En los primeros 10 términos hay cinco 2's y cinco 3's, por lo que
$$T(2,3;10)=5\cdot 2+5\cdot 3=25.$$
Ese caso concreto aparece en la validación y sirve como ejemplo pequeño del mecanismo completo.
Una vez resuelto un par \((a,b)\), la cantidad pedida por el problema es
$$S(N)=\sum_{\substack{2\le a,b\le 223\\ a\ne b}} T(a,b;N)\pmod{2233222333},\qquad N=22332223332233.$$
Hay \(222 \times 221 = 49062\) pares ordenados. Como son independientes entre sí, el mismo evaluador matemático puede reutilizarse para todos ellos y luego sumar las contribuciones módulo \(2233222333\).
Para valores fijos de \(a\) y \(b\), las implementaciones en C++, Python y Java crean un evaluador de bloques para \(K_{a,b}\). Van probando profundidades crecientes hasta que el bloque inicial cubre \(N\). El resumen devuelto ya contiene los conteos de \(a\) y \(b\) que hacen falta en la fórmula \(T(a,b;N)=aA+bB\).
La clave de la caché es el par “estado más profundidad”. Cada entrada memorizada guarda tres datos: el número total de \(a\)'s del bloque completo, el número total de \(b\)'s y el estado siguiente al finalizar el bloque. Una entrada memorizada solo puede reutilizarse si el presupuesto restante alcanza para consumir el bloque entero. Si el presupuesto se corta dentro del bloque, hay que bajar recursivamente, porque un último hijo truncado modifica tanto los conteos como el estado final.
Después de evaluar un par, la implementación transforma los conteos de símbolos en la suma prefija ponderada y agrega la contribución módulo \(2233222333\). Las versiones en C++ y Java reparten distintos valores de \(a\) entre hilos de trabajo, mientras que la versión en Python recorre el mismo bucle externo en serie. El núcleo matemático es el mismo en los tres lenguajes.
Para un par fijo \((a,b)\), el coste no está gobernado por \(N\) directamente, sino por el número de estados de bloques completos realmente alcanzados. Si llamamos \(M_{a,b}\) a ese número, el uso de memoria es \(O(M_{a,b})\), porque cada entrada de memoización almacena un único resumen de bloque completo.
El trabajo asociado a cada entrada está acotado por el número de hijos inspeccionados, que nunca supera \(\max(a,b)\le 223\). Por eso una descripción razonable es \(O(\max(a,b)\,M_{a,b})\) tiempo por par ordenado y \(O(M_{a,b})\) memoria. El cálculo total de Euler repite este proceso para 49062 pares y acumula los resultados módulo \(2233222333\). Lo importante es que el algoritmo escala con el espacio de estados recursivo alcanzable, no con \(N=22332223332233\) en bruto.
对每个有序对 \((a,b)\)，其中 \(2 \le a,b \le 223\) 且 \(a \ne b\)，定义字母表 \(\{a,b\}\) 上的广义 Kolakoski 序列 \(K_{a,b}=x_1,x_2,\dots\)。它满足 \(x_1=a\)，各段连续相同数字的符号按 \(a,b,a,b,\dots\) 交替出现，而这些连续段的长度恰好又等于序列本身的各项。题目要求计算
$$T(a,b;N)=\sum_{i=1}^{N} x_i$$
其中 \(N=22332223332233\)，然后把所有有序对的结果相加，并对 \(2233222333\) 取模。
显然，不可能真的把前 \(N\) 项全部生成出来。可行的方法来自这个序列的“自描述”结构：上一层的值决定下一层要展开多少个块。因此实现并不是逐项展开，而是递归地评估大块，并缓存完整块的摘要。
核心思想是把“逐项生成”改写成“递归块摘要”。在这道题里，真正重要的数学对象是 \(K_{a,b}\) 的连续段分解、前缀中 \(a\) 和 \(b\) 的出现次数，以及一个能够记录当前交替段机制走到哪里的状态转移。
记 \(K_{a,b}=x_1,x_2,\dots\)，其中每个 \(x_i\) 都属于 \(\{a,b\}\)。按照定义，这个序列的最大连续段可以写成
$$K_{a,b}= \underbrace{a\cdots a}_{x_1} \underbrace{b\cdots b}_{x_2} \underbrace{a\cdots a}_{x_3} \underbrace{b\cdots b}_{x_4}\cdots.$$
也就是说，同一批符号同时扮演了两种角色：它们既是序列的取值，又规定了交替连续段的长度。这种自指结构正是整个算法能够递归工作的原因。
设 \(A_{a,b}(n)\) 表示前 \(n\) 项中 \(a\) 的个数，\(B_{a,b}(n)\) 表示前 \(n\) 项中 \(b\) 的个数，则有
$$A_{a,b}(n)+B_{a,b}(n)=n,$$
于是所求加权前缀和就是
$$T(a,b;n)=a\,A_{a,b}(n)+b\,B_{a,b}(n).$$
因此真正要解决的问题并不是“把超长前缀全部列出来再求和”，而是“在这个超长的自描述前缀中，一共出现了多少个 \(a\) 和多少个 \(b\)”。只要这两个计数得到，\(T(a,b;n)\) 就立刻确定。
深度 0 的块就是一个最大连续段。根据当前状态，它会输出当前符号的 \(a\) 份或 \(b\) 份。深度 1 的块则是 \(a\) 个或 \(b\) 个深度 0 块的串接。更一般地，深度 \(d\) 的块是 \(a\) 个或 \(b\) 个深度 \(d-1\) 块的串接。
对一个状态 \(s\)，记
$$F_d(s;n)=\bigl(\alpha_d(s;n),\beta_d(s;n),\nu_d(s;n)\bigr)$$
为深度 \(d\) 的块在输出前 \(n\) 项时的摘要：\(\alpha_d\) 是产生的 \(a\) 的个数，\(\beta_d\) 是产生的 \(b\) 的个数，\(\nu_d\) 是输出这段前缀之后的下一个状态。若取完整块，则简写为 \(F_d(s)\)。
若 \(\lambda_d(s)\in\{a,b\}\) 表示深度 \(d\) 这一层需要展开的子块个数，\(s_1,s_2,\dots\) 表示依次进入的子状态，则完整块长度满足
$$L_0(s)=\lambda_0(s),\qquad L_d(s)=\sum_{j=1}^{\lambda_d(s)} L_{d-1}(s_j).$$
符号计数满足完全相同的可加递推：
$$\alpha_d(s)=\sum_{j=1}^{\lambda_d(s)} \alpha_{d-1}(s_j),\qquad \beta_d(s)=\sum_{j=1}^{\lambda_d(s)} \beta_{d-1}(s_j).$$
如果所需前缀在最后一个子块中途结束，那么只有最后这个子块需要部分展开；它之前的所有子块都是完整块。这正是实现所使用的递归结构。
递归要高效，就必须用一个紧凑状态来表示“接下来该展开什么”。实现里把状态编码成一个位向量。最低位表示底层下一次输出的符号是 \(a\) 还是 \(b\)。对每个递归层级 \(r \ge 0\)，第 \(r+1\) 位表示该层当前激活的重复次数是 \(a\) 还是 \(b\)。
从数学上看，这个状态保存了所有尚未关闭的递归层的边界信息。一旦状态 \(s\) 和深度 \(d\) 固定，完整块就完全确定：它会产生多少个 \(a\)、多少个 \(b\)，以及结束后转到什么新状态。也正因为如此，完整块摘要只依赖于 \((s,d)\)，这就是可以进行记忆化缓存的根本原因。
由于 \(a,b \ge 2\)，每个块至少有 2 个子块，所以完整块长度至少按指数增长：
$$L_d(s)\ge 2^{d+1}.$$
于是对任意固定的 \(N\)，总能找到某个深度 \(d=O(\log N)\)，使得从初始状态开始的那个块已经足够长，可以覆盖前 \(N\) 项。实现的做法很直接：不断增加深度，直到初始块覆盖 \(N\)，然后从这个足够大的块中截取所需前缀。
当 \((a,b)=(2,3)\) 时，序列开头是
$$K_{2,3}=2,2,3,3,2,2,2,3,3,3,\dots$$
按连续段分组后就是
$$22\;33\;222\;333\;\cdots,$$
因此这些连续段的长度再次变成 \(2,2,3,3,\dots\)，也就是序列本身。前 10 项里有 5 个 2 和 5 个 3，所以
$$T(2,3;10)=5\cdot 2+5\cdot 3=25.$$
这个例子正是实现中用来做校验的样例之一，也很好地展示了整个方法的缩影。
当一个 \((a,b)\) 已经求出后，题目最终要求的是
$$S(N)=\sum_{\substack{2\le a,b\le 223\\ a\ne b}} T(a,b;N)\pmod{2233222333},\qquad N=22332223332233.$$
这里共有 \(222 \times 221 = 49062\) 个有序对。它们彼此独立，因此同一个数学评估器可以反复用于每个有序对，然后再把所有贡献在模 \(2233222333\) 下累加。
对固定的 \(a\) 和 \(b\)，C++、Python 和 Java 实现都会建立一个面向 \(K_{a,b}\) 的块评估器。程序从较小深度开始，逐步提高递归深度，直到初始块足够长，能够覆盖 \(N\)。返回的摘要已经直接给出了 \(T(a,b;N)=aA+bB\) 所需的两个计数。
缓存键由“状态 + 深度”组成。每条缓存记录保存三个量：完整块输出的 \(a\) 的总数、\(b\) 的总数，以及该块结束后的新状态。只有当剩余预算足以吞下整个块时，这条记录才能被直接复用。若预算在块中途截断，就必须递归下钻，因为最后那个被截断的子块会同时影响计数和后继状态。
在一个有序对求值完成后，实现会把 \(a\) 与 \(b\) 的计数转换成加权前缀和，并把这项贡献按模 \(2233222333\) 加到总答案里。C++ 和 Java 版本把不同的 \(a\) 值分配给多个工作线程，Python 版本则串行完成同样的外层循环。三种语言共享完全相同的数学核心。
对固定 \((a,b)\) 而言，时间复杂度并不由 \(N\) 的大小直接决定，而是由真正到达的完整块状态数量决定。若把这个数量记为 \(M_{a,b}\)，那么空间复杂度就是 \(O(M_{a,b})\)，因为每个可达缓存项只存一个完整块摘要。
每个缓存项所需的工作量，最多等于它需要查看的子块个数，而这个个数不超过 \(\max(a,b)\le 223\)。因此，每个有序对可以自然地描述为 \(O(\max(a,b)\,M_{a,b})\) 时间、\(O(M_{a,b})\) 空间。最终的 Euler 计算会对 49062 个有序对重复这一过程，并在模 \(2233222333\) 下累加。关键点在于：算法的规模取决于可达递归状态空间，而不是原始前缀长度 \(N=22332223332233\) 本身。
Для каждой упорядоченной пары \((a,b)\), где \(2 \le a,b \le 223\) и \(a \ne b\), рассматривается обобщенная последовательность Колакоски \(K_{a,b}=x_1,x_2,\dots\) над алфавитом \(\{a,b\}\). Первый член равен \(x_1=a\), символы серий чередуются как \(a,b,a,b,\dots\), а длины этих серий снова совпадают с самими членами последовательности. Требуется вычислить
$$T(a,b;N)=\sum_{i=1}^{N} x_i$$
для огромного индекса \(N=22332223332233\), затем просуммировать это значение по всем упорядоченным парам и взять результат по модулю \(2233222333\).
Явно породить первые \(N\) членов невозможно. Решение опирается на самопорождающуюся структуру последовательности: один уровень описывает, сколько блоков появляется уровнем ниже. Поэтому реализации не разворачивают последовательность поэлементно, а вычисляют большие рекурсивные блоки и кэшируют сводки для полных блоков.
Главная идея состоит в том, чтобы заменить поэлементную генерацию анализом рекурсивно построенных блоков. В этой задаче ключевыми математическими объектами являются разложение \(K_{a,b}\) на серии, префиксные количества символов \(a\) и \(b\), а также переход состояния, который запоминает текущую позицию в механизме чередующихся серий.
Запишем \(K_{a,b}=x_1,x_2,\dots\), где каждый \(x_i\) принадлежит \(\{a,b\}\). По определению последовательность разбивается на максимальные серии
$$K_{a,b}= \underbrace{a\cdots a}_{x_1} \underbrace{b\cdots b}_{x_2} \underbrace{a\cdots a}_{x_3} \underbrace{b\cdots b}_{x_4}\cdots.$$
Одни и те же значения играют две роли одновременно: это и сами элементы последовательности, и длины чередующихся серий. Именно эта самоссылочная структура делает возможной рекурсивную схему.
Обозначим через \(A_{a,b}(n)\) число символов \(a\) среди первых \(n\) членов, а через \(B_{a,b}(n)\) число символов \(b\). Тогда
$$A_{a,b}(n)+B_{a,b}(n)=n,$$
а искомая взвешенная префиксная сумма равна
$$T(a,b;n)=a\,A_{a,b}(n)+b\,B_{a,b}(n).$$
Значит, вычислительная задача состоит не в том, чтобы явно выписать гигантский префикс, а в том, чтобы узнать, сколько раз в этом самореферентном префиксе встречаются \(a\) и \(b\). После этого значение \(T(a,b;n)\) получается сразу.
Блок глубины 0 представляет собой одну максимальную серию. В зависимости от состояния он порождает \(a\) или \(b\) копий текущего символа. Блок глубины 1 есть конкатенация \(a\) или \(b\) блоков глубины 0. Вообще блок глубины \(d\) есть конкатенация \(a\) или \(b\) блоков глубины \(d-1\).
Для состояния \(s\) обозначим через
$$F_d(s;n)=\bigl(\alpha_d(s;n),\beta_d(s;n),\nu_d(s;n)\bigr)$$
сводку первых \(n\) выданных членов блока глубины \(d\): \(\alpha_d\) считает, сколько символов \(a\) было порождено, \(\beta_d\) считает число символов \(b\), а \(\nu_d\) обозначает следующее состояние после этого префикса. Для полного блока будем писать просто \(F_d(s)\).
Если \(\lambda_d(s)\in\{a,b\}\) обозначает число дочерних блоков на глубине \(d\), а \(s_1,s_2,\dots\) обозначают последовательные дочерние состояния, то длина полного блока подчиняется соотношению
$$L_0(s)=\lambda_0(s),\qquad L_d(s)=\sum_{j=1}^{\lambda_d(s)} L_{d-1}(s_j).$$
Для подсчета символов действует та же аддитивная рекурсия:
$$\alpha_d(s)=\sum_{j=1}^{\lambda_d(s)} \alpha_{d-1}(s_j),\qquad \beta_d(s)=\sum_{j=1}^{\lambda_d(s)} \beta_{d-1}(s_j).$$
Если нужный префикс заканчивается в середине последнего дочернего блока, частично вычислять нужно только этот последний блок; все предыдущие дети берутся целиком. Именно так и устроена рекурсивная процедура в реализациях.
Чтобы рекурсия была эффективной, надо компактно кодировать, какой блок должен раскрываться следующим. Состояние представлено битовым вектором. Младший бит задает, какой символ будет выдан следующим на базовом уровне: \(a\) или \(b\). Для каждого уровня рекурсии \(r \ge 0\) бит в позиции \(r+1\) показывает, является ли текущая активная кратность на этом уровне равной \(a\) или \(b\).
С математической точки зрения состояние хранит границу всех еще не закрытых уровней рекурсии. Как только фиксированы \(s\) и \(d\), полный блок однозначно определен: сколько он породит символов \(a\), сколько символов \(b\) и в какое состояние перейдет после закрытия. Поэтому сводка полного блока зависит только от пары \((s,d)\), и именно это делает мемоизацию корректной.
Так как \(a,b \ge 2\), у каждого блока как минимум 2 дочерних блока. Следовательно, длины полных блоков растут как минимум экспоненциально:
$$L_d(s)\ge 2^{d+1}.$$
Значит, для любого фиксированного \(N\) найдется глубина \(d=O(\log N)\), на которой начальный блок уже покрывает первые \(N\) членов. Реализации просто увеличивают глубину, пока это не станет верно, а затем извлекают нужный префикс из достаточно большого блока.
Для \((a,b)=(2,3)\) последовательность начинается так:
$$K_{2,3}=2,2,3,3,2,2,2,3,3,3,\dots$$
Если сгруппировать ее по сериям, получим
$$22\;33\;222\;333\;\cdots,$$
то есть длины серий снова равны \(2,2,3,3,\dots\), то есть самой последовательности. Среди первых 10 членов имеется пять двоек и пять троек, поэтому
$$T(2,3;10)=5\cdot 2+5\cdot 3=25.$$
Этот пример явно проверяется в реализации и хорошо иллюстрирует общий механизм на маленьком случае.
После того как вычислено значение для одной пары \((a,b)\), итоговая величина задачи имеет вид
$$S(N)=\sum_{\substack{2\le a,b\le 223\\ a\ne b}} T(a,b;N)\pmod{2233222333},\qquad N=22332223332233.$$
Всего имеется \(222 \times 221 = 49062\) упорядоченных пар. Они независимы, поэтому один и тот же математический вычислитель можно многократно применять к каждой паре, а затем сложить вклады по модулю \(2233222333\).
Для фиксированных \(a\) и \(b\) реализации на C++, Python и Java создают вычислитель блоков для \(K_{a,b}\). Они постепенно увеличивают глубину рекурсии, пока начальный блок не станет достаточно длинным, чтобы покрыть \(N\). Возвращенная сводка уже содержит два количества, необходимые для формулы \(T(a,b;N)=aA+bB\).
Ключ кэша состоит из пары “состояние и глубина”. Каждая кэшированная запись хранит три величины: общее число символов \(a\) в полном блоке, общее число символов \(b\) в полном блоке и следующее состояние после завершения блока. Такую запись можно использовать повторно только в том случае, когда оставшегося бюджета хватает на весь блок. Если бюджет обрезает блок внутри, вычисление должно спуститься рекурсивно ниже, потому что усеченный последний дочерний блок меняет и счетчики, и конечное состояние.
После вычисления одной пары код переводит числа символов в взвешенную префиксную сумму и добавляет вклад по модулю \(2233222333\). В версиях на C++ и Java разные значения \(a\) распределяются между рабочими потоками, а версия на Python выполняет тот же внешний цикл последовательно. Во всех трех языках математическое ядро одно и то же.
Для фиксированной пары \((a,b)\) время работы определяется не величиной \(N\) само по себе, а числом реально достигнутых состояний полных блоков. Если обозначить это число через \(M_{a,b}\), то память составляет \(O(M_{a,b})\), поскольку каждая достижимая запись мемоизации хранит ровно одну сводку полного блока.
Работа, связанная с одной такой записью, ограничена числом просматриваемых дочерних блоков, а это число не превосходит \(\max(a,b)\le 223\). Поэтому естественно описывать сложность как \(O(\max(a,b)\,M_{a,b})\) времени на одну упорядоченную пару и \(O(M_{a,b})\) памяти. Полный расчет задачи Euler повторяет этот процесс для 49062 пар и суммирует результаты по модулю \(2233222333\). Ключевой момент состоит в том, что алгоритм масштабируется по достижимому рекурсивному пространству состояний, а не по самому \(N=22332223332233\).
لكل زوج مرتب \((a,b)\) بحيث \(2 \le a,b \le 223\) و\(a \ne b\)، نعرّف متتالية كولاكوسكي المعممة \(K_{a,b}=x_1,x_2,\dots\) على الأبجدية \(\{a,b\}\). الحد الأول هو \(x_1=a\)، والرموز في الرانات تتناوب على الصورة \(a,b,a,b,\dots\)، بينما أطوال هذه الرانات تساوي حدود المتتالية نفسها. المطلوب حساب
$$T(a,b;N)=\sum_{i=1}^{N} x_i$$
عند الفهرس الضخم \(N=22332223332233\)، ثم جمع هذه القيمة على جميع الأزواج المرتبة وأخذ النتيجة بترديد \(2233222333\).
من المستحيل عمليًا توليد أول \(N\) حدًا واحدًا بعد واحد. الحل يعتمد على أن المتتالية تصف نفسها: مستوى واحد منها يحدد عدد الكتل التي يجب أن تتمدد في المستوى الأدنى. لذلك لا تقوم التطبيقات بتوليد الحدود عنصرًا بعد عنصر، بل تقيّم كتلًا تكرارية كبيرة وتخزن ملخصات الكتل الكاملة.
الفكرة الأساسية هي التوقف عن التفكير على مستوى الحد المفرد، والانتقال إلى تلخيص كتل تتولد بصورة تكرارية. في هذه المسألة، الكائنات الرياضية المهمة فعلًا هي تفكيك \(K_{a,b}\) إلى رانات، وعدد مرات ظهور \(a\) و\(b\) داخل البادئة، وحالة انتقال تحفظ موضعنا الحالي داخل آلية الرانات المتناوبة.
لنكتب \(K_{a,b}=x_1,x_2,\dots\) حيث كل \(x_i\) ينتمي إلى \(\{a,b\}\). حسب التعريف، تنقسم المتتالية إلى رانات عظمى بالشكل
$$K_{a,b}= \underbrace{a\cdots a}_{x_1} \underbrace{b\cdots b}_{x_2} \underbrace{a\cdots a}_{x_3} \underbrace{b\cdots b}_{x_4}\cdots.$$
إذن القيم نفسها تلعب دورين في آن واحد: فهي حدود المتتالية، وهي أيضًا الأطوال التي تحدد الرانات المتعاقبة. هذه البنية الذاتية هي السبب الذي يجعل المعالجة التكرارية ممكنة أصلًا.
لنرمز بـ \(A_{a,b}(n)\) إلى عدد مرات ظهور \(a\) في أول \(n\) حد، وبـ \(B_{a,b}(n)\) إلى عدد مرات ظهور \(b\). عندئذ
$$A_{a,b}(n)+B_{a,b}(n)=n,$$
ويصبح مجموع البادئة الموزون المطلوب
$$T(a,b;n)=a\,A_{a,b}(n)+b\,B_{a,b}(n).$$
وهذا يعني أن جوهر المسألة الحسابية ليس توليد البادئة العملاقة ثم جمعها، بل معرفة كم مرة يظهر \(a\) وكم مرة يظهر \(b\) داخل هذه البادئة ذاتية المرجع. بمجرد معرفة هذين العددين نحصل على \(T(a,b;n)\) فورًا.
كتلة العمق 0 هي رانة عظمى واحدة. وفقًا للحالة الحالية، تنتج \(a\) أو \(b\) نسخة من الرمز الحالي. أما كتلة العمق 1 فهي لصق \(a\) أو \(b\) من كتل العمق 0. وبشكل عام، كتلة العمق \(d\) هي لصق \(a\) أو \(b\) من كتل العمق \(d-1\).
لأي حالة \(s\)، نعرّف
$$F_d(s;n)=\bigl(\alpha_d(s;n),\beta_d(s;n),\nu_d(s;n)\bigr)$$
على أنها ملخص أول \(n\) حدًا مخرَجًا من كتلة عمقها \(d\): حيث \(\alpha_d\) هو عدد قيم \(a\) الناتجة، و\(\beta_d\) هو عدد قيم \(b\) الناتجة، و\(\nu_d\) هي الحالة التالية بعد هذه البادئة. وعند أخذ الكتلة كاملة نكتب فقط \(F_d(s)\).
إذا كانت \(\lambda_d(s)\in\{a,b\}\) تمثل عدد الأبناء في العمق \(d\)، وكانت \(s_1,s_2,\dots\) هي حالات الأبناء المتتالية، فإن طول الكتلة الكاملة يحقق
$$L_0(s)=\lambda_0(s),\qquad L_d(s)=\sum_{j=1}^{\lambda_d(s)} L_{d-1}(s_j).$$
ويخضع العد للعلاقة الجمعية نفسها:
$$\alpha_d(s)=\sum_{j=1}^{\lambda_d(s)} \alpha_{d-1}(s_j),\qquad \beta_d(s)=\sum_{j=1}^{\lambda_d(s)} \beta_{d-1}(s_j).$$
إذا انتهت البادئة المطلوبة داخل الابن الأخير، فذلك الابن الأخير فقط هو الذي يقيَّم جزئيًا؛ أما الأبناء السابقون فهم كتل كاملة. وهذه هي البنية الرياضية الدقيقة التي تطبقها الشيفرة.
لكي تعمل هذه البنية التكرارية بكفاءة، لا بد من تمثيل مضغوط لما سيأتي بعد ذلك. الحالة ممثلة بمتجه بتات. البت الأقل وزنًا يحدد هل الرمز التالي على المستوى الأساسي هو \(a\) أم \(b\). ولكل مستوى تكراري \(r \ge 0\)، فإن البت في الموضع \(r+1\) يحدد هل المضاعفية النشطة على ذلك المستوى هي \(a\) أم \(b\).
رياضيًا، هذه الحالة تحفظ الحدود المفتوحة لجميع مستويات التوسع الحالية. وما دام \(s\) و\(d\) معروفين، فإن الكتلة الكاملة تصبح محددة بالكامل: كم عدد \(a\) الذي تنتجه، وكم عدد \(b\)، وما الحالة التي نصل إليها بعد إغلاق الكتلة. ولهذا فإن ملخص الكتلة الكاملة يعتمد فقط على الزوج \((s,d)\)، ومن هنا تأتي صحة التخزين بالذاكرة.
بما أن \(a,b \ge 2\)، فكل كتلة تحتوي على ابنين على الأقل. لذلك تنمو أطوال الكتل الكاملة نموًا أسيًا على الأقل:
$$L_d(s)\ge 2^{d+1}.$$
إذن لأي \(N\) ثابت يوجد عمق \(d=O(\log N)\) تصبح عنده الكتلة الابتدائية طويلة بما يكفي لتغطية أول \(N\) حدًا. ما تفعله التطبيقات ببساطة هو زيادة العمق تدريجيًا حتى يتحقق ذلك، ثم استخراج البادئة المطلوبة من داخل تلك الكتلة الكبيرة.
عندما \((a,b)=(2,3)\) تبدأ المتتالية على الصورة
$$K_{2,3}=2,2,3,3,2,2,2,3,3,3,\dots$$
وبتجميعها في رانات نحصل على
$$22\;33\;222\;333\;\cdots,$$
فتعود أطوال الرانات نفسها لتكون \(2,2,3,3,\dots\)، أي المتتالية ذاتها من جديد. في أول 10 حدود يوجد خمس قيم 2 وخمس قيم 3، ولذلك
$$T(2,3;10)=5\cdot 2+5\cdot 3=25.$$
هذه الحالة الصغيرة مستخدمة صراحة في التحقق، وهي نموذج واضح للطريقة العامة.
بعد حساب قيمة زوج واحد \((a,b)\)، تصبح الكمية المطلوبة في المسألة
$$S(N)=\sum_{\substack{2\le a,b\le 223\\ a\ne b}} T(a,b;N)\pmod{2233222333},\qquad N=22332223332233.$$
يوجد \(222 \times 221 = 49062\) زوجًا مرتبًا. وهذه الأزواج مستقلة عن بعضها، ولذلك يمكن إعادة استخدام نفس المقيّم الرياضي لكل زوج ثم جمع الإسهامات بترديد \(2233222333\).
لكل قيمتين ثابتتين \(a\) و\(b\)، تنشئ تطبيقات C++ وPython وJava مقيّم كتل خاصًا بـ \(K_{a,b}\). ثم تزيد عمق التكرار خطوة خطوة حتى تصبح الكتلة الابتدائية كافية لتغطية \(N\). الملخص المعاد يحتوي مباشرة على العددين اللازمين في الصيغة \(T(a,b;N)=aA+bB\).
مفتاح الذاكرة المؤقتة هو الزوج «الحالة + العمق». وكل مدخل مخزن يحتوي على ثلاث قيم: العدد الكلي لرموز \(a\) في الكتلة الكاملة، والعدد الكلي لرموز \(b\)، والحالة التالية بعد انتهاء الكتلة. ولا يمكن إعادة استخدام هذا الملخص إلا إذا كانت الميزانية المتبقية تكفي لابتلاع الكتلة كاملة. أما إذا قُطعت الكتلة في الوسط، فلا بد من النزول تكراريًا، لأن الابن الأخير المبتور يغيّر العدّ والحالة اللاحقة معًا.
بعد إنهاء زوج واحد، تحوّل الشيفرة عدد مرات ظهور الرمزين إلى مجموع بادئة موزون، ثم تضيف هذه المساهمة بترديد \(2233222333\). نسختا C++ وJava توزعان القيم المختلفة لـ \(a\) على خيوط عمل متعددة، بينما تنفذ نسخة Python الحلقة الخارجية نفسها بصورة تسلسلية. اللب الرياضي واحد في جميع اللغات الثلاث.
بالنسبة إلى زوج ثابت \((a,b)\)، لا يتحكم \(N\) مباشرة في زمن التنفيذ، بل يتحكم فيه عدد حالات الكتل الكاملة التي يتم الوصول إليها فعلًا. إذا سمينا هذا العدد \(M_{a,b}\)، فإن الذاكرة تكون \(O(M_{a,b})\)، لأن كل مدخل محفوظ يخزن ملخص كتلة كاملة واحدة.
أما العمل المرتبط بكل مدخل، فهو محدود بعدد الأبناء الذين يجب فحصهم، وهذا العدد لا يتجاوز \(\max(a,b)\le 223\). لذلك يمكن وصف التعقيد طبيعيًا بأنه \(O(\max(a,b)\,M_{a,b})\) زمنًا لكل زوج مرتب و\(O(M_{a,b})\) ذاكرة. وتكرر عملية Euler الكاملة ذلك على 49062 زوجًا ثم تجمع النتائج بترديد \(2233222333\). الفكرة الحاسمة هي أن الخوارزمية تتوسع مع حجم فضاء الحالات التكراري القابل للوصول، لا مع \(N=22332223332233\) نفسه.