An Ulam sequence \(U(a,b)\) starts with \(a\) and \(b\). Every later term is the smallest integer larger than the previous term that can be written in exactly one way as a sum of two distinct earlier terms. In this problem we must evaluate
$$S(k)=\sum_{n=2}^{10} u_k\bigl(U(2,2n+1)\bigr),$$
so the nine relevant sequences are \(U(2,5),U(2,7),\dots,U(2,21)\). The target index is enormous in the original problem, so a term-by-term generator is useless. The solution works only because this particular family of Ulam sequences has a highly constrained structure.
Fix one sequence \(U(2,v)\) with \(v=2n+1\) odd. The core idea is that the even terms become trivial, and once that happens the odd terms are governed by a linear recurrence over \(\mathbb{F}_2\).
For the nine values \(v=5,7,\dots,21\), the implementation exploits a specific fact about \(U(2,v)\): after the initial term \(2\), there is exactly one further even term, namely
$$E=2(v+1).$$
Beyond that point the new members are odd. This matters because every odd candidate \(x>E\) can only be formed as
$$x=2+(x-2),\qquad x=E+(x-E).$$
Odd numbers cannot come from odd plus odd, and there are no other even Ulam terms available. Therefore an odd number \(x>E\) enters the sequence exactly when one of \(x-2\) and \(x-E\) is already present and the other is not.
Define an indicator for odd membership by
$$b_t=\chi(2t+1),$$
where \(b_t=1\) if \(2t+1\) belongs to \(U(2,v)\), and \(b_t=0\) otherwise. Also write
$$g=v+1,\qquad E=2g.$$
For odd \(x=2t+1>E\), the previous observation becomes
$$\chi(x)=\chi(x-2)\oplus\chi(x-E),$$
which is the same as
$$b_t=b_{t-1}\oplus b_{t-g}\qquad (t\ge g).$$
So one window of \(g\) consecutive bits determines every later odd term. Instead of thinking about huge integers directly, we can think about a \(g\)-bit state evolving by a deterministic update rule.
For \(v=5\) we have \(g=6\) and \(E=12\). The beginning of the sequence is
$$2,5,7,9,11,12,13,15,19,23,\dots$$
Look at the odd numbers in the initial window \(\{1,3,5,7,9,11\}\). Their membership bits are
$$b_0,\dots,b_5=(0,0,1,1,1,1).$$
Now apply the recurrence \(b_t=b_{t-1}\oplus b_{t-6}\):
$$b_6=b_5\oplus b_0=1\oplus 0=1,$$
so \(13=2\cdot 6+1\) is in the sequence. Next,
$$b_7=b_6\oplus b_1=1\oplus 0=1,$$
so \(15\) is in. Then
$$b_8=b_7\oplus b_2=1\oplus 1=0,$$
so \(17\) is skipped, and
$$b_9=b_8\oplus b_3=0\oplus 1=1,$$
so \(19\) appears. This is exactly the pattern produced by the brute-force prefix and then continued by the fast method.
At step \(t\), the recurrence only needs the last \(g\) bits, for example the state
$$\bigl(b_{t-g+1},b_{t-g+2},\dots,b_t\bigr).$$
The next bit is determined by the oldest and newest entries, so the transition is deterministic. There are only \(2^g\) possible states, hence some state must repeat. Once the same \(g\)-bit state appears again, every later update repeats as well, so the odd-membership sequence has a finite preperiod followed by a pure cycle.
The full Ulam sequence is almost all odd, but the exceptional even term \(E\) must still be inserted at the correct position. Its index is
$$r_E=2+\#\{x<E:x\equiv 1 \pmod 2,\ x\in U(2,v)\}.$$
The first position is occupied by \(2\), then come all odd members below \(E\), and then \(E\) itself. Therefore
$$u_1(v)=2,\qquad u_{r_E}(v)=E,$$
and every other query is converted to an odd rank
$$r_{\mathrm{odd}}= \begin{cases} k-1,&k<r_E,\\ k-2,&k>r_E. \end{cases}$$
Prefix sums of the bit sequence tell how many odd Ulam numbers have appeared up to a given odd value. Once the preperiod length and the number of 1-bits per cycle are known, the algorithm can skip whole cycles arithmetically and then locate the exact odd value with one binary search.
The C++, Python, and Java implementations first generate only a short brute-force prefix, just far enough to know which odd numbers up to \(2g-1\) are members. That gives one complete seed window \(b_0,\dots,b_{g-1}\) and also determines how many odd members lie below the special even term \(E\).
From there the implementation builds a \(g\)-bit state, computes prefix counts of 1-bits, and stops using ordinary Ulam generation. All later odd membership decisions come from the XOR recurrence.
Each new bit updates the sliding \(g\)-bit state. The first repeated state gives the beginning and end of the eventual cycle. The implementation stores the number of odd members before the cycle, the number contributed by one cycle, and prefix counts inside the cycle itself.
To answer the query, the implementation handles the special cases \(2\) and \(E\), converts the requested position into an odd rank, skips as many full cycles as possible, and then binary-searches the relevant prefix table to recover the matching odd number \(2t+1\). The C++ and Java implementations do this independently for the nine values of \(v\) in parallel; the Python implementation applies the same logic serially.
For one sequence \(U(2,v)\), the main cost is cycle detection on the \(g=v+1\) bit states. In the worst case this takes \(O(2^g)\) time and \(O(2^g)\) memory for the table that records the first visit to each state. Here \(v\le 21\), so \(g\le 22\) and the state space is at most \(2^{22}=4{,}194{,}304\), which is entirely manageable.
After that preprocessing, finding \(u_k(v)\) is \(O(\log(P+\lambda))\), where \(P\) is the preperiod length and \(\lambda\) is the cycle length, because the remaining work is arithmetic plus one binary search on prefix sums. The full problem repeats this for only nine independent sequences and adds the results.
Eine Ulam-Folge \(U(a,b)\) beginnt mit \(a\) und \(b\). Jeder spätere Term ist die kleinste ganze Zahl, die größer als der vorherige Term ist und sich auf genau eine Weise als Summe zweier verschiedener früherer Terme darstellen lässt. In dieser Aufgabe ist
$$S(k)=\sum_{n=2}^{10} u_k\bigl(U(2,2n+1)\bigr)$$
zu berechnen; betrachtet werden also die neun Folgen \(U(2,5),U(2,7),\dots,U(2,21)\). Der Zielindex ist in der Originalaufgabe riesig, daher ist eine naive Erzeugung der Folgen bis zum \(k\)-ten Glied ausgeschlossen. Die Lösung funktioniert nur, weil diese spezielle Ulam-Familie eine sehr starre Struktur besitzt.
Fixiere eine Folge \(U(2,v)\) mit ungeradem \(v=2n+1\). Der entscheidende Punkt ist, dass der gerade Anteil praktisch verschwindet; danach werden die ungeraden Terme durch eine lineare Rekurrenz über \(\mathbb{F}_2\) beschrieben.
Für die neun Werte \(v=5,7,\dots,21\) nutzt die Implementierung die Tatsache aus, dass nach dem Anfangsterm \(2\) genau ein weiterer gerader Term vorkommt, nämlich
$$E=2(v+1).$$
Danach sind die neu auftretenden Ulam-Zahlen ungerade. Damit kann ein ungerader Kandidat \(x>E\) nur in den Formen
$$x=2+(x-2),\qquad x=E+(x-E).$$
geschrieben werden. Ungerade Zahl gleich ungerade plus ungerade ist unmöglich, und andere gerade Ulam-Terme stehen nicht zur Verfügung. Also gehört \(x>E\) genau dann zur Folge, wenn genau einer der beiden Vorgänger \(x-2\) und \(x-E\) bereits in der Folge liegt.
Wir definieren für ungerade Zahlen den Indikator
$$b_t=\chi(2t+1),$$
wobei \(b_t=1\) bedeutet, dass \(2t+1\) in \(U(2,v)\) liegt, und \(b_t=0\) sonst. Außerdem setzen wir
$$g=v+1,\qquad E=2g.$$
Für \(x=2t+1>E\) folgt aus der obigen Beobachtung
$$\chi(x)=\chi(x-2)\oplus\chi(x-E),$$
also äquivalent
$$b_t=b_{t-1}\oplus b_{t-g}\qquad (t\ge g).$$
Ein Fenster aus \(g\) aufeinanderfolgenden Bits bestimmt somit alle späteren ungeraden Terme. Statt mit riesigen Zahlen zu arbeiten, genügt es, einen deterministischen \(g\)-Bit-Zustand weiterzuschieben.
Für \(v=5\) gilt \(g=6\) und \(E=12\). Der Anfang der Folge lautet
$$2,5,7,9,11,12,13,15,19,23,\dots$$
Betrachten wir die ungeraden Zahlen im Startfenster \(\{1,3,5,7,9,11\}\). Ihre Mitgliedschaftsbits sind
$$b_0,\dots,b_5=(0,0,1,1,1,1).$$
Jetzt wenden wir \(b_t=b_{t-1}\oplus b_{t-6}\) an:
$$b_6=b_5\oplus b_0=1\oplus 0=1,$$
also liegt \(13=2\cdot 6+1\) in der Folge. Weiter,
$$b_7=b_6\oplus b_1=1\oplus 0=1,$$
also erscheint \(15\). Dann
$$b_8=b_7\oplus b_2=1\oplus 1=0,$$
also wird \(17\) übersprungen, und
$$b_9=b_8\oplus b_3=0\oplus 1=1,$$
also taucht \(19\) auf. Genau dieses Muster sieht man auch in der tatsächlich erzeugten Präfixfolge.
Im Schritt \(t\) benötigt die Rekurrenz nur die letzten \(g\) Bits, also etwa den Zustand
$$\bigl(b_{t-g+1},b_{t-g+2},\dots,b_t\bigr).$$
Das nächste Bit ist durch den ältesten und den neuesten Eintrag eindeutig bestimmt. Da es nur \(2^g\) mögliche Zustände gibt, muss irgendwann ein Zustand erneut auftreten. Ab diesem Moment wiederholt sich die gesamte weitere Entwicklung, also besteht die ungerade Mitgliedschaftsfolge aus einer Vorperiode und anschließend einem reinen Zyklus.
Die vollständige Ulam-Folge ist fast nur ungerade, aber der besondere gerade Term \(E\) muss an der richtigen Stelle eingefügt werden. Sein Index ist
$$r_E=2+\#\{x<E:x\equiv 1 \pmod 2,\ x\in U(2,v)\}.$$
Auf Platz 1 steht \(2\), danach kommen alle ungeraden Folgenglieder unterhalb von \(E\), und dann folgt \(E\) selbst. Also gilt
$$u_1(v)=2,\qquad u_{r_E}(v)=E,$$
und jede andere Anfrage wird in einen Rang unter den ungeraden Termen übersetzt:
$$r_{\mathrm{odd}}= \begin{cases} k-1,&k<r_E,\\ k-2,&k>r_E. \end{cases}$$
Präfixsummen der Bitfolge geben an, wie viele ungerade Ulam-Zahlen bis zu einem bestimmten ungeraden Wert erschienen sind. Mit Vorperiode und Eins-Anzahl pro Zyklus kann man deshalb ganze Zyklen arithmetisch überspringen und den exakten Wert anschließend per Binärsuche finden.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst nur ein kurzes Brute-Force-Präfix, gerade lang genug, um die Mitgliedschaft der ungeraden Zahlen bis \(2g-1\) zu kennen. Damit erhält man das vollständige Startfenster \(b_0,\dots,b_{g-1}\) und zugleich die Anzahl der ungeraden Folgenglieder unterhalb des speziellen geraden Terms \(E\).
Aus diesem Startfenster wird ein \(g\)-Bit-Zustand aufgebaut, dazu Präfixsummen der 1-Bits. Danach wird die normale Ulam-Erzeugung nicht mehr verwendet; alle späteren Entscheidungen folgen direkt aus der XOR-Rekurrenz.
Jedes neue Bit aktualisiert den gleitenden \(g\)-Bit-Zustand. Der erste wiederholte Zustand markiert Anfang und Ende des endgültigen Zyklus. Gespeichert werden die Anzahl ungerader Terme vor dem Zyklus, die Anzahl pro Zyklus sowie Präfixsummen innerhalb eines Zyklus.
Für eine Anfrage werden zuerst die Sonderfälle \(2\) und \(E\) behandelt, danach wird die Position in einen ungeraden Rang umgerechnet, es werden möglichst viele volle Zyklen übersprungen, und schließlich liefert eine Binärsuche auf der passenden Präfixtabelle den gesuchten Wert \(2t+1\). Die C++- und Java-Implementierungen rechnen die neun Werte von \(v\) parallel aus; die Python-Implementierung benutzt dieselbe Mathematik seriell.
Für eine einzelne Folge \(U(2,v)\) dominiert die Zykluserkennung auf den \(g=v+1\) Bitzuständen. Im schlimmsten Fall kostet das \(O(2^g)\) Zeit und \(O(2^g)\) Speicher für die Tabelle der ersten Auftretenszeit jedes Zustands. Hier gilt \(v\le 21\), also \(g\le 22\), und der Zustandsraum hat damit höchstens \(2^{22}=4{,}194{,}304\) Elemente.
Nach dieser Vorverarbeitung kostet die Bestimmung von \(u_k(v)\) nur noch \(O(\log(P+\lambda))\), wobei \(P\) die Vorperiodenlänge und \(\lambda\) die Zykluslänge ist; übrig bleiben nämlich nur arithmetische Sprünge und eine Binärsuche auf Präfixsummen. Das Gesamtproblem wiederholt diesen Ablauf für nur neun voneinander unabhängige Folgen und addiert die Ergebnisse.
Bir Ulam dizisi \(U(a,b)\), \(a\) ve \(b\) ile başlar. Ondan sonraki her terim, bir önceki terimden büyük olan ve daha önceki iki farklı terimin toplamı olarak tam bir kez yazılabilen en küçük tam sayıdır. Bu problemde hesaplanmak istenen değer
$$S(k)=\sum_{n=2}^{10} u_k\bigl(U(2,2n+1)\bigr)$$
olduğundan incelenen dokuz dizi \(U(2,5),U(2,7),\dots,U(2,21)\) olur. Hedef indeks orijinal problemde çok büyüktür; bu yüzden dizileri tek tek üretmek işe yaramaz. Çözüm, yalnızca bu özel Ulam ailesinin çok katı bir yapıya sahip olmasından dolayı mümkündür.
Tek bir \(U(2,v)\) dizisini ele alalım; burada \(v=2n+1\) tektir. Asıl fikir şudur: çift terimler neredeyse tamamen ortadan kalkar, geriye kalan tek terimler de \(\mathbb{F}_2\) üzerinde doğrusal bir reküransla yönetilir.
\(v=5,7,\dots,21\) için uygulamanın kullandığı özel yapı şudur: başlangıçtaki \(2\) dışında dizide yalnızca bir tane daha çift terim vardır, o da
$$E=2(v+1).$$
Bu noktadan sonra yeni gelen terimler tektir. Böylece \(E\)'den büyük tek bir aday \(x\) ancak şu iki biçimde yazılabilir:
$$x=2+(x-2),\qquad x=E+(x-E).$$
Tek sayı, tek artı tek olarak oluşamaz; ayrıca kullanılabilecek başka çift Ulam terimi de yoktur. Dolayısıyla \(x>E\), tam olarak \(x-2\) ve \(x-E\) sayılarından biri dizideyse ve diğeri değilse Ulam dizisine girer.
Tek sayılar için şu göstergeyi tanımlayalım:
$$b_t=\chi(2t+1).$$
Burada \(b_t=1\), \(2t+1\) sayısının \(U(2,v)\) içinde olduğunu; \(b_t=0\) ise olmadığını gösterir. Ayrıca
$$g=v+1,\qquad E=2g$$
yazalım. \(x=2t+1>E\) için yukarıdaki gözlem
$$\chi(x)=\chi(x-2)\oplus\chi(x-E)$$
şeklindedir; bu da
$$b_t=b_{t-1}\oplus b_{t-g}\qquad (t\ge g)$$
demektir. Yani \(g\) adet ardışık bitten oluşan tek bir pencere, daha sonraki tüm tek terimleri belirler. Büyük sayılarla uğraşmak yerine, deterministik bir \(g\)-bit durumu izlemek yeterlidir.
\(v=5\) için \(g=6\) ve \(E=12\) olur. Dizinin başlangıcı
$$2,5,7,9,11,12,13,15,19,23,\dots$$
şeklindedir. Başlangıç penceresindeki tek sayılar \(\{1,3,5,7,9,11\}\) için üyelik bitleri
$$b_0,\dots,b_5=(0,0,1,1,1,1)$$
olur. Şimdi \(b_t=b_{t-1}\oplus b_{t-6}\) bağıntısını uygulayalım:
$$b_6=b_5\oplus b_0=1\oplus 0=1,$$
dolayısıyla \(13=2\cdot 6+1\) dizidedir. Sonra
$$b_7=b_6\oplus b_1=1\oplus 0=1,$$
yani \(15\) gelir. Ardından
$$b_8=b_7\oplus b_2=1\oplus 1=0,$$
olduğu için \(17\) atlanır ve
$$b_9=b_8\oplus b_3=0\oplus 1=1$$
olduğu için \(19\) görünür. Hızlı yöntemin ürettiği desen, doğrudan hesaplanan ön ekle tam olarak örtüşür.
\(t\) adımında rekürans yalnızca son \(g\) bite ihtiyaç duyar; örneğin durum
$$\bigl(b_{t-g+1},b_{t-g+2},\dots,b_t\bigr)$$
ile temsil edilebilir. Bir sonraki bit, en eski ve en yeni bitten tek anlamlı biçimde belirlenir. Toplam yalnızca \(2^g\) farklı durum bulunduğu için bir noktada bir durum tekrar etmek zorundadır. Aynı \(g\)-bit durum ikinci kez görüldüğü anda sonraki gelişim de aynı şekilde tekrar eder; yani tek-terim üyelik dizisi sonlu bir ön dönemden sonra saf bir döngüye girer.
Tam Ulam dizisi neredeyse tamamen tek terimlerden oluşur, fakat istisna olan çift terim \(E\) doğru yere yerleştirilmelidir. Bu terimin dizideki konumu
$$r_E=2+\#\{x<E:x\equiv 1 \pmod 2,\ x\in U(2,v)\}$$
şeklindedir. İlk konumda \(2\) vardır, sonra \(E\)'den küçük tüm tek Ulam terimleri gelir, ardından \(E\) yer alır. Bu yüzden
$$u_1(v)=2,\qquad u_{r_E}(v)=E,$$
ve diğer tüm sorgular şu tek-sıra indeksine çevrilir:
$$r_{\mathrm{odd}}= \begin{cases} k-1,&k<r_E,\\ k-2,&k>r_E. \end{cases}$$
Bit dizisinin prefix toplamları, belli bir tek sayıya kadar kaç tek Ulam teriminin geldiğini verir. Ön dönem uzunluğu ve döngü başına düşen 1 sayısı bilindiğinde, algoritma tam döngüleri aritmetik olarak atlayabilir; ardından tek bir ikili aramayla doğru \(2t+1\) değerini bulur.
C++, Python ve Java uygulamaları önce çok kısa bir brute-force ön ek üretir; amaç yalnızca \(2g-1\)'e kadar olan tek sayıların üyeliğini öğrenmektir. Böylece tam başlangıç penceresi \(b_0,\dots,b_{g-1}\) elde edilir ve özel çift terim \(E\)'nin altındaki tek üyelerin sayısı bulunur.
Bu başlangıç penceresinden bir \(g\)-bit durum kurulur, 1-bit prefix toplamları hesaplanır ve bundan sonra normal Ulam üretimi bırakılır. Sonraki tüm üyelik kararları XOR reküransı üzerinden verilir.
Her yeni bit, kayan \(g\)-bit durumunu günceller. İlk tekrar eden durum, nihai döngünün başlangıcını ve sonunu verir. Uygulama, döngüden önce görülen tek terim sayısını, bir tam döngüde gelen tek terim sayısını ve döngü içi prefix toplamlarını saklar.
Sorgu geldiğinde önce \(2\) ve \(E\) için özel durumlar ele alınır, sonra istenen pozisyon tek-terim sırasına çevrilir, mümkün olan kadar çok tam döngü atlanır ve ilgili prefix tablosu üzerinde ikili arama yapılarak karşılık gelen \(2t+1\) değeri bulunur. C++ ve Java sürümleri bunu dokuz \(v\) değeri için paralel yürütür; Python sürümü aynı matematiği seri uygular.
Tek bir \(U(2,v)\) dizisi için baskın maliyet, \(g=v+1\) bit durumları üzerinde döngü aramaktır. En kötü durumda süre \(O(2^g)\), her durumun ilk görüldüğü adımı tutmak için bellek de \(O(2^g)\) olur. Bu problemde \(v\le 21\) olduğu için \(g\le 22\) ve durum uzayı en fazla \(2^{22}=4{,}194{,}304\) durumdur.
Bu ön işlemden sonra \(u_k(v)\) değerini bulmak \(O(\log(P+\lambda))\) zaman alır; burada \(P\) ön dönem, \(\lambda\) ise döngü uzunluğudur. Geriye yalnızca aritmetik sıçramalar ve prefix toplamları üzerinde tek bir ikili arama kalır. Tüm problem bu işlemi sadece dokuz bağımsız dizi için tekrarlayıp sonuçları toplar.
Una sucesión de Ulam \(U(a,b)\) empieza con \(a\) y \(b\). Cada término posterior es el menor entero mayor que el término anterior que puede escribirse de manera única como suma de dos términos anteriores distintos. En este problema hay que calcular
$$S(k)=\sum_{n=2}^{10} u_k\bigl(U(2,2n+1)\bigr),$$
de modo que las nueve sucesiones relevantes son \(U(2,5),U(2,7),\dots,U(2,21)\). El índice pedido es gigantesco en el enunciado original, así que generar cada sucesión hasta la posición \(k\) es inviable. La solución depende por completo de una estructura muy rígida propia de esta familia concreta.
Fijemos una sucesión \(U(2,v)\) con \(v=2n+1\) impar. La observación clave es que la parte par de la sucesión se reduce a un caso excepcional, y a partir de ahí la parte impar queda gobernada por una recurrencia lineal sobre \(\mathbb{F}_2\).
Para los nueve valores \(v=5,7,\dots,21\), la implementación explota el hecho de que, después del término inicial \(2\), solo aparece un término par adicional:
$$E=2(v+1).$$
A partir de ese momento, los nuevos miembros son impares. Entonces un candidato impar \(x>E\) solo puede escribirse como
$$x=2+(x-2),\qquad x=E+(x-E).$$
Un impar no puede venir de impar más impar, y no existen otros términos pares disponibles dentro de la sucesión. Por lo tanto, \(x>E\) entra en \(U(2,v)\) exactamente cuando uno de \(x-2\) y \(x-E\) ya pertenece a la sucesión y el otro no.
Definimos el indicador de pertenencia impar mediante
$$b_t=\chi(2t+1),$$
donde \(b_t=1\) si \(2t+1\) pertenece a \(U(2,v)\), y \(b_t=0\) en caso contrario. Además escribimos
$$g=v+1,\qquad E=2g.$$
Para \(x=2t+1>E\), la observación anterior se reescribe como
$$\chi(x)=\chi(x-2)\oplus\chi(x-E),$$
es decir,
$$b_t=b_{t-1}\oplus b_{t-g}\qquad (t\ge g).$$
Así, una ventana de \(g\) bits consecutivos determina todos los términos impares posteriores. En vez de seguir la sucesión entera, basta con seguir un estado binario de longitud \(g\) que evoluciona de manera determinista.
Para \(v=5\), tenemos \(g=6\) y \(E=12\). El comienzo de la sucesión es
$$2,5,7,9,11,12,13,15,19,23,\dots$$
Si miramos los impares de la ventana inicial \(\{1,3,5,7,9,11\}\), obtenemos los bits
$$b_0,\dots,b_5=(0,0,1,1,1,1).$$
Ahora aplicamos la recurrencia \(b_t=b_{t-1}\oplus b_{t-6}\):
$$b_6=b_5\oplus b_0=1\oplus 0=1,$$
por lo que \(13=2\cdot 6+1\) pertenece a la sucesión. Después,
$$b_7=b_6\oplus b_1=1\oplus 0=1,$$
así que \(15\) también aparece. Luego
$$b_8=b_7\oplus b_2=1\oplus 1=0,$$
por eso \(17\) se descarta, y
$$b_9=b_8\oplus b_3=0\oplus 1=1,$$
por eso \(19\) sí entra. Es exactamente el mismo patrón que se observa en el prefijo generado por fuerza bruta.
En el paso \(t\), la recurrencia solo necesita los últimos \(g\) bits, por ejemplo el estado
$$\bigl(b_{t-g+1},b_{t-g+2},\dots,b_t\bigr).$$
El siguiente bit queda determinado por el más antiguo y el más reciente, de modo que la transición es determinista. Como solo existen \(2^g\) estados posibles, algún estado debe repetirse. Una vez que reaparece el mismo estado de longitud \(g\), toda la evolución posterior se repite también, así que la secuencia de pertenencia impar tiene un preperiodo finito seguido de un ciclo puro.
La sucesión completa de Ulam es casi totalmente impar, pero el término par excepcional \(E\) debe insertarse en su posición correcta. Ese índice es
$$r_E=2+\#\{x<E:x\equiv 1 \pmod 2,\ x\in U(2,v)\}.$$
La primera posición está ocupada por \(2\), luego vienen todos los miembros impares por debajo de \(E\), y después aparece \(E\). Por tanto,
$$u_1(v)=2,\qquad u_{r_E}(v)=E,$$
mientras que cualquier otra consulta se convierte en un rango entre los términos impares:
$$r_{\mathrm{odd}}= \begin{cases} k-1,&k<r_E,\\ k-2,&k>r_E. \end{cases}$$
Las sumas prefijas de la secuencia de bits indican cuántos números de Ulam impares han aparecido hasta un cierto valor impar. Conocidos el preperiodo y el número de unos por ciclo, el algoritmo puede saltar ciclos completos aritméticamente y luego localizar el valor exacto con una sola búsqueda binaria.
Las implementaciones en C++, Python y Java generan primero un prefijo muy corto por fuerza bruta, solo lo suficiente para conocer la pertenencia de los impares hasta \(2g-1\). Eso proporciona la ventana inicial completa \(b_0,\dots,b_{g-1}\) y también el número de miembros impares situados por debajo del término par especial \(E\).
A partir de esa ventana inicial, la implementación construye un estado de \(g\) bits, calcula sumas prefijas de unos y deja de usar la generación Ulam ordinaria. Todas las decisiones posteriores de pertenencia impar vienen de la recurrencia XOR.
Cada bit nuevo actualiza el estado deslizante de \(g\) bits. El primer estado repetido determina el comienzo y el final del ciclo eventual. La implementación almacena cuántos términos impares aparecen antes del ciclo, cuántos aparecen en un ciclo completo y las sumas prefijas dentro del propio ciclo.
Cuando llega la consulta, la implementación separa los casos especiales \(2\) y \(E\), convierte la posición pedida en un rango impar, salta tantos ciclos completos como sea posible y finalmente hace una búsqueda binaria sobre la tabla prefija adecuada para recuperar el valor \(2t+1\). Las versiones en C++ y Java realizan este cálculo en paralelo para los nueve valores de \(v\); la versión en Python aplica la misma matemática de forma secuencial.
Para una sola sucesión \(U(2,v)\), el coste dominante es detectar el ciclo sobre los estados binarios de tamaño \(g=v+1\). En el peor caso eso requiere \(O(2^g)\) tiempo y \(O(2^g)\) memoria para la tabla que registra la primera aparición de cada estado. En este problema \(v\le 21\), luego \(g\le 22\), así que el espacio de estados es como máximo \(2^{22}=4{,}194{,}304\).
Una vez hecha esa precomputación, obtener \(u_k(v)\) cuesta \(O(\log(P+\lambda))\), donde \(P\) es la longitud del preperiodo y \(\lambda\) la longitud del ciclo, porque solo quedan saltos aritméticos y una búsqueda binaria sobre sumas prefijas. El problema completo repite este proceso para solo nueve sucesiones independientes y suma los resultados.
Ulam 序列 \(U(a,b)\) 以 \(a\) 和 \(b\) 开始。之后的每一项都是严格大于前一项、并且能够唯一表示为两个不同先前项之和的最小整数。本题要求计算
$$S(k)=\sum_{n=2}^{10} u_k\bigl(U(2,2n+1)\bigr),$$
因此真正需要处理的是九条序列 \(U(2,5),U(2,7),\dots,U(2,21)\)。原题中的目标下标极大，所以不可能按定义一项一项地生成到第 \(k\) 项。可行做法来自这组序列非常特殊的结构，而不是来自对通用 Ulam 序列的暴力优化。
固定一条序列 \(U(2,v)\)，其中 \(v=2n+1\) 为奇数。整个解法的关键在于：偶数项几乎完全退化，只剩一个特殊值；从那以后，奇数项的成员资格满足 \(\mathbb{F}_2\) 上的线性递推。
对于题目中出现的九个参数 \(v=5,7,\dots,21\)，实现所利用的结构是：序列除了起始项 \(2\) 之外，只会再出现一个偶数项
$$E=2(v+1).$$
从那以后新增项都为奇数。这一点极其重要，因为任意一个大于 \(E\) 的奇数候选 \(x\) 只能写成
$$x=2+(x-2),\qquad x=E+(x-E).$$
奇数不可能由奇数加奇数得到，而序列里又没有别的偶数 Ulam 项可用。因此，对所有 \(x>E\)，它属于序列当且仅当 \(x-2\) 与 \(x-E\) 这两个数里恰好有一个已经属于序列。
把奇数的成员资格写成指示函数
$$b_t=\chi(2t+1),$$
其中 \(b_t=1\) 表示 \(2t+1\) 属于 \(U(2,v)\)，\(b_t=0\) 表示不属于。再记
$$g=v+1,\qquad E=2g.$$
对所有 \(x=2t+1>E\)，上面的结构立刻给出
$$\chi(x)=\chi(x-2)\oplus\chi(x-E),$$
也就是
$$b_t=b_{t-1}\oplus b_{t-g}\qquad (t\ge g).$$
这意味着，只要知道连续 \(g\) 个比特，就能推出后面所有奇数项。于是问题不再是“如何继续生成巨大的 Ulam 数”，而是“如何推进一个长度为 \(g\) 的有限二进制状态”。
取 \(v=5\)，则 \(g=6\)，\(E=12\)。序列开头为
$$2,5,7,9,11,12,13,15,19,23,\dots$$
先看初始窗口中的奇数 \(\{1,3,5,7,9,11\}\)。它们对应的成员资格比特是
$$b_0,\dots,b_5=(0,0,1,1,1,1).$$
现在应用递推 \(b_t=b_{t-1}\oplus b_{t-6}\)：
$$b_6=b_5\oplus b_0=1\oplus 0=1,$$
所以 \(13=2\cdot 6+1\) 在序列中。接着
$$b_7=b_6\oplus b_1=1\oplus 0=1,$$
于是 \(15\) 也在序列中。再往后
$$b_8=b_7\oplus b_2=1\oplus 1=0,$$
因此 \(17\) 被跳过，而
$$b_9=b_8\oplus b_3=0\oplus 1=1,$$
所以 \(19\) 又重新出现。这个例子正好展示了代码中“短前缀 + 递推延伸”的工作方式。
在第 \(t\) 步，递推只依赖最近的 \(g\) 个比特，例如状态可以写成
$$\bigl(b_{t-g+1},b_{t-g+2},\dots,b_t\bigr).$$
下一个比特由最旧和最新两个位置唯一决定，所以状态转移是确定性的。由于这样的 \(g\)-比特状态总共只有 \(2^g\) 种，按照抽屉原理，某个状态一定会再次出现。一旦同一个状态重复出现，之后的更新过程也会完全重复，因此奇数成员资格序列必然由“有限前导段 + 纯周期段”构成。
完整的 Ulam 序列几乎全是奇数，但特殊偶数项 \(E\) 必须插入到正确的位置。它在整条序列中的下标是
$$r_E=2+\#\{x<E:x\equiv 1 \pmod 2,\ x\in U(2,v)\}.$$
原因是：第 1 项是 \(2\)，然后是所有小于 \(E\) 的奇数成员，接下来才轮到 \(E\) 本身。因此
$$u_1(v)=2,\qquad u_{r_E}(v)=E,$$
其余情况都先转换成“在奇数成员中的排名”
$$r_{\mathrm{odd}}= \begin{cases} k-1,&k<r_E,\\ k-2,&k>r_E. \end{cases}$$
一旦知道了比特序列前导段里有多少个 1、每个周期里又有多少个 1，就可以用整数除法一次跳过很多整个周期。剩下的部分再通过前缀计数做一次二分搜索，就能精确定位对应的奇数 \(2t+1\)。
C++、Python 和 Java 实现都会先暴力生成一个很短的前缀，长度只需要足以判断 \(2g-1\) 以内的奇数哪些属于序列。这一步给出了完整的初始窗口 \(b_0,\dots,b_{g-1}\)，同时也确定了特殊偶数项 \(E\) 之前一共有多少个奇数成员。
有了这组种子以后，实现会构造一个 \(g\)-比特状态、建立 1 的前缀计数，然后就不再继续做普通的 Ulam 生成。后续所有奇数成员判定都来自上面的 XOR 递推。
每生成一个新比特，滑动的 \(g\)-比特状态就更新一次。第一次遇到重复状态时，前导段的终点和周期段的范围就都确定了。实现会记录周期前已有多少个奇数成员、一个完整周期贡献多少个奇数成员，以及周期内部的前缀计数。
回答查询时，先单独处理 \(2\) 和 \(E\) 这两个特殊位置，再把原始下标换成奇数排名，随后尽可能跳过完整周期，最后对相应的前缀表做一次二分搜索，恢复出正确的 \(2t+1\)。C++ 和 Java 实现会把九个不同的 \(v\) 分开并行求解；Python 实现使用完全相同的数学步骤串行完成。
对单条序列 \(U(2,v)\) 而言，主要开销是对 \(g=v+1\) 位状态做循环检测。最坏情况下，时间复杂度为 \(O(2^g)\)，记录每个状态首次出现位置所需的空间复杂度同样是 \(O(2^g)\)。本题里 \(v\le 21\)，所以 \(g\le 22\)，状态总数最多只有 \(2^{22}=4{,}194{,}304\)。
一旦前处理完成，求 \(u_k(v)\) 只需要 \(O(\log(P+\lambda))\) 时间，其中 \(P\) 是前导段长度，\(\lambda\) 是周期长度，因为剩余工作只包括常数次算术跳转和一次对前缀和的二分搜索。整道题不过是把这一过程对九条彼此独立的序列各做一次并求和。
Последовательность Улама \(U(a,b)\) начинается с \(a\) и \(b\). Каждый следующий член — это наименьшее целое число, большее предыдущего, которое единственным образом представимо как сумма двух различных более ранних членов. В задаче требуется вычислить
$$S(k)=\sum_{n=2}^{10} u_k\bigl(U(2,2n+1)\bigr),$$
то есть рассмотреть девять последовательностей \(U(2,5),U(2,7),\dots,U(2,21)\). В исходной постановке индекс \(k\) огромен, поэтому прямое построение последовательностей до нужного места невозможно. Рабочее решение появляется только потому, что именно эта семейство имеет очень специальную внутреннюю структуру.
Зафиксируем одну последовательность \(U(2,v)\), где \(v=2n+1\) нечётно. Главная идея в том, что чётная часть почти полностью исчезает, а нечётная часть после этого подчиняется линейной рекуррентной формуле над \(\mathbb{F}_2\).
Для девяти значений \(v=5,7,\dots,21\) реализация использует следующий факт: после начального чётного члена \(2\) в последовательности появляется ровно ещё один чётный член, а именно
$$E=2(v+1).$$
После этого новые элементы уже нечётны. Поэтому любой нечётный кандидат \(x>E\) может быть записан только в одном из двух видов:
$$x=2+(x-2),\qquad x=E+(x-E).$$
Нечётное число не может получиться как нечётное плюс нечётное, а других чётных членов Улама больше нет. Значит, число \(x>E\) входит в последовательность тогда и только тогда, когда ровно одно из чисел \(x-2\) и \(x-E\) уже присутствует в последовательности.
Введём индикатор принадлежности нечётных чисел:
$$b_t=\chi(2t+1),$$
где \(b_t=1\), если \(2t+1\in U(2,v)\), и \(b_t=0\) иначе. Также обозначим
$$g=v+1,\qquad E=2g.$$
Для \(x=2t+1>E\) наблюдение выше даёт
$$\chi(x)=\chi(x-2)\oplus\chi(x-E),$$
то есть
$$b_t=b_{t-1}\oplus b_{t-g}\qquad (t\ge g).$$
Итак, одно окно из \(g\) подряд идущих бит полностью определяет все последующие нечётные элементы. Вместо работы с гигантскими числами задача сводится к эволюции конечного двоичного состояния длины \(g\).
При \(v=5\) имеем \(g=6\) и \(E=12\). Начало последовательности выглядит так:
$$2,5,7,9,11,12,13,15,19,23,\dots$$
Рассмотрим нечётные числа в стартовом окне \(\{1,3,5,7,9,11\}\). Их биты принадлежности равны
$$b_0,\dots,b_5=(0,0,1,1,1,1).$$
Теперь применим рекурсию \(b_t=b_{t-1}\oplus b_{t-6}\):
$$b_6=b_5\oplus b_0=1\oplus 0=1,$$
поэтому \(13=2\cdot 6+1\) входит в последовательность. Далее
$$b_7=b_6\oplus b_1=1\oplus 0=1,$$
значит, входит и \(15\). Затем
$$b_8=b_7\oplus b_2=1\oplus 1=0,$$
поэтому \(17\) пропускается, а
$$b_9=b_8\oplus b_3=0\oplus 1=1,$$
так что \(19\) снова появляется. Этот мини-пример в точности показывает механизм, который затем работает на всех больших индексах.
На шаге \(t\) рекурсия использует только последние \(g\) бит, например состояние
$$\bigl(b_{t-g+1},b_{t-g+2},\dots,b_t\bigr).$$
Следующий бит однозначно определяется самым старым и самым новым значением, то есть переход детерминирован. Но возможных состояний всего \(2^g\), следовательно, какое-то состояние обязательно повторится. После повторения того же \(g\)-битного состояния вся дальнейшая эволюция повторяется тоже, и поэтому последовательность нечётной принадлежности имеет конечный предпериод и затем чистый цикл.
Полная последовательность Улама почти целиком нечётна, но специальный чётный член \(E\) нужно вставить на правильное место. Его индекс равен
$$r_E=2+\#\{x<E:x\equiv 1 \pmod 2,\ x\in U(2,v)\}.$$
Первое место занимает \(2\), затем идут все нечётные элементы меньше \(E\), и только потом сам \(E\). Поэтому
$$u_1(v)=2,\qquad u_{r_E}(v)=E,$$
а любая другая позиция переводится в ранг среди нечётных членов:
$$r_{\mathrm{odd}}= \begin{cases} k-1,&k<r_E,\\ k-2,&k>r_E. \end{cases}$$
Префиксные суммы по битовой последовательности показывают, сколько нечётных чисел Улама уже встретилось до заданного нечётного значения. Зная длину предпериода и число единиц на цикл, можно арифметически перескочить через множество полных циклов, а затем одной двоичной поисковой процедурой найти точное значение \(2t+1\).
Реализации на C++, Python и Java сначала строят очень короткий префикс грубой силой — ровно настолько длинный, чтобы выяснить, какие нечётные числа до \(2g-1\) принадлежат последовательности. Это даёт полное стартовое окно \(b_0,\dots,b_{g-1}\) и одновременно число нечётных членов, расположенных ниже специального чётного значения \(E\).
После этого реализация формирует \(g\)-битное состояние, считает префиксные суммы единиц и перестаёт использовать обычную генерацию Улама. Все дальнейшие решения о принадлежности нечётных чисел приходят уже из XOR-рекурсии.
Каждый новый бит обновляет скользящее \(g\)-битное состояние. Первый повтор состояния определяет начало и конец окончательного цикла. Реализация запоминает, сколько нечётных членов появляется до цикла, сколько появляется за один цикл, а также префиксные суммы внутри самого цикла.
При ответе на запрос отдельно обрабатываются особые позиции \(2\) и \(E\), затем исходный индекс переводится в ранг среди нечётных членов, пропускается максимально возможное число полных циклов, и по подходящей таблице префиксных сумм выполняется двоичный поиск, возвращающий нужное число \(2t+1\). Версии на C++ и Java считают девять случаев \(v\) параллельно; версия на Python делает то же самое последовательно.
Для одной последовательности \(U(2,v)\) основная стоимость связана с обнаружением цикла в пространстве битовых состояний размера \(g=v+1\). В худшем случае это \(O(2^g)\) по времени и \(O(2^g)\) по памяти для таблицы первого появления каждого состояния. В нашей задаче \(v\le 21\), поэтому \(g\le 22\), а пространство состояний не превышает \(2^{22}=4{,}194{,}304\).
После такой предобработки получение \(u_k(v)\) занимает \(O(\log(P+\lambda))\), где \(P\) — длина предпериода, а \(\lambda\) — длина цикла, потому что остаются только арифметические прыжки и один двоичный поиск по префиксным суммам. Полная задача просто повторяет эту процедуру для девяти независимых последовательностей и суммирует результаты.
متتالية أولام \(U(a,b)\) تبدأ بالحدين \(a\) و\(b\). وكل حد تالٍ هو أصغر عدد صحيح أكبر من الحد السابق ويمكن كتابته بطريقة وحيدة على صورة مجموع حدين سابقين مختلفين. في هذه المسألة نريد حساب
$$S(k)=\sum_{n=2}^{10} u_k\bigl(U(2,2n+1)\bigr),$$
وبذلك فإن المتتاليات التسع المطلوبة هي \(U(2,5),U(2,7),\dots,U(2,21)\). في النص الأصلي للمسألة يكون \(k\) هائلًا، لذا فإن توليد الحدود واحدًا بعد الآخر حتى الوصول إلى الرتبة المطلوبة غير ممكن عمليًا. الطريقة الناجحة تعتمد على بنية خاصة جدًا لهذه العائلة بالذات من متتاليات أولام.
لنثبت متتالية واحدة \(U(2,v)\) حيث \(v=2n+1\) عدد فردي. الفكرة الحاسمة هي أن الحدود الزوجية تنكمش إلى حالة استثنائية واحدة تقريبًا، وبعد ذلك تصبح عضوية الحدود الفردية محكومة بعلاقة عودية خطية فوق \(\mathbb{F}_2\).
بالنسبة إلى القيم التسع \(v=5,7,\dots,21\)، تستفيد الخوارزمية من الحقيقة التالية: بعد الحد الابتدائي \(2\)، لا يظهر في المتتالية إلا حد زوجي واحد إضافي، وهو
$$E=2(v+1).$$
بعد هذه النقطة تصبح الحدود الجديدة فردية. ولهذا فإن أي مرشح فردي \(x>E\) لا يمكن أن يكتب إلا بإحدى الصورتين
$$x=2+(x-2),\qquad x=E+(x-E).$$
فالعدد الفردي لا يمكن أن ينتج من فردي زائد فردي، ولا توجد حدود زوجية أخرى من متتالية أولام يمكن استخدامها. لذلك فإن \(x>E\) ينتمي إلى المتتالية إذا وفقط إذا كان واحد فقط من \(x-2\) و\(x-E\) موجودًا فيها.
نعرّف مؤشر العضوية للأعداد الفردية على الصورة
$$b_t=\chi(2t+1),$$
حيث إن \(b_t=1\) إذا كان \(2t+1\) ضمن \(U(2,v)\)، و\(b_t=0\) في غير ذلك. كما نكتب
$$g=v+1,\qquad E=2g.$$
وعند \(x=2t+1>E\) تتحول الملاحظة السابقة إلى
$$\chi(x)=\chi(x-2)\oplus\chi(x-E),$$
أي
$$b_t=b_{t-1}\oplus b_{t-g}\qquad (t\ge g).$$
وهذا يعني أن نافذة واحدة مكوّنة من \(g\) بتات متتالية تكفي لتحديد جميع الحدود الفردية اللاحقة. بدلًا من متابعة أعداد أولام الضخمة مباشرة، يكفي تتبع حالة ثنائية بطول \(g\) تتطور بطريقة حتمية.
عندما \(v=5\) نحصل على \(g=6\) و\(E=12\). وبداية المتتالية هي
$$2,5,7,9,11,12,13,15,19,23,\dots$$
إذا نظرنا إلى الأعداد الفردية في النافذة الابتدائية \(\{1,3,5,7,9,11\}\)، فإن بتات العضوية تكون
$$b_0,\dots,b_5=(0,0,1,1,1,1).$$
نطبق الآن العلاقة \(b_t=b_{t-1}\oplus b_{t-6}\):
$$b_6=b_5\oplus b_0=1\oplus 0=1,$$
ولذلك فإن \(13=2\cdot 6+1\) يظهر في المتتالية. ثم
$$b_7=b_6\oplus b_1=1\oplus 0=1,$$
فيظهر \(15\) أيضًا. بعد ذلك
$$b_8=b_7\oplus b_2=1\oplus 1=0,$$
ولهذا يُستبعد \(17\)، بينما
$$b_9=b_8\oplus b_3=0\oplus 1=1,$$
فيعيد \(19\) إلى المتتالية. هذا المثال الصغير يوضح بالضبط كيف تنتقل الخوارزمية من بادئة قصيرة إلى توليد سريع للمواقع البعيدة.
في الخطوة \(t\)، لا تحتاج العلاقة إلا إلى آخر \(g\) بتات، ويمكن تمثيل الحالة مثلًا بـ
$$\bigl(b_{t-g+1},b_{t-g+2},\dots,b_t\bigr).$$
البت التالي يتحدد بالكامل من أقدم بت وأحدث بت، أي إن الانتقال حتمي. وبما أن عدد الحالات الممكنة لا يتجاوز \(2^g\)، فلا بد أن تتكرر حالة ما. وما إن تتكرر الحالة الثنائية نفسها حتى يتكرر ما بعدها أيضًا، ولذلك تنقسم سلسلة عضوية الأعداد الفردية إلى مقدمة منتهية يتبعها دور خالص.
متتالية أولام الكاملة تكاد تكون فردية بالكامل، لكن الحد الزوجي الاستثنائي \(E\) يجب أن يوضع في موضعه الصحيح. رتبة هذا الحد هي
$$r_E=2+\#\{x<E:x\equiv 1 \pmod 2,\ x\in U(2,v)\}.$$
فالمرتبة الأولى يشغلها \(2\)، ثم تأتي جميع الحدود الفردية الأصغر من \(E\)، وبعدها مباشرة يظهر \(E\). ومن ثم
$$u_1(v)=2,\qquad u_{r_E}(v)=E,$$
وأي استعلام آخر يتحول أولًا إلى رتبة داخل الحدود الفردية فقط:
$$r_{\mathrm{odd}}= \begin{cases} k-1,&k<r_E,\\ k-2,&k>r_E. \end{cases}$$
المجاميع البادئة لسلسلة البتات تخبرنا بعدد حدود أولام الفردية التي ظهرت حتى قيمة فردية معينة. وبمجرد معرفة طول المقدمة وعدد الواحدات في كل دور، يمكن تخطي أدوار كاملة حسابيًا، ثم استخدام بحث ثنائي واحد لتحديد العدد الصحيح \(2t+1\).
تبدأ تطبيقات C++ وPython وJava بتوليد بادئة قصيرة جدًا بالقوة الغاشمة، بالقدر الكافي فقط لمعرفة أي الأعداد الفردية حتى \(2g-1\) تنتمي إلى المتتالية. بهذه الخطوة نحصل على نافذة البداية الكاملة \(b_0,\dots,b_{g-1}\)، ونعرف أيضًا عدد الحدود الفردية الواقعة قبل الحد الزوجي الخاص \(E\).
انطلاقًا من هذه البذرة، تبني الشيفرة حالة من \(g\) بتات وتحسب مجاميع بادئة لعدد الواحدات، ثم تتوقف عن استخدام التوليد التقليدي لمتتاليات أولام. كل قرار لاحق بشأن عضوية عدد فردي يأتي مباشرة من علاقة XOR.
كل بت جديد يحدّث الحالة المنزلقة ذات الطول \(g\). وأول حالة متكررة تحدد بداية الدور النهائي ونهايته. بعد ذلك تخزن الشيفرة عدد الحدود الفردية قبل الدور، وعدد الحدود الفردية داخل دور كامل، وكذلك المجاميع البادئة داخل هذا الدور نفسه.
عند الإجابة عن الاستعلام، تفصل الشيفرة أولًا الحالتين الخاصتين \(2\) و\(E\)، ثم تحول الموضع المطلوب إلى رتبة بين الحدود الفردية، وتتخطى أكبر عدد ممكن من الأدوار الكاملة، وأخيرًا تجري بحثًا ثنائيًا على جدول المجاميع البادئة المناسب لاستعادة القيمة \(2t+1\). نسختا C++ وJava تنفذان هذه العملية بشكل مستقل للقيم التسع من \(v\) بالتوازي، أما نسخة Python فتطبق المنهج نفسه على نحو تسلسلي.
بالنسبة إلى متتالية واحدة \(U(2,v)\)، فإن الكلفة الأساسية هي كشف الدور في فضاء الحالات الثنائية ذي الحجم \(g=v+1\). في أسوأ الأحوال يكون الزمن \(O(2^g)\) وتكون الذاكرة \(O(2^g)\) أيضًا لتخزين أول موضع ظهرت فيه كل حالة. هنا لدينا \(v\le 21\)، وبالتالي \(g\le 22\)، أي إن فضاء الحالات لا يتجاوز \(2^{22}=4{,}194{,}304\) حالة.
بعد هذه المعالجة المسبقة، يصبح إيجاد \(u_k(v)\) مسألة \(O(\log(P+\lambda))\)، حيث \(P\) طول المقدمة و\(\lambda\) طول الدور، لأن العمل المتبقي لا يتعدى قفزات حسابية وبحثًا ثنائيًا واحدًا على المجاميع البادئة. أما المسألة الكاملة فتعيد هذه العملية لتسع متتاليات مستقلة فقط ثم تجمع النتائج.