Let \(t=0110100110010110\ldots\) be the infinite Thue-Morse word, the fixed point of the morphism \(\mu:0\mapsto01,\;1\mapsto10\). For each length \(\ell\), let \(T_\ell\) be the set of distinct factors of \(t\) of length \(\ell\). Sort \(T_\ell\) lexicographically, keep only the words whose first bit is \(1\), and then concatenate these filtered lists for \(\ell=1,2,3,\ldots\). Reading every chosen word as a binary integer produces the sequence \(A(1),A(2),\ldots\). The goal is to compute
$$\sum_{k=1}^{18} A(10^k) \pmod{10^9}.$$
Write
$$p(\ell)=|T_\ell|.$$
The solution files use the standard Thue-Morse factor-complexity recurrence with the explicit base values
$$p(1)=2,\qquad p(2)=4,\qquad p(3)=6,$$
and for \(n\ge 2\),
$$p(2n)=p(n)+p(n+1),\qquad p(2n+1)=2p(n+1).$$
Now define the cumulative count
$$s(\ell)=\sum_{j=1}^{\ell} p(j).$$
The code memoizes the derived recurrences
$$s(2n)=3s(n)+s(n+1)-8,\qquad s(2n+1)=4s(n)+3p(n+1)-8.$$
Why does this help with the Project Euler sequence? Because the Thue-Morse word is closed under bitwise complement: if \(w\in T_\ell\), then \(\overline{w}\in T_\ell\). No nonempty binary word equals its own complement, so the factors of length \(\ell\) are paired into one word starting with \(0\) and one starting with \(1\). Hence exactly half of them start with \(1\), and the number of valid Euler terms up to length \(\ell\) is
$$\operatorname{count\_upto}(\ell)=\frac{s(\ell)}{2}.$$
Given \(N\), the program first finds the smallest length \(\ell\) such that
$$\frac{s(\ell)}{2}\ge N.$$
This is done by doubling an upper bound and then applying binary search. Once \(\ell\) is known, the rank of the desired word inside the filtered list for this fixed length is
$$k=N-\operatorname{count\_upto}(\ell-1).$$
Inside the full lexicographic list of all words in \(T_\ell\), the leading-\(0\) half comes first and the leading-\(1\) half comes second. Therefore the wanted factor is the
$$\frac{p(\ell)}{2}+k$$
th factor of length \(\ell\) in complete lexicographic order. This is the reason for the line
$$\texttt{offset}=p(\ell)/2+k$$
in all three implementations.
The difficult part is selecting the \(\texttt{offset}\)-th factor of length \(\ell\) without listing all factors. The implementations stop recursion at lengths \(1,2,3\), where the factor sets are stored explicitly:
$$T_1=\{0,1\},\qquad T_2=\{00,01,10,11\},\qquad T_3=\{001,010,011,100,101,110\}.$$
For \(\ell\ge 4\), the solution uses the unique reading frame induced by the length-2 morphism \(\mu\). Every factor either starts on a block boundary of \(\mu\) or one symbol later, and that leads to three lexicographic classes called \(O1\), \(E\), and \(O0\) in the source code.
Let \(\ell=2n\). If a factor starts on an even boundary, it is exactly \(\mu(u)\) for a unique \(u\in T_n\). This gives the middle class
$$E(u)=\mu(u),\qquad u\in T_n,$$
with size \(p(n)\).
If the factor starts one position later, it begins inside one \(\mu\)-block and ends inside another. For an ancestor \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\), the odd-start construction used by the code is
$$\operatorname{OE}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_n)\,a_{n+1}.$$
If \(a_1=1\), the result starts with \(0\); if \(a_1=0\), the result starts with \(1\). Thus the complete lexicographic order for length \(2n\) splits into three consecutive blocks:
$$O1,\qquad E,\qquad O0,$$
with sizes
$$\frac{p(n+1)}{2},\qquad p(n),\qquad \frac{p(n+1)}{2}.$$
A concrete example is \(\ell=4\), where the ten factors are
$$0010,0011,0100 \mid 0101,0110,1001,1010 \mid 1011,1100,1101.$$
The first block is \(O1\), the middle block is \(E\), and the last block is \(O0\).
Let \(\ell=2n+1\). There are again two alignment types, but now an odd-start factor crosses only the left block boundary, while an even-start factor crosses only the right one. For \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\), the code uses
$$\operatorname{OO}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_{n+1}),$$
$$\operatorname{EO}(a)=\mu(a_1a_2\cdots a_n)\,a_{n+1}.$$
Exactly as in the even case, the lexicographic order is
$$O1,\qquad E,\qquad O0,$$
but now the block sizes are
$$\frac{p(n+1)}{2},\qquad p(n+1),\qquad \frac{p(n+1)}{2}.$$
This is why the recursive selector only needs the values \(p(n)\) and \(p(n+1)\) to decide which branch contains the required factor.
The chosen factor can be very long, so the program never builds its ordinary binary integer directly. Instead it defines
$$M=10^9,\qquad B_i=2^{2^i}\bmod M,$$
and lets \(V_i(w)\) be the value of a binary word \(w\) when read in base \(B_i\). In particular, \(V_0(w)\) is exactly the ordinary binary value modulo \(M\).
Concatenation satisfies the standard rule
$$V_i(uv)=V_i(u)\,B_i^{|v|}+V_i(v).$$
For the morphism, one block \(\mu(c)\) has value
$$V_i(\mu(c))=1+(B_i-1)c,\qquad c\in\{0,1\}.$$
So for \(w=c_1c_2\cdots c_m\),
$$V_i(\mu(w))=\sum_{j=1}^{m} B_i^{m-j}\bigl(1+(B_i-1)c_j\bigr).$$
Separating the constant part from the digit-dependent part gives
$$V_i(\mu(w))=G_{i+1}(m)+(B_i-1)V_{i+1}(w),$$
where
$$G_j(m)=\sum_{r=0}^{m-1} B_j^r.$$
This identity is exactly what the cached MU node evaluation computes. The helper
pow_sum stores both \(B_i^m\) and \(G_i(m)\), so each evaluation step remains small and reusable.
The C++, Python, and Java versions all follow the same structure. They memoize p_count and
s_count, use find_length_for_index to locate the correct length, and then call
select_node to build only a symbolic expression DAG for the requested factor. WordBuilder
has four node types: empty, leaf, concatenation, and morphism application. The helper methods
prefix, suffix, and middle implement the ancestor-to-descendant maps behind
the \(O1/E/O0\) split. Finally get_eval computes the cached values \(V_i\) for each node, and
compute_A_mod returns \(V_0\). The C++ file also contains sanity checks proving that the construction
reproduces \(A(100)=3251\) and \(A(1000)=80852364498\).
Because every recurrence halves its argument, computing \(p(\ell)\) or \(s(\ell)\) touches only \(O(\log \ell)\)
memoized states. The length search for \(A(N)\) costs \(O(\log N)\) calls to count_upto. After that,
select_node descends through \(O(\log \ell)\) recursive levels, and the node evaluator works with a
fixed base table of size 64. So each query is handled in polylogarithmic time with \(O(\log \ell)\) symbolic
memory, which is dramatically smaller than generating all factors or building the full binary integer.
Sei \(t=0110100110010110\ldots\) das unendliche Thue-Morse-Wort, also der Fixpunkt des Morphismus \(\mu:0\mapsto01,\;1\mapsto10\). Für jede Länge \(\ell\) bezeichne \(T_\ell\) die Menge aller verschiedenen Faktoren von \(t\) mit Länge \(\ell\). Diese Menge wird lexikographisch sortiert; danach behält man nur die Wörter, die mit \(1\) beginnen, und hängt die so gefilterten Listen für \(\ell=1,2,3,\ldots\) aneinander. Liest man jedes dieser Wörter als Binärzahl, entsteht die Folge \(A(1),A(2),\ldots\). Gesucht ist
$$\sum_{k=1}^{18} A(10^k) \pmod{10^9}.$$
Wir schreiben
$$p(\ell)=|T_\ell|.$$
Die Implementierungen verwenden für die Thue-Morse-Teilwortkomplexität die Startwerte
$$p(1)=2,\qquad p(2)=4,\qquad p(3)=6,$$
und für \(n\ge 2\) die Rekursionen
$$p(2n)=p(n)+p(n+1),\qquad p(2n+1)=2p(n+1).$$
Dazu kommt die kumulative Funktion
$$s(\ell)=\sum_{j=1}^{\ell} p(j),$$
für die der Code die abgeleiteten Formeln
$$s(2n)=3s(n)+s(n+1)-8,\qquad s(2n+1)=4s(n)+3p(n+1)-8$$
memoisiert.
Entscheidend ist die Komplement-Symmetrie des Thue-Morse-Wortes: Aus \(w\in T_\ell\) folgt auch \(\overline{w}\in T_\ell\). Kein nichtleeres Binärwort ist mit seinem eigenen Komplement identisch, also zerfallen die Faktoren in Paare aus einem Wort mit führender \(0\) und einem Wort mit führender \(1\). Deshalb beginnt genau die Hälfte aller Faktoren mit \(1\), und die Zahl der für Euler relevanten Wörter bis Länge \(\ell\) ist
$$\operatorname{count\_upto}(\ell)=\frac{s(\ell)}{2}.$$
Für ein gegebenes \(N\) sucht das Programm zunächst die kleinste Länge \(\ell\) mit
$$\frac{s(\ell)}{2}\ge N.$$
Das geschieht per Verdopplung der Schranke und anschließender Binärsuche. Danach ist der Rang innerhalb der gefilterten Liste fester Länge gleich
$$k=N-\operatorname{count\_upto}(\ell-1).$$
In der vollständigen lexikographischen Ordnung von \(T_\ell\) stehen zuerst alle Wörter mit führender \(0\) und danach alle mit führender \(1\). Gesucht ist also der
$$\frac{p(\ell)}{2}+k$$
te Faktor von Länge \(\ell\) in der Gesamtliste. Genau das codiert die Zeile
$$\texttt{offset}=p(\ell)/2+k.$$
Der schwierige Teil ist die Auswahl des \(\texttt{offset}\)-ten Faktors ohne vollständige Aufzählung. Für die Längen \(1,2,3\) sind die Faktorlisten direkt hinterlegt:
$$T_1=\{0,1\},\qquad T_2=\{00,01,10,11\},\qquad T_3=\{001,010,011,100,101,110\}.$$
Für \(\ell\ge 4\) nutzt der Code den eindeutigen Leserahmen des 2-Buchstaben-Morphismus \(\mu\). Ein Faktor beginnt entweder genau auf einer \(\mu\)-Blockgrenze oder um ein Symbol versetzt. Daraus entstehen die drei im Quelltext verwendeten Klassen \(O1\), \(E\) und \(O0\).
Sei \(\ell=2n\). Beginnt ein Faktor auf einer geraden Blockgrenze, dann ist er genau \(\mu(u)\) für ein eindeutiges \(u\in T_n\). Das ist die mittlere Klasse
$$E(u)=\mu(u),\qquad u\in T_n,$$
mit Größe \(p(n)\).
Beginnt der Faktor eine Position später, so startet er innerhalb eines \(\mu\)-Blocks und endet innerhalb eines anderen. Für einen Vorfahren \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\) verwendet das Programm die Abbildung
$$\operatorname{OE}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_n)\,a_{n+1}.$$
Bei \(a_1=1\) beginnt das Ergebnis mit \(0\), bei \(a_1=0\) mit \(1\). Daher zerfällt die lexikographische Ordnung aller Faktoren der Länge \(2n\) in die drei aufeinanderfolgenden Blöcke
$$O1,\qquad E,\qquad O0,$$
mit den Größen
$$\frac{p(n+1)}{2},\qquad p(n),\qquad \frac{p(n+1)}{2}.$$
Für \(\ell=4\) erhält man konkret
$$0010,0011,0100 \mid 0101,0110,1001,1010 \mid 1011,1100,1101,$$
also genau die Aufteilung \(O1\), \(E\), \(O0\).
Sei \(\ell=2n+1\). Auch hier gibt es zwei Ausrichtungen, aber nun überquert ein ungerade gestarteter Faktor nur die linke Blockgrenze, ein gerade gestarteter nur die rechte. Für \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\) benutzt der Code
$$\operatorname{OO}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_{n+1}),$$
$$\operatorname{EO}(a)=\mu(a_1a_2\cdots a_n)\,a_{n+1}.$$
Die lexikographische Reihenfolge lautet wieder
$$O1,\qquad E,\qquad O0,$$
diesmal mit den Blockgrößen
$$\frac{p(n+1)}{2},\qquad p(n+1),\qquad \frac{p(n+1)}{2}.$$
Darum reichen im rekursiven Wähler die Werte \(p(n)\) und \(p(n+1)\), um den richtigen Zweig zu bestimmen.
Der ausgewählte Faktor kann sehr lang sein, daher bildet der Code die gewöhnliche Binärzahl nie vollständig aus. Stattdessen definiert er
$$M=10^9,\qquad B_i=2^{2^i}\bmod M,$$
und \(V_i(w)\) als Wert des Wortes \(w\) in Basis \(B_i\). Insbesondere ist \(V_0(w)\) genau der gewöhnliche Binärwert modulo \(M\).
Für eine Konkatenation gilt
$$V_i(uv)=V_i(u)\,B_i^{|v|}+V_i(v).$$
Für den Morphismus hat ein einzelner Block \(\mu(c)\) den Wert
$$V_i(\mu(c))=1+(B_i-1)c,\qquad c\in\{0,1\}.$$
Somit folgt für \(w=c_1c_2\cdots c_m\)
$$V_i(\mu(w))=\sum_{j=1}^{m} B_i^{m-j}\bigl(1+(B_i-1)c_j\bigr).$$
Nach Trennung des konstanten und des von den Ziffern abhängigen Anteils ergibt sich
$$V_i(\mu(w))=G_{i+1}(m)+(B_i-1)V_{i+1}(w),$$
wobei
$$G_j(m)=\sum_{r=0}^{m-1} B_j^r.$$
Genau diese Identität implementiert die Auswertung eines MU-Knotens. Die Hilfsfunktion
pow_sum speichert dabei sowohl \(B_i^m\) als auch \(G_i(m)\).
Die C++-, Python- und Java-Datei sind strukturell praktisch identisch. Zuerst werden p_count und
s_count memoisiert, dann liefert find_length_for_index die richtige Länge. Anschließend
baut select_node nur einen symbolischen Ausdrucks-DAG für den gesuchten Faktor auf.
WordBuilder kennt vier Knotentypen: leer, Blatt, Konkatenation und Morphismusanwendung. Die Methoden
prefix, suffix und middle realisieren die Abbildungen hinter dem
\(O1/E/O0\)-Split. Am Ende berechnet get_eval die Werte \(V_i\) pro Knoten, und
compute_A_mod gibt \(V_0\) zurück. Die C++-Version überprüft zusätzlich, dass
\(A(100)=3251\) und \(A(1000)=80852364498\) korrekt reproduziert werden.
Da jede Rekursion ihr Argument halbiert, berührt die Berechnung von \(p(\ell)\) oder \(s(\ell)\) nur
\(O(\log \ell)\) memoisierten Zustände. Die Längensuche für \(A(N)\) benötigt \(O(\log N)\) Aufrufe von
count_upto. Danach steigt select_node über \(O(\log \ell)\) Ebenen rekursiv ab, und die
Knotenauswertung arbeitet mit einer festen Basistabelle der Größe 64. Insgesamt wird jede Anfrage also in
polylogarithmischer Zeit und mit \(O(\log \ell)\) symbolischem Speicher gelöst, statt astronomisch viele Faktoren
zu erzeugen.
\(t=0110100110010110\ldots\) sonsuz Thue-Morse sözcüğü olsun; bu sözcük \(\mu:0\mapsto01,\;1\mapsto10\) morfizmasının sabit noktasıdır. Her \(\ell\) uzunluğu için \(T_\ell\), \(t\) içinde görülen farklı uzunluk-\(\ell\) faktörlerin kümesi olsun. \(T_\ell\) leksikografik olarak sıralanır, başı \(1\) olanlar tutulur ve bu filtrelenmiş listeler \(\ell=1,2,3,\ldots\) için art arda eklenir. Her seçilmiş sözcük ikilik tamsayı olarak okununca \(A(1),A(2),\ldots\) dizisi elde edilir. Hesaplanması istenen değer
$$\sum_{k=1}^{18} A(10^k) \pmod{10^9}$$
ifadesidir.
Şunu tanımlayalım:
$$p(\ell)=|T_\ell|.$$
Çözüm dosyaları Thue-Morse alt sözcük karmaşıklığı için şu başlangıç değerlerini kullanır:
$$p(1)=2,\qquad p(2)=4,\qquad p(3)=6,$$
ve \(n\ge 2\) için
$$p(2n)=p(n)+p(n+1),\qquad p(2n+1)=2p(n+1).$$
Ardından kümülatif toplam
$$s(\ell)=\sum_{j=1}^{\ell} p(j)$$
tanımlanır. Kod şu türetilmiş bağıntıları önbelleğe alır:
$$s(2n)=3s(n)+s(n+1)-8,\qquad s(2n+1)=4s(n)+3p(n+1)-8.$$
Bu neden önemlidir? Çünkü Thue-Morse sözcüğü bit tümleyeni altında kapalıdır: \(w\in T_\ell\) ise \(\overline{w}\in T_\ell\) de vardır. Boş olmayan hiçbir ikilik sözcük kendi tümleyenine eşit değildir; dolayısıyla faktörler biri \(0\) ile, diğeri \(1\) ile başlayan çiftler halinde gelir. Böylece her uzunlukta faktörlerin tam yarısı \(1\) ile başlar ve Euler dizisinde \(\ell\) uzunluğuna kadar gelen terim sayısı
$$\operatorname{count\_upto}(\ell)=\frac{s(\ell)}{2}$$
olur.
Verilen \(N\) için program önce
$$\frac{s(\ell)}{2}\ge N$$
şartını sağlayan en küçük \(\ell\) değerini bulur. Bunun için önce üst sınır iki katına çıkarılır, sonra ikili arama yapılır. \(\ell\) bulunduktan sonra, sabit bu uzunluk içindeki sıra
$$k=N-\operatorname{count\_upto}(\ell-1)$$
şeklindedir.
\(T_\ell\) kümesinin tam leksikografik sıralamasında önce başı \(0\) olanlar, sonra başı \(1\) olanlar gelir. Bu yüzden aranan faktör, uzunluğu \(\ell\) olan tüm faktörler arasında
$$\frac{p(\ell)}{2}+k$$
numaralı öğedir. Bütün dillerde görülen
$$\texttt{offset}=p(\ell)/2+k$$
satırı tam olarak bunu yapar.
Zor kısım, \(\texttt{offset}\)-inci faktörü bütün faktörleri üretmeden seçmektir. Uygulamalar \(1,2,3\) uzunluklarında durur; bu uzunluklar için faktör kümeleri doğrudan verilidir:
$$T_1=\{0,1\},\qquad T_2=\{00,01,10,11\},\qquad T_3=\{001,010,011,100,101,110\}.$$
\(\ell\ge 4\) için çözüm, \(\mu\) morfizmasının 2 harfli bloklarına göre oluşan benzersiz okuma çerçevesini kullanır. Her faktör ya tam bir \(\mu\)-blok sınırında başlar ya da bir karakter kaymış başlar. Kaynak koddaki \(O1\), \(E\) ve \(O0\) sınıfları buradan doğar.
\(\ell=2n\) olsun. Bir faktör çift konumlu blok sınırında başlıyorsa tam olarak bir \(u\in T_n\) için \(\mu(u)\) biçimindedir. Bu orta sınıfı verir:
$$E(u)=\mu(u),\qquad u\in T_n,$$
ve bu sınıfın büyüklüğü \(p(n)\)'dir.
Faktör bir karakter sonra başlıyorsa bir \(\mu\)-blok içinde başlar ve başka bir \(\mu\)-blok içinde biter. \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\) atası için kodun kullandığı dönüşüm
$$\operatorname{OE}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_n)\,a_{n+1}$$
şeklindedir. \(a_1=1\) ise çıktı \(0\) ile, \(a_1=0\) ise \(1\) ile başlar. Bu yüzden uzunluğu \(2n\) olan tüm faktörlerin leksikografik sırası üç bitişik bloğa ayrılır:
$$O1,\qquad E,\qquad O0,$$
ve blok boyutları
$$\frac{p(n+1)}{2},\qquad p(n),\qquad \frac{p(n+1)}{2}$$
olur.
\(\ell=4\) için somut liste
$$0010,0011,0100 \mid 0101,0110,1001,1010 \mid 1011,1100,1101$$
şeklindedir; soldan sağa \(O1\), \(E\), \(O0\) sınıfları görülür.
\(\ell=2n+1\) olsun. Yine iki hizalama türü vardır; fakat bu kez tek konumdan başlayan faktör sadece soldaki blok sınırını, çift konumdan başlayan faktör ise sadece sağdaki blok sınırını keser. \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\) için kod
$$\operatorname{OO}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_{n+1}),$$
$$\operatorname{EO}(a)=\mu(a_1a_2\cdots a_n)\,a_{n+1}$$
dönüşümlerini kullanır.
Leksikografik sıra yine
$$O1,\qquad E,\qquad O0$$
şeklindedir; bu kez blok boyutları
$$\frac{p(n+1)}{2},\qquad p(n+1),\qquad \frac{p(n+1)}{2}$$
olur. Böylece özyinelemeli seçimde yalnızca \(p(n)\) ve \(p(n+1)\) değerleri hangi dala gidileceğini belirlemeye yeter.
Seçilen faktör çok uzun olabileceği için program normal ikilik sayıyı hiç açıkça kurmaz. Bunun yerine
$$M=10^9,\qquad B_i=2^{2^i}\bmod M$$
tanımlanır ve \(V_i(w)\), \(w\) sözcüğünün tabanı \(B_i\) olan değeri olarak alınır. Özellikle \(V_0(w)\), sıradan ikilik değerin \(M\) modundaki karşılığıdır.
Birleştirme için standart özdeşlik
$$V_i(uv)=V_i(u)\,B_i^{|v|}+V_i(v)$$
geçerlidir. Morfizmada tek bir \(\mu(c)\) bloğunun değeri
$$V_i(\mu(c))=1+(B_i-1)c,\qquad c\in\{0,1\}$$
olur. Dolayısıyla \(w=c_1c_2\cdots c_m\) için
$$V_i(\mu(w))=\sum_{j=1}^{m} B_i^{m-j}\bigl(1+(B_i-1)c_j\bigr).$$
Sabit kısım ile rakamlara bağlı kısım ayrıldığında
$$V_i(\mu(w))=G_{i+1}(m)+(B_i-1)V_{i+1}(w)$$
elde edilir; burada
$$G_j(m)=\sum_{r=0}^{m-1} B_j^r.$$
MU düğümünün değerlendirmesi tam olarak bu formülü uygular. pow_sum hem \(B_i^m\) hem de
\(G_i(m)\) değerlerini önbelleğe alır.
C++, Python ve Java çözümleri aynı iskelete sahiptir. Önce p_count ve s_count için
önbellek kurulur, ardından find_length_for_index doğru uzunluğu bulur. Sonra
select_node, istenen faktörün sadece sembolik bir DAG gösterimini inşa eder. WordBuilder
dört düğüm tipi kullanır: boş, yaprak, birleştirme ve morfizma uygulaması. prefix, suffix
ve middle yardımcıları \(O1/E/O0\) ayrımındaki ata-çocuk dönüşümlerini gerçekleştirir. Son olarak
get_eval her düğüm için \(V_i\) değerlerini hesaplar ve compute_A_mod sonucu \(V_0\)
olarak döndürür. C++ sürümü ayrıca \(A(100)=3251\) ve \(A(1000)=80852364498\) kontrollerini içerir.
Her bağıntı argümanı ikiye böldüğü için \(p(\ell)\) veya \(s(\ell)\) hesabı yalnızca \(O(\log \ell)\) adet
önbelleklenmiş duruma dokunur. \(A(N)\) için uzunluk araması \(O(\log N)\) adet count_upto çağrısı
gerektirir. Daha sonra select_node \(O(\log \ell)\) derinlikte aşağı iner ve düğüm değerlendirmesi
sabit boyutlu 64 elemanlı bir taban tablosu ile çalışır. Sonuç olarak her sorgu çoklu logaritmik zamanda ve
\(O(\log \ell)\) sembolik bellekle çözülür; bu, bütün faktörleri üretmeye göre çok daha küçüktür.
Sea \(t=0110100110010110\ldots\) la palabra infinita de Thue-Morse, punto fijo del morfismo \(\mu:0\mapsto01,\;1\mapsto10\). Para cada longitud \(\ell\), sea \(T_\ell\) el conjunto de factores distintos de \(t\) de longitud \(\ell\). Se ordena \(T_\ell\) lexicográficamente, se conservan solo las palabras que empiezan por \(1\), y luego se concatenan esas listas filtradas para \(\ell=1,2,3,\ldots\). Al interpretar cada palabra seleccionada como un entero binario, se obtiene la sucesión \(A(1),A(2),\ldots\). El objetivo es calcular
$$\sum_{k=1}^{18} A(10^k) \pmod{10^9}.$$
Definimos
$$p(\ell)=|T_\ell|.$$
Los programas usan los valores iniciales
$$p(1)=2,\qquad p(2)=4,\qquad p(3)=6,$$
y, para \(n\ge 2\), las recurrencias
$$p(2n)=p(n)+p(n+1),\qquad p(2n+1)=2p(n+1).$$
Además se define el acumulado
$$s(\ell)=\sum_{j=1}^{\ell} p(j),$$
para el cual el código memoiza
$$s(2n)=3s(n)+s(n+1)-8,\qquad s(2n+1)=4s(n)+3p(n+1)-8.$$
La simetría clave es que la palabra de Thue-Morse es estable bajo complemento bit a bit: si \(w\in T_\ell\), también \(\overline{w}\in T_\ell\). Ninguna palabra binaria no vacía coincide con su propio complemento, así que los factores se emparejan en una palabra que empieza por \(0\) y otra que empieza por \(1\). Por tanto, exactamente la mitad empieza por \(1\), y el número de términos válidos hasta la longitud \(\ell\) es
$$\operatorname{count\_upto}(\ell)=\frac{s(\ell)}{2}.$$
Dado \(N\), el algoritmo busca primero la menor longitud \(\ell\) tal que
$$\frac{s(\ell)}{2}\ge N.$$
Esto se hace duplicando una cota superior y luego aplicando búsqueda binaria. Una vez conocida \(\ell\), el rango de la palabra buscada dentro de la lista filtrada de longitud fija es
$$k=N-\operatorname{count\_upto}(\ell-1).$$
En la ordenación lexicográfica completa de \(T_\ell\), primero aparecen todas las palabras que empiezan por \(0\) y después todas las que empiezan por \(1\). Por eso el factor deseado es el número
$$\frac{p(\ell)}{2}+k$$
dentro de la lista total de factores de longitud \(\ell\). De ahí sale la instrucción
$$\texttt{offset}=p(\ell)/2+k.$$
La parte delicada consiste en escoger el factor número \(\texttt{offset}\) sin enumerar todos los factores. Para las longitudes \(1,2,3\), los conjuntos de factores están almacenados explícitamente:
$$T_1=\{0,1\},\qquad T_2=\{00,01,10,11\},\qquad T_3=\{001,010,011,100,101,110\}.$$
Para \(\ell\ge 4\), la solución usa el marco de lectura único impuesto por los bloques de longitud 2 del morfismo \(\mu\). Un factor empieza o bien justo en una frontera de bloque, o bien desplazado un símbolo. Eso produce las tres clases \(O1\), \(E\) y \(O0\) que aparecen en el código.
Sea \(\ell=2n\). Si un factor empieza en una frontera par, entonces es exactamente \(\mu(u)\) para un único \(u\in T_n\). Esa es la clase central
$$E(u)=\mu(u),\qquad u\in T_n,$$
de tamaño \(p(n)\).
Si el factor empieza un símbolo más tarde, arranca dentro de un bloque \(\mu\) y termina dentro de otro. Para un ancestro \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\), la transformación usada por el programa es
$$\operatorname{OE}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_n)\,a_{n+1}.$$
Cuando \(a_1=1\), el resultado empieza por \(0\); cuando \(a_1=0\), empieza por \(1\). Por eso el orden lexicográfico completo de los factores de longitud \(2n\) se divide en tres bloques consecutivos:
$$O1,\qquad E,\qquad O0,$$
con tamaños
$$\frac{p(n+1)}{2},\qquad p(n),\qquad \frac{p(n+1)}{2}.$$
Para \(\ell=4\), la lista concreta es
$$0010,0011,0100 \mid 0101,0110,1001,1010 \mid 1011,1100,1101.$$
Sea \(\ell=2n+1\). Vuelven a aparecer dos alineaciones, pero ahora un factor que empieza en posición impar cruza solo la frontera izquierda y uno que empieza en posición par cruza solo la derecha. Para \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\), el código utiliza
$$\operatorname{OO}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_{n+1}),$$
$$\operatorname{EO}(a)=\mu(a_1a_2\cdots a_n)\,a_{n+1}.$$
El orden vuelve a ser
$$O1,\qquad E,\qquad O0,$$
pero ahora con tamaños
$$\frac{p(n+1)}{2},\qquad p(n+1),\qquad \frac{p(n+1)}{2}.$$
De este modo, el selector recursivo puede decidir el bloque correcto usando solo \(p(n)\) y \(p(n+1)\).
El factor elegido puede ser muy largo, así que el programa nunca construye directamente su entero binario completo. En su lugar define
$$M=10^9,\qquad B_i=2^{2^i}\bmod M,$$
y \(V_i(w)\) como el valor de la palabra \(w\) leído en base \(B_i\). En particular, \(V_0(w)\) es exactamente el valor binario usual módulo \(M\).
La concatenación satisface
$$V_i(uv)=V_i(u)\,B_i^{|v|}+V_i(v).$$
Para el morfismo, un bloque \(\mu(c)\) tiene valor
$$V_i(\mu(c))=1+(B_i-1)c,\qquad c\in\{0,1\}.$$
Entonces, si \(w=c_1c_2\cdots c_m\),
$$V_i(\mu(w))=\sum_{j=1}^{m} B_i^{m-j}\bigl(1+(B_i-1)c_j\bigr).$$
Separando la parte constante de la parte dependiente de los bits, se obtiene
$$V_i(\mu(w))=G_{i+1}(m)+(B_i-1)V_{i+1}(w),$$
donde
$$G_j(m)=\sum_{r=0}^{m-1} B_j^r.$$
Esa es exactamente la identidad que implementa la evaluación de un nodo MU. La función
pow_sum memoiza tanto \(B_i^m\) como \(G_i(m)\).
Las versiones en C++, Python y Java siguen la misma estructura. Primero memoizan p_count y
s_count, luego usan find_length_for_index para localizar la longitud correcta y, por
último, llaman a select_node para construir solo un DAG simbólico del factor pedido.
WordBuilder maneja cuatro tipos de nodos: vacío, hoja, concatenación y aplicación del morfismo. Los
métodos prefix, suffix y middle implementan las transformaciones entre
ancestro y descendiente que sostienen el corte \(O1/E/O0\). Después, get_eval calcula una sola vez los
valores \(V_i\) de cada nodo, y compute_A_mod devuelve \(V_0\). El archivo C++ además verifica que
\(A(100)=3251\) y \(A(1000)=80852364498\).
Como cada recurrencia divide su argumento aproximadamente por 2, calcular \(p(\ell)\) o \(s(\ell)\) toca solo
\(O(\log \ell)\) estados memoizados. La búsqueda de longitud para \(A(N)\) requiere \(O(\log N)\) llamadas a
count_upto. Después, select_node baja por \(O(\log \ell)\) niveles recursivos y la
evaluación trabaja con una tabla base fija de tamaño 64. En consecuencia, cada consulta se resuelve en tiempo
polilogarítmico y con \(O(\log \ell)\) memoria simbólica, muy lejos del coste de enumerar todos los factores.
设 \(t=0110100110010110\ldots\) 为无限 Thue-Morse 单词，它是形态替换 \(\mu:0\mapsto01,\;1\mapsto10\) 的不动点。对每个长度 \(\ell\)，记 \(T_\ell\) 为 \(t\) 中所有不同的长度 \(\ell\) 因子集合。把 \(T_\ell\) 按字典序排序，只保留首位为 \(1\) 的单词，再按 \(\ell=1,2,3,\ldots\) 的顺序把这些列表依次拼接。将每个保留下来的单词看作二进制整数，就得到序列 \(A(1),A(2),\ldots\)。题目要求计算
$$\sum_{k=1}^{18} A(10^k) \pmod{10^9}.$$
记
$$p(\ell)=|T_\ell|.$$
程序使用的初值为
$$p(1)=2,\qquad p(2)=4,\qquad p(3)=6,$$
并在 \(n\ge 2\) 时使用递推
$$p(2n)=p(n)+p(n+1),\qquad p(2n+1)=2p(n+1).$$
再定义前缀累计量
$$s(\ell)=\sum_{j=1}^{\ell} p(j),$$
代码记忆化的则是
$$s(2n)=3s(n)+s(n+1)-8,\qquad s(2n+1)=4s(n)+3p(n+1)-8.$$
这里最关键的是补码对称性。Thue-Morse 单词在按位取反下封闭：如果 \(w\in T_\ell\)，那么 \(\overline{w}\in T_\ell\) 也成立。任意非空二进制单词都不可能等于自己的补码，因此长度 \(\ell\) 的所有因子 可以两两配对，每一对中一个以 \(0\) 开头，另一个以 \(1\) 开头。所以首位为 \(1\) 的因子恰好占一半， 长度不超过 \(\ell\) 的有效 Euler 项数就是
$$\operatorname{count\_upto}(\ell)=\frac{s(\ell)}{2}.$$
给定 \(N\)，程序首先寻找满足
$$\frac{s(\ell)}{2}\ge N$$
的最小长度 \(\ell\)。实现方式是先不断翻倍上界，再做二分查找。长度确定后，该单词在“固定长度且首位为 \(1\)”的列表中的局部排名为
$$k=N-\operatorname{count\_upto}(\ell-1).$$
而在 \(T_\ell\) 的完整字典序中，所有首位为 \(0\) 的因子一定排在前半段，首位为 \(1\) 的因子排在后半段。 因此真正要选的是长度 \(\ell\) 的全部因子里第
$$\frac{p(\ell)}{2}+k$$
个元素，这正是代码里的
$$\texttt{offset}=p(\ell)/2+k$$
所表示的含义。
难点在于不显式枚举全部因子，就直接取出第 \(\texttt{offset}\) 个因子。程序在长度 \(1,2,3\) 时停止递归， 因为这些集合已经直接写出：
$$T_1=\{0,1\},\qquad T_2=\{00,01,10,11\},\qquad T_3=\{001,010,011,100,101,110\}.$$
对于 \(\ell\ge 4\)，实现利用 \(\mu\) 的长度为 2 的块结构。每个因子要么正好从块边界开始，要么向后偏移一个 字符开始。源代码中的三类 \(O1\)、\(E\)、\(O0\) 就来自这种分类。
令 \(\ell=2n\)。如果因子从偶数块边界开始，那么它必然恰好等于某个唯一 \(u\in T_n\) 的形态像 \(\mu(u)\)。这给出中间那一类
$$E(u)=\mu(u),\qquad u\in T_n,$$
其大小为 \(p(n)\)。
如果因子从后移一位的位置开始，它就会在一个 \(\mu\)-块内部开始，又在另一个 \(\mu\)-块内部结束。对祖先 \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\)，代码使用的构造是
$$\operatorname{OE}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_n)\,a_{n+1}.$$
当 \(a_1=1\) 时，结果首位是 \(0\)；当 \(a_1=0\) 时，结果首位是 \(1\)。因此长度 \(2n\) 的全部因子在 字典序中分成三个连续区间：
$$O1,\qquad E,\qquad O0,$$
对应大小为
$$\frac{p(n+1)}{2},\qquad p(n),\qquad \frac{p(n+1)}{2}.$$
\(\ell=4\) 时的十个因子恰好是
$$0010,0011,0100 \mid 0101,0110,1001,1010 \mid 1011,1100,1101,$$
中间竖线正对应 \(O1\)、\(E\)、\(O0\) 三段。
令 \(\ell=2n+1\)。这时仍有两种对齐方式，但奇起点的因子只跨过左侧块边界，偶起点的因子只跨过右侧块边界。 对 \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\)，程序使用
$$\operatorname{OO}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_{n+1}),$$
$$\operatorname{EO}(a)=\mu(a_1a_2\cdots a_n)\,a_{n+1}.$$
字典序同样是
$$O1,\qquad E,\qquad O0,$$
但三个区间的大小变成
$$\frac{p(n+1)}{2},\qquad p(n+1),\qquad \frac{p(n+1)}{2}.$$
因此递归选择时，只需要知道 \(p(n)\) 和 \(p(n+1)\) 就能判断目标因子落在哪一段。
目标因子可能非常长，所以程序从不直接构造其完整二进制整数。它定义
$$M=10^9,\qquad B_i=2^{2^i}\bmod M,$$
并把 \(V_i(w)\) 定义为单词 \(w\) 在基数 \(B_i\) 下的数值。特别地，\(V_0(w)\) 就是普通二进制值模 \(M\) 的结果。
连接两个单词时有
$$V_i(uv)=V_i(u)\,B_i^{|v|}+V_i(v).$$
对于形态替换，一个块 \(\mu(c)\) 的值满足
$$V_i(\mu(c))=1+(B_i-1)c,\qquad c\in\{0,1\}.$$
于是若 \(w=c_1c_2\cdots c_m\)，就有
$$V_i(\mu(w))=\sum_{j=1}^{m} B_i^{m-j}\bigl(1+(B_i-1)c_j\bigr).$$
把常数项和与比特相关的部分拆开，得到
$$V_i(\mu(w))=G_{i+1}(m)+(B_i-1)V_{i+1}(w),$$
其中
$$G_j(m)=\sum_{r=0}^{m-1} B_j^r.$$
这正是 MU 节点求值时使用的恒等式。辅助函数 pow_sum 同时缓存 \(B_i^m\) 与
\(G_i(m)\)。
C++、Python 和 Java 三个版本的结构几乎完全一致。它们先记忆化 p_count 与
s_count，再用 find_length_for_index 找到目标长度，然后调用
select_node 只构造所需因子的一个符号 DAG。WordBuilder 有四种节点类型：
空节点、叶子、连接、以及形态替换应用。prefix、suffix、middle
三个辅助函数负责实现 \(O1/E/O0\) 分裂中的祖先到后代映射。最后 get_eval 统一计算每个节点
的 \(V_i\) 值，而 compute_A_mod 返回的就是 \(V_0\)。C++ 版本还额外验证了
\(A(100)=3251\) 与 \(A(1000)=80852364498\)。
由于每一步递推都会把参数大致减半，计算 \(p(\ell)\) 或 \(s(\ell)\) 只会访问 \(O(\log \ell)\) 个记忆化状态。
对 \(A(N)\) 做长度定位需要 \(O(\log N)\) 次 count_upto 调用。之后
select_node 的递归深度为 \(O(\log \ell)\)，而求值阶段使用的基数表大小固定为 64。于是每次
查询都能在多对数时间内完成，额外符号内存为 \(O(\log \ell)\)，远小于显式生成全部因子的成本。
Пусть \(t=0110100110010110\ldots\) — бесконечное слово Туэ-Морса, то есть неподвижная точка морфизма \(\mu:0\mapsto01,\;1\mapsto10\). Для каждой длины \(\ell\) обозначим через \(T_\ell\) множество всех различных факторов слова \(t\) длины \(\ell\). Множество \(T_\ell\) упорядочивается лексикографически; затем сохраняются только слова, начинающиеся с \(1\), и такие списки склеиваются для \(\ell=1,2,3,\ldots\). Если каждое выбранное слово трактовать как двоичное число, получается последовательность \(A(1),A(2),\ldots\). Требуется вычислить
$$\sum_{k=1}^{18} A(10^k) \pmod{10^9}.$$
Обозначим
$$p(\ell)=|T_\ell|.$$
В решении используются начальные значения
$$p(1)=2,\qquad p(2)=4,\qquad p(3)=6,$$
а для \(n\ge 2\) — рекуррентные формулы
$$p(2n)=p(n)+p(n+1),\qquad p(2n+1)=2p(n+1).$$
Также вводится накопленная функция
$$s(\ell)=\sum_{j=1}^{\ell} p(j),$$
для которой код мемоизирует
$$s(2n)=3s(n)+s(n+1)-8,\qquad s(2n+1)=4s(n)+3p(n+1)-8.$$
Ключевая симметрия состоит в том, что слово Туэ-Морса замкнуто относительно побитового дополнения: из \(w\in T_\ell\) следует \(\overline{w}\in T_\ell\). Ни одно непустое двоичное слово не совпадает со своим дополнением, поэтому факторы распадаются на пары: одно слово начинается с \(0\), другое — с \(1\). Следовательно, ровно половина факторов длины \(\ell\) начинается с \(1\), и число допустимых членов Euler-последовательности до длины \(\ell\) равно
$$\operatorname{count\_upto}(\ell)=\frac{s(\ell)}{2}.$$
Для данного \(N\) программа сначала ищет минимальную длину \(\ell\), для которой
$$\frac{s(\ell)}{2}\ge N.$$
Это делается через удвоение верхней границы и последующий бинарный поиск. Когда длина найдена, локальный ранг в отфильтрованном списке фиксированной длины равен
$$k=N-\operatorname{count\_upto}(\ell-1).$$
В полном лексикографическом порядке множества \(T_\ell\) сначала идут все слова с первым битом \(0\), а затем все слова с первым битом \(1\). Поэтому нужный фактор — это
$$\frac{p(\ell)}{2}+k$$
й элемент среди всех факторов длины \(\ell\). Именно это выражает строка
$$\texttt{offset}=p(\ell)/2+k.$$
Главная трудность — выбрать фактор с номером \(\texttt{offset}\), не перечисляя все факторы явно. Для длин \(1,2,3\) множества заданы непосредственно:
$$T_1=\{0,1\},\qquad T_2=\{00,01,10,11\},\qquad T_3=\{001,010,011,100,101,110\}.$$
При \(\ell\ge 4\) решение использует единственную рамку чтения, возникающую из блоков длины 2 морфизма \(\mu\). Каждый фактор либо начинается на границе блока, либо со сдвигом на один символ. Так появляются три класса \(O1\), \(E\) и \(O0\), обозначенные в исходниках.
Пусть \(\ell=2n\). Если фактор начинается на чётной границе блока, он в точности равен \(\mu(u)\) для единственного \(u\in T_n\). Это средний класс
$$E(u)=\mu(u),\qquad u\in T_n,$$
размера \(p(n)\).
Если же фактор начинается на один символ позже, он начинается внутри одного \(\mu\)-блока и заканчивается внутри другого. Для предка \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\) код использует отображение
$$\operatorname{OE}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_n)\,a_{n+1}.$$
При \(a_1=1\) результат начинается с \(0\), при \(a_1=0\) — с \(1\). Поэтому лексикографический порядок факторов длины \(2n\) распадается на три последовательных блока
$$O1,\qquad E,\qquad O0,$$
с размерами
$$\frac{p(n+1)}{2},\qquad p(n),\qquad \frac{p(n+1)}{2}.$$
Например, при \(\ell=4\) получаем
$$0010,0011,0100 \mid 0101,0110,1001,1010 \mid 1011,1100,1101,$$
то есть ровно разбиение \(O1\), \(E\), \(O0\).
Пусть \(\ell=2n+1\). Снова существуют две ориентации, но теперь фактор с нечётным стартом пересекает только левую границу блока, а фактор с чётным стартом — только правую. Для \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\) программа использует
$$\operatorname{OO}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_{n+1}),$$
$$\operatorname{EO}(a)=\mu(a_1a_2\cdots a_n)\,a_{n+1}.$$
Лексикографический порядок снова имеет вид
$$O1,\qquad E,\qquad O0,$$
но теперь размеры блоков равны
$$\frac{p(n+1)}{2},\qquad p(n+1),\qquad \frac{p(n+1)}{2}.$$
Именно поэтому рекурсивному селектору достаточно знать значения \(p(n)\) и \(p(n+1)\), чтобы понять, в какой блок попадает нужный фактор.
Выбранный фактор может быть очень длинным, поэтому программа не строит полное двоичное число напрямую. Вместо этого вводятся
$$M=10^9,\qquad B_i=2^{2^i}\bmod M,$$
а \(V_i(w)\) обозначает значение слова \(w\) в системе счисления с основанием \(B_i\). В частности, \(V_0(w)\) — это обычное двоичное значение по модулю \(M\).
Для конкатенации верно
$$V_i(uv)=V_i(u)\,B_i^{|v|}+V_i(v).$$
Для морфизма один блок \(\mu(c)\) имеет значение
$$V_i(\mu(c))=1+(B_i-1)c,\qquad c\in\{0,1\}.$$
Следовательно, если \(w=c_1c_2\cdots c_m\), то
$$V_i(\mu(w))=\sum_{j=1}^{m} B_i^{m-j}\bigl(1+(B_i-1)c_j\bigr).$$
Выделяя постоянную часть и часть, зависящую от цифр, получаем
$$V_i(\mu(w))=G_{i+1}(m)+(B_i-1)V_{i+1}(w),$$
где
$$G_j(m)=\sum_{r=0}^{m-1} B_j^r.$$
Именно это тождество реализует вычисление узла MU. Вспомогательная функция pow_sum
кэширует и \(B_i^m\), и \(G_i(m)\).
Версии на C++, Python и Java устроены одинаково. Сначала мемоизируются p_count и
s_count, затем функция find_length_for_index находит правильную длину. После этого
select_node строит только символический DAG для нужного фактора. WordBuilder использует
четыре типа узлов: пустой, лист, конкатенация и применение морфизма. Методы prefix,
suffix и middle реализуют преобразования между предком и потомком, лежащие в основе
разбиения \(O1/E/O0\). Затем get_eval вычисляет значения \(V_i\) для каждого узла, а
compute_A_mod возвращает \(V_0\). В файле на C++ дополнительно проверяется, что
\(A(100)=3251\) и \(A(1000)=80852364498\).
Поскольку каждая рекурсия делит аргумент примерно пополам, вычисление \(p(\ell)\) и \(s(\ell)\) посещает лишь
\(O(\log \ell)\) мемоизированных состояний. Поиск длины для \(A(N)\) требует \(O(\log N)\) вызовов
count_upto. Затем select_node проходит \(O(\log \ell)\) уровней рекурсии, а вычислитель
значений работает с фиксированной таблицей оснований размера 64. Поэтому каждый запрос обрабатывается за
полилогарифмическое время и \(O(\log \ell)\) символической памяти, без перебора гигантского числа факторов.
لتكن \(t=0110100110010110\ldots\) هي كلمة ثو-مورس اللانهائية، أي نقطة التثبيت للمورفزم \(\mu:0\mapsto01,\;1\mapsto10\). ولكل طول \(\ell\)، نرمز بـ \(T_\ell\) إلى مجموعة جميع المقاطع المختلفة من \(t\) ذات الطول \(\ell\). نرتب \(T_\ell\) ترتيبًا معجميًا، ثم نحتفظ فقط بالكلمات التي تبدأ بالبت \(1\)، وبعد ذلك نلصق هذه القوائم المصفاة لجميع \(\ell=1,2,3,\ldots\). وعند تفسير كل كلمة مختارة على أنها عدد ثنائي نحصل على المتتالية \(A(1),A(2),\ldots\). والمطلوب حساب
$$\sum_{k=1}^{18} A(10^k) \pmod{10^9}.$$
نعرّف
$$p(\ell)=|T_\ell|.$$
وتستعمل الحلول القيم الابتدائية
$$p(1)=2,\qquad p(2)=4,\qquad p(3)=6,$$
ومع \(n\ge 2\) تستعمل العلاقتين
$$p(2n)=p(n)+p(n+1),\qquad p(2n+1)=2p(n+1).$$
ثم نعرّف المجموع التراكمي
$$s(\ell)=\sum_{j=1}^{\ell} p(j),$$
ويقوم الكود بتخزين العلاقتين المشتقتين
$$s(2n)=3s(n)+s(n+1)-8,\qquad s(2n+1)=4s(n)+3p(n+1)-8.$$
الفكرة الجوهرية هنا هي تناظر المتمّم. فكلمة ثو-مورس مغلقة تحت قلب كل بت: إذا كان \(w\in T_\ell\) فإن \(\overline{w}\in T_\ell\) أيضًا. ولا توجد كلمة ثنائية غير فارغة تساوي متممها، لذلك تتوزع المقاطع في أزواج: واحدة تبدأ بـ \(0\) وأخرى تبدأ بـ \(1\). ومن ثم فإن نصف المقاطع تمامًا يبدأ بـ \(1\)، وعدد العناصر المقبولة في متتالية Euler حتى الطول \(\ell\) هو
$$\operatorname{count\_upto}(\ell)=\frac{s(\ell)}{2}.$$
لعدد معطى \(N\)، تبحث الخوارزمية أولًا عن أصغر طول \(\ell\) يحقق
$$\frac{s(\ell)}{2}\ge N.$$
ويتم ذلك بتكبير حد علوي بالضرب في 2 ثم إجراء بحث ثنائي. وبعد معرفة \(\ell\)، تكون رتبة الكلمة المطلوبة داخل القائمة المصفاة ذات الطول الثابت مساوية لـ
$$k=N-\operatorname{count\_upto}(\ell-1).$$
أما في الترتيب المعجمي الكامل لعناصر \(T_\ell\)، فإن جميع الكلمات التي تبدأ بـ \(0\) تأتي أولًا ثم تأتي الكلمات التي تبدأ بـ \(1\). لهذا السبب يكون العامل المطلوب هو العنصر رقم
$$\frac{p(\ell)}{2}+k$$
ضمن جميع عوامل الطول \(\ell\). وهذا هو معنى السطر
$$\texttt{offset}=p(\ell)/2+k.$$
الجزء الصعب هو اختيار العامل رقم \(\texttt{offset}\) من دون تعداد كل العوامل. عند الأطوال \(1,2,3\) تتوقف العودية لأن القوائم الأساسية مخزنة صراحة:
$$T_1=\{0,1\},\qquad T_2=\{00,01,10,11\},\qquad T_3=\{001,010,011,100,101,110\}.$$
أما عندما \(\ell\ge 4\)، فإن الحل يعتمد على إطار القراءة الفريد الناتج عن كتل \(\mu\) ذات الطول 2. فكل عامل يبدأ إما على حد كتلة تمامًا، أو بعده بحرف واحد. ومن هنا تنشأ الفئات الثلاث \(O1\) و\(E\) و\(O0\) المستعملة في الشفرة.
لنفرض أن \(\ell=2n\). إذا بدأ العامل عند حد كتلة زوجي، فإنه يساوي بالضبط \(\mu(u)\) لعامل وحيد \(u\in T_n\). وهذه هي الفئة الوسطى
$$E(u)=\mu(u),\qquad u\in T_n,$$
وحجمها \(p(n)\).
أما إذا بدأ العامل بعد حد الكتلة بمقدار رمز واحد، فإنه يبدأ داخل كتلة \(\mu\) وينتهي داخل كتلة أخرى. ولأصل \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\) تستعمل الشفرة التحويل
$$\operatorname{OE}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_n)\,a_{n+1}.$$
إذا كان \(a_1=1\) بدأ الناتج بـ \(0\)، وإذا كان \(a_1=0\) بدأ بـ \(1\). لذلك ينقسم الترتيب المعجمي الكامل لعوامل الطول \(2n\) إلى ثلاثة كتل متتالية:
$$O1,\qquad E,\qquad O0,$$
وأحجام هذه الكتل هي
$$\frac{p(n+1)}{2},\qquad p(n),\qquad \frac{p(n+1)}{2}.$$
وعند \(\ell=4\) نحصل مثلًا على
$$0010,0011,0100 \mid 0101,0110,1001,1010 \mid 1011,1100,1101,$$
وهو بالضبط التقسيم \(O1\) ثم \(E\) ثم \(O0\).
لنفرض أن \(\ell=2n+1\). هنا أيضًا توجد محاذاتان، لكن العامل الذي يبدأ من موضع فردي يقطع الحد الأيسر فقط، بينما العامل الذي يبدأ من موضع زوجي يقطع الحد الأيمن فقط. ولـ \(a=a_1a_2\cdots a_{n+1}\in T_{n+1}\) تستعمل الشفرة
$$\operatorname{OO}(a)=(1-a_1)\,\mu(a_2a_3\cdots a_{n+1}),$$
$$\operatorname{EO}(a)=\mu(a_1a_2\cdots a_n)\,a_{n+1}.$$
ويظل الترتيب المعجمي هو
$$O1,\qquad E,\qquad O0,$$
لكن أحجام الكتل تصبح
$$\frac{p(n+1)}{2},\qquad p(n+1),\qquad \frac{p(n+1)}{2}.$$
ولهذا يكفي أن تعرف الدالة العودية القيمتين \(p(n)\) و\(p(n+1)\) لتحديد الفرع الذي يحتوي العامل المطلوب.
قد يكون العامل المختار طويلًا جدًا، لذلك لا تبني الشفرة العدد الثنائي الكامل مباشرة. بدلًا من ذلك تعرّف
$$M=10^9,\qquad B_i=2^{2^i}\bmod M,$$
وتجعل \(V_i(w)\) قيمة الكلمة \(w\) عند قراءتها في الأساس \(B_i\). وبصورة خاصة فإن \(V_0(w)\) هو القيمة الثنائية المعتادة بترديد \(M\).
وللضم لدينا
$$V_i(uv)=V_i(u)\,B_i^{|v|}+V_i(v).$$
أما بالنسبة إلى المورفزم، فقيمة الكتلة الواحدة \(\mu(c)\) هي
$$V_i(\mu(c))=1+(B_i-1)c,\qquad c\in\{0,1\}.$$
وبالتالي إذا كانت \(w=c_1c_2\cdots c_m\)، فإن
$$V_i(\mu(w))=\sum_{j=1}^{m} B_i^{m-j}\bigl(1+(B_i-1)c_j\bigr).$$
وبفصل الجزء الثابت عن الجزء التابع للبتات نحصل على
$$V_i(\mu(w))=G_{i+1}(m)+(B_i-1)V_{i+1}(w),$$
حيث
$$G_j(m)=\sum_{r=0}^{m-1} B_j^r.$$
وهذه هي الهوية التي تنفذها بالضبط عملية تقييم العقدة MU. كما أن الدالة pow_sum تخزن
القيمتين \(B_i^m\) و\(G_i(m)\) معًا.
النسخ المكتوبة بـ C++ وPython وJava تتبع البنية نفسها. أولًا تُخزَّن قيم p_count و
s_count، ثم تستعمل find_length_for_index لإيجاد الطول الصحيح. بعد ذلك تبني
select_node فقط DAG رمزيًا للعامل المطلوب. ويدعم WordBuilder أربعة أنواع من العقد:
عقدة فارغة، ورقة، ضم، وتطبيق للمورفزم. وتقوم التوابع prefix وsuffix و
middle بتنفيذ التحويلات بين السلف والنسل التي تقف وراء التقسيم \(O1/E/O0\). ثم تحسب
get_eval قيم \(V_i\) لكل عقدة مرة واحدة، وتعيد compute_A_mod القيمة \(V_0\). كما أن
ملف C++ يحتوي اختبارات تحقق تؤكد أن \(A(100)=3251\) و\(A(1000)=80852364498\).
بما أن كل علاقة عودية تقسم الوسيط تقريبًا على 2، فإن حساب \(p(\ell)\) أو \(s(\ell)\) يزور فقط
\(O(\log \ell)\) من الحالات المخزنة. والبحث عن طول \(A(N)\) يحتاج إلى \(O(\log N)\) نداءات لـ
count_upto. وبعد ذلك تهبط select_node عبر \(O(\log \ell)\) مستويات عودية، بينما تعمل
عملية التقييم على جدول قواعد ثابت حجمه 64. لذا فإن كل استعلام يُعالج في زمن متعدد اللوغاريتم وباستهلاك
\(O(\log \ell)\) من الذاكرة الرمزية، بدلًا من تعداد عدد هائل من المقاطع صراحة.