Start from integers \(x \ge 2\) and \(y\), and define
$$a_0=y,\qquad z_0=x,\qquad a_{t+1}=a_t^2 \bmod z_t,\qquad z_{t+1}=z_t+1.$$
The sequence is counted until the first time \(a_t \le 1\). Since both \(0\) and \(1\) stay fixed under squaring, they are terminal values. Let \(\ell(x,y)\) be the number of terms from \(a_0\) through that first terminal term. Then
$$g(x)=\max_y \ell(x,y),\qquad f(n)=\max_{2 \le x \le n} g(x).$$
The direct search over all starting values is far too expensive, so the implementations reorganize the computation around the distinct residues that can still be alive after each step.
The key observation is that the process quickly merges many different starts into the same residue. Once we track those shared residues instead of individual starts, the problem becomes manageable.
For fixed \(x\), the first update depends only on \(y \bmod x\), so it is enough to consider residues \(0 \le y < x\). Moreover,
$$ (x-y)^2 \equiv y^2 \pmod{x}, $$
so the starts \(y\) and \(x-y\) merge immediately. For \(x>2\), the only starts worth keeping are \(2 \le y \le \lfloor x/2 \rfloor\), and only if the first residue is greater than \(1\). Define the first active frontier by
$$A_1(x)=\left\{y^2 \bmod x : 2 \le y \le \left\lfloor \frac{x}{2} \right\rfloor,\ y^2 \bmod x > 1\right\}.$$
If \(A_1(x)=\varnothing\), then every nontrivial start reaches \(0\) or \(1\) after one update, so \(g(x)=2\). The only special case is \(x=2\), where even the initial value is already forced to be terminal and \(g(2)=1\).
For \(t \ge 1\), let \(A_t(x)\) be the set of residues still alive after \(t\) updates. The recurrence is
$$A_{t+1}(x)=\left\{a^2 \bmod (x+t) : a \in A_t(x),\ a^2 \bmod (x+t) > 1\right\}.$$
Each set update simultaneously represents every starting value whose trajectory has merged into one of those residues. When \(A_t(x)\) becomes empty, every trajectory has terminated, so the total length is \(t+1\). This replaces many separate simulations by one deduplicated state update per time step.
If the frontier shrinks to a single residue, say
$$A_t(x)=\{v\},$$
then all surviving starting values now share exactly the same future. From that moment onward, there is no benefit in keeping a set representation: the rest is just the single trajectory starting from value \(v\) with current modulus \(x+t\). In other words, after coalescence the problem stops being a many-start search and becomes one ordinary modular-squaring chain.
To compute \(f(n)\), the implementations do not scan every \(x\) from \(2\) to \(n\). Instead they use a rigorous upper bound on intervals. Fix \(L \le u \le R\). Take any start \(y\) for the modulus \(u\), and advance the sequence for exactly \(R-u\) updates. At that point the current modulus is \(R\), and the current value is some residue \(b<R\). Therefore the remaining lifetime is at most \(g(R)\), which gives
$$\ell(u,y) \le (R-u) + g(R).$$
Taking the maximum over all \(y\) yields
$$g(u) \le (R-u) + g(R) \le (R-L) + g(R).$$
So every interval \([L,R]\) has the valid bound
$$UB([L,R]) = g(R) + (R-L).$$
If this bound is no better than the best value already known, the whole interval can be discarded safely.
The first distinct nonterminal residues are
$$A_1(10)=\{2^2,3^2,4^2,5^2\}\bmod 10 \setminus \{0,1\}=\{4,5,6,9\}.$$
Now propagate the frontier:
$$A_2(10)=\{a^2 \bmod 11 : a \in A_1(10)\}\setminus\{0,1\}=\{3,4,5\},$$
$$A_3(10)=\{a^2 \bmod 12 : a \in A_2(10)\}\setminus\{0,1\}=\{4,9\},$$
$$A_4(10)=\{a^2 \bmod 13 : a \in A_3(10)\}\setminus\{0,1\}=\{3\}.$$
At this point the frontier is a singleton, so only one tail remains. Continuing from value \(3\) with moduli \(14,15,16,\dots\) gives
$$3 \to 9 \to 6 \to 4 \to 16 \to 4 \to 16 \to 16 \to \cdots \to 8 \to 0.$$
The terminal \(0\) appears right after the step modulo \(32\), so the sequence has \(24\) terms in total and therefore
$$g(10)=24.$$
This example shows all the main ideas: first-step symmetry, deduplication of equal residues, and the switch to a single tail once every surviving start has merged.
The C++, Python, and Java implementations follow the same logic. First they build the initial frontier by scanning only half of the possible starting residues, using the symmetry \(y \leftrightarrow x-y\), and discarding first-step residues \(0\) and \(1\). To avoid recomputing each square from scratch during that initial scan, the compiled implementations update consecutive squares incrementally.
While the frontier contains more than one residue, the implementation advances the whole set one modulus at a time. Large frontiers use a dense seen-array for fast deduplication; small frontiers use a sparse hash-based container to avoid touching every residue class of the modulus. Once the frontier becomes empty, the current length is the answer for that \(x\). Once the frontier becomes a singleton, the remaining steps are computed by direct modular squaring of that one value.
For the outer function \(f(n)\), the implementation first samples a coarse grid of \(x\)-values, caches the computed \(g(x)\), and places the intervals between sampled points into a max-priority queue keyed by the bound \(UB([L,R])\). It then repeatedly bisects only those intervals whose upper bound can still beat the current best answer. The C++ and Java implementations evaluate the initial grid points in parallel, while the Python implementation uses the same search strategy sequentially.
For a fixed \(x\), building the first frontier costs \(O(x)\) time, because the scan goes through \(2,3,\dots,\lfloor x/2 \rfloor\). After that, one sparse frontier update costs expected \(O(|A_t(x)|)\), while one dense update costs \(O(x+t)\) because the deduplication array spans the whole current modulus. Therefore the running time for \(g(x)\) is output-sensitive: it is governed by the cumulative frontier sizes until extinction or singleton collapse, rather than by the number of possible starts alone.
The memory usage for one evaluation of \(g(x)\) is \(O(x+t_{\max})\) in dense phases and \(O(|A_t(x)|)\) in sparse phases. For \(f(n)\), if the interval search evaluates \(m\) different values of \(x\), the total cost is
$$O\left(m + \sum_{i=1}^{m} T(x_i)\right),$$
where \(T(x_i)\) is the cost of computing \(g(x_i)\). In the worst case \(m\) can still be \(O(n)\), but the interval bound usually prunes most subintervals long before that.
Wir starten mit ganzen Zahlen \(x \ge 2\) und \(y\) und definieren
$$a_0=y,\qquad z_0=x,\qquad a_{t+1}=a_t^2 \bmod z_t,\qquad z_{t+1}=z_t+1.$$
Gezählt wird bis zum ersten Zeitpunkt, an dem \(a_t \le 1\) gilt. Da sowohl \(0\) als auch \(1\) beim Quadrieren fest bleiben, sind dies Endzustände. Sei \(\ell(x,y)\) die Anzahl der Terme von \(a_0\) bis zu diesem ersten Endterm. Dann gilt
$$g(x)=\max_y \ell(x,y),\qquad f(n)=\max_{2 \le x \le n} g(x).$$
Ein vollständiges Durchprobieren aller Startwerte ist zu teuer. Deshalb zählen die Implementierungen nicht einzelne Starts, sondern die verschiedenen Restklassen, die nach jedem Schritt noch aktiv sein können.
Der entscheidende Punkt ist, dass viele verschiedene Starts sehr schnell in dieselbe Restklasse zusammenfallen. Sobald man diese gemeinsamen Zustände statt aller einzelnen Pfade verfolgt, wird das Problem deutlich kleiner.
Für festes \(x\) hängt das erste Update nur von \(y \bmod x\) ab. Daher genügt es, die Restklassen \(0 \le y < x\) zu betrachten. Außerdem gilt
$$ (x-y)^2 \equiv y^2 \pmod{x}, $$
sodass die Startwerte \(y\) und \(x-y\) sofort zusammenfallen. Für \(x>2\) muss man nur \(2 \le y \le \lfloor x/2 \rfloor\) prüfen und nur diejenigen ersten Restklassen behalten, die größer als \(1\) sind. Die erste aktive Front ist also
$$A_1(x)=\left\{y^2 \bmod x : 2 \le y \le \left\lfloor \frac{x}{2} \right\rfloor,\ y^2 \bmod x > 1\right\}.$$
Ist \(A_1(x)=\varnothing\), dann erreicht jeder nichttriviale Start nach genau einem Update bereits \(0\) oder \(1\), also ist \(g(x)=2\). Nur \(x=2\) ist ein Sonderfall; dort ist schon der Start trivial und \(g(2)=1\).
Für \(t \ge 1\) sei \(A_t(x)\) die Menge aller Restklassen, die nach \(t\) Updates noch leben. Dann gilt die Rekursion
$$A_{t+1}(x)=\left\{a^2 \bmod (x+t) : a \in A_t(x),\ a^2 \bmod (x+t) > 1\right\}.$$
Jedes Mengen-Update repräsentiert gleichzeitig alle Startwerte, deren Bahnen inzwischen zu einer dieser Restklassen verschmolzen sind. Sobald \(A_t(x)\) leer ist, sind alle Bahnen beendet, und die Gesamtlänge beträgt \(t+1\). So ersetzt ein einziger deduplizierter Schritt viele getrennte Simulationen.
Wenn die aktive Front auf genau eine Restklasse schrumpft, also
$$A_t(x)=\{v\},$$
dann teilen alle noch lebenden Starts exakt dieselbe Zukunft. Ab diesem Moment ist eine Mengenrepräsentation unnötig: Es bleibt nur noch die einzelne Bahn, die mit dem aktuellen Wert \(v\) und dem aktuellen Modul \(x+t\) weiterläuft. Nach dem Zusammenfallen wird das Problem also von einer Mehrfachsuche zu einer gewöhnlichen Einzeltrajektorie.
Um \(f(n)\) zu berechnen, werden nicht alle \(x\) zwischen \(2\) und \(n\) einzeln geprüft. Stattdessen verwendet die Lösung eine echte obere Schranke auf Intervallen. Sei \(L \le u \le R\). Nimm einen beliebigen Start \(y\) für das Modul \(u\) und führe genau \(R-u\) Updates aus. Danach ist das aktuelle Modul gleich \(R\), und der aktuelle Wert ist irgendeine Restklasse \(b<R\). Die verbleibende Lebensdauer kann also höchstens \(g(R)\) sein. Damit folgt
$$\ell(u,y) \le (R-u) + g(R).$$
Durch Maximieren über alle \(y\) erhält man
$$g(u) \le (R-u) + g(R) \le (R-L) + g(R).$$
Somit besitzt jedes Intervall \([L,R]\) die gültige obere Schranke
$$UB([L,R]) = g(R) + (R-L).$$
Wenn diese Schranke den bisher besten Wert nicht übertreffen kann, darf das ganze Intervall sicher verworfen werden.
Die ersten verschiedenen nichtterminalen Restklassen sind
$$A_1(10)=\{2^2,3^2,4^2,5^2\}\bmod 10 \setminus \{0,1\}=\{4,5,6,9\}.$$
Nun wird die Front fortgeschrieben:
$$A_2(10)=\{a^2 \bmod 11 : a \in A_1(10)\}\setminus\{0,1\}=\{3,4,5\},$$
$$A_3(10)=\{a^2 \bmod 12 : a \in A_2(10)\}\setminus\{0,1\}=\{4,9\},$$
$$A_4(10)=\{a^2 \bmod 13 : a \in A_3(10)\}\setminus\{0,1\}=\{3\}.$$
Ab hier ist die Front ein Singleton, also bleibt nur ein einziger Schwanz. Setzt man mit dem Wert \(3\) und den Modulen \(14,15,16,\dots\) fort, erhält man
$$3 \to 9 \to 6 \to 4 \to 16 \to 4 \to 16 \to 16 \to \cdots \to 8 \to 0.$$
Die terminale \(0\) erscheint direkt nach dem Schritt modulo \(32\). Daher hat die Folge insgesamt \(24\) Terme und somit
$$g(10)=24.$$
Dieses Beispiel illustriert alle Hauptideen zugleich: Symmetrie im ersten Schritt, Deduplizierung gleicher Restklassen und den Wechsel zu einem Einzelpfad, sobald alle überlebenden Starts zusammengefallen sind.
Die Implementierungen in C++, Python und Java folgen derselben Struktur. Zuerst bauen sie die erste aktive Front auf, indem sie wegen der Symmetrie \(y \leftrightarrow x-y\) nur die halbe Menge möglicher Startrestklassen prüfen und die Erstschritt-Werte \(0\) und \(1\) verwerfen. Um bei dieser Initialisierung nicht jedes Quadrat von Grund auf neu zu berechnen, aktualisieren die kompilierten Implementierungen aufeinanderfolgende Quadrate inkrementell.
Solange die Front mehr als eine Restklasse enthält, wird die gesamte Menge Modul für Modul weitergeschoben. Große Fronten verwenden ein dichtes Gesehen-Array für schnelle Deduplizierung; kleine Fronten nutzen eine hashbasierte sparse-Struktur, damit nicht jede Restklasse des Moduls angefasst werden muss. Wird die Front leer, ist die aktuelle Länge die Antwort für dieses \(x\). Bleibt genau eine Restklasse übrig, wird der Rest direkt durch fortgesetztes modulares Quadrieren dieses einen Werts berechnet.
Für die äußere Funktion \(f(n)\) bewertet die Implementierung zunächst ein grobes Gitter von \(x\)-Werten, speichert die berechneten \(g(x)\)-Werte und legt die Intervalle zwischen den Stützpunkten in eine Max-Prioritätswarteschlange, sortiert nach der Schranke \(UB([L,R])\). Danach werden nur noch diejenigen Intervalle halbiert, deren obere Schranke den bisherigen Bestwert überhaupt noch schlagen kann. C++ und Java berechnen die ersten Gitterpunkte parallel, Python verwendet dieselbe Suchidee sequenziell.
Für festes \(x\) kostet der Aufbau der ersten Front \(O(x)\) Zeit, weil die Werte \(2,3,\dots,\lfloor x/2 \rfloor\) durchlaufen werden. Danach kostet ein sparse-Update im Erwartungswert \(O(|A_t(x)|)\), während ein dense-Update \(O(x+t)\) kostet, weil das Deduplizierungsarray die gesamte aktuelle Modulusgröße umfasst. Damit ist die Laufzeit von \(g(x)\) ausgabesensitiv: Entscheidend sind die kumulierten Frontgrößen bis zum Aussterben oder bis zum Zusammenfallen zu einem Singleton.
Der Speicherbedarf einer einzelnen Auswertung von \(g(x)\) beträgt in dichten Phasen \(O(x+t_{\max})\) und in sparse-Phasen \(O(|A_t(x)|)\). Wenn die Intervallsuche für \(f(n)\) insgesamt \(m\) verschiedene Werte von \(x\) auswertet, liegt der Gesamtaufwand bei
$$O\left(m + \sum_{i=1}^{m} T(x_i)\right),$$
wobei \(T(x_i)\) die Kosten für \(g(x_i)\) bezeichnet. Im schlechtesten Fall kann \(m\) immer noch \(O(n)\) sein, in der Praxis schneidet die Intervallschranke aber den größten Teil des Suchraums frühzeitig weg.
\(x \ge 2\) ve \(y\) tamsayılarıyla başlayıp
$$a_0=y,\qquad z_0=x,\qquad a_{t+1}=a_t^2 \bmod z_t,\qquad z_{t+1}=z_t+1$$
tanımını yapıyoruz. Dizi, ilk kez \(a_t \le 1\) olduğunda durduruluyor. Çünkü \(0\) ve \(1\), karesi alındığında değişmeyen terminal değerlerdir. \(a_0\)'dan bu ilk terminal terime kadar olan toplam terim sayısına \(\ell(x,y)\) diyelim. O zaman
$$g(x)=\max_y \ell(x,y),\qquad f(n)=\max_{2 \le x \le n} g(x).$$
Tüm başlangıç değerlerini tek tek denemek çok pahalıdır. Bu yüzden uygulamalar, her adım sonunda hâlâ yaşayabilen farklı kalıntıları izleyerek hesabı sıkıştırır.
Ana gözlem şudur: farklı başlangıçların çok büyük bir kısmı birkaç adım içinde aynı kalıntıya düşer. O ortak kalıntıları takip etmek, her başlangıcı ayrı ayrı simüle etmekten çok daha verimlidir.
Sabit bir \(x\) için ilk güncelleme yalnızca \(y \bmod x\)'e bağlıdır; dolayısıyla \(0 \le y < x\) artıklarını incelemek yeterlidir. Ayrıca
$$ (x-y)^2 \equiv y^2 \pmod{x} $$
olduğu için \(y\) ile \(x-y\) aynı ilk kalıntıya gider. Bu nedenle \(x>2\) için yalnızca \(2 \le y \le \lfloor x/2 \rfloor\) aralığını taramak ve ilk adımda \(1\)'den büyük çıkan kalıntıları tutmak yeterlidir. İlk aktif cepheyi şöyle tanımlayalım:
$$A_1(x)=\left\{y^2 \bmod x : 2 \le y \le \left\lfloor \frac{x}{2} \right\rfloor,\ y^2 \bmod x > 1\right\}.$$
Eğer \(A_1(x)=\varnothing\) ise tüm önemsiz olmayan başlangıçlar tek güncelleme sonra \(0\) ya da \(1\)'e ulaşır; dolayısıyla \(g(x)=2\). Tek özel durum \(x=2\)'dir; burada daha başlangıçta terminal durumdan çıkılamadığı için \(g(2)=1\) olur.
\(t \ge 1\) için \(A_t(x)\), \(t\) güncelleme sonrası hâlâ yaşayan kalıntıların kümesi olsun. O zaman yineleme
$$A_{t+1}(x)=\left\{a^2 \bmod (x+t) : a \in A_t(x),\ a^2 \bmod (x+t) > 1\right\}$$
şeklindedir. Bu küme güncellemesi, o anda aynı kalıntıda birleşmiş bütün başlangıçları tek adımda temsil eder. \(A_t(x)\) boş olduğunda tüm yörüngeler bitmiştir; toplam uzunluk da \(t+1\) olur. Böylece ayrı ayrı yapılan çok sayıda simülasyon, her zamanda tek bir deduplike küme geçişine indirgenir.
Eğer aktif cephe tek elemana düşerse, yani
$$A_t(x)=\{v\},$$
artık yaşayan bütün başlangıçların geleceği birebir aynıdır. Bu noktadan sonra küme tutmanın bir anlamı kalmaz; elde kalan şey, mevcut değer \(v\) ve mevcut modül \(x+t\) ile devam eden tek bir zincirdir. Yani birleşme tamamlandığında problem çoklu başlangıç aramasından tek bir modüler karesini alma zincirine dönüşür.
\(f(n)\)'i hesaplarken bütün \(x\) değerlerini sırayla taramak yerine, güvenli bir aralık üst sınırı kullanılır. \(L \le u \le R\) olsun. Modülü \(u\) olan herhangi bir başlangıcı \(R-u\) adım ilerletelim. Bu noktada güncel modül \(R\) olur ve eldeki değer \(b<R\) biçiminde bir kalıntıdır. Geriye kalan ömür en fazla \(g(R)\) olabilir; dolayısıyla
$$\ell(u,y) \le (R-u) + g(R).$$
Tüm \(y\) üzerinde maksimum alınca
$$g(u) \le (R-u) + g(R) \le (R-L) + g(R)$$
elde edilir. Böylece \([L,R]\) aralığı için geçerli üst sınır
$$UB([L,R]) = g(R) + (R-L)$$
olur. Bu sınır mevcut en iyi değeri geçemiyorsa, bütün aralık güvenle elenir.
İlk farklı ve terminal olmayan kalıntılar şunlardır:
$$A_1(10)=\{2^2,3^2,4^2,5^2\}\bmod 10 \setminus \{0,1\}=\{4,5,6,9\}.$$
Şimdi cepheyi ilerletelim:
$$A_2(10)=\{a^2 \bmod 11 : a \in A_1(10)\}\setminus\{0,1\}=\{3,4,5\},$$
$$A_3(10)=\{a^2 \bmod 12 : a \in A_2(10)\}\setminus\{0,1\}=\{4,9\},$$
$$A_4(10)=\{a^2 \bmod 13 : a \in A_3(10)\}\setminus\{0,1\}=\{3\}.$$
Burada cephe tek elemana düştüğü için artık tek kuyruk kalır. Değer \(3\) ile ve modüller \(14,15,16,\dots\) olacak şekilde devam edilirse
$$3 \to 9 \to 6 \to 4 \to 16 \to 4 \to 16 \to 16 \to \cdots \to 8 \to 0$$
zinciri oluşur. Terminal \(0\), mod \(32\) adımından hemen sonra gelir. Bu yüzden toplam terim sayısı \(24\) olur ve
$$g(10)=24$$
sonucuna ulaşılır. Bu örnek ilk-adım simetrisini, aynı kalıntıların birleştirilmesini ve tek kuyruğa geçişi aynı anda gösterir.
C++, Python ve Java uygulamaları aynı mantığı izler. Önce \(y \leftrightarrow x-y\) simetrisinden yararlanarak olası başlangıç kalıntılarının yalnızca yarısını tarar, ilk adımda \(0\) veya \(1\) verenleri atar ve ilk aktif cepheyi oluşturur. Derlenmiş sürümlerde bu ilk tarama sırasında her kareyi baştan hesaplamak yerine ardışık kareler artımlı biçimde güncellenir.
Aktif cephede birden fazla kalıntı kaldığı sürece uygulama tüm küme üzerinde bir sonraki modüle geçer. Cephe büyükse hızlı deduplikasyon için yoğun bir görüldü dizisi kullanılır; cephe küçükse, modülün bütün kalıntı sınıflarına dokunmamak için hash tabanlı seyrek bir yapı tercih edilir. Cephe boşalırsa o anki uzunluk cevap olur. Cephe tek elemana düşerse geri kalan adımlar bu tek değer üzerinde doğrudan modüler karesini alma şeklinde ilerletilir.
Dıştaki \(f(n)\) hesabında önce kaba bir \(x\) ızgarası örneklenir, hesaplanan \(g(x)\) değerleri önbelleğe alınır ve örnek noktalar arasındaki aralıklar \(UB([L,R])\) değerine göre bir maksimum öncelik kuyruğuna konur. Daha sonra yalnızca üst sınırı mevcut en iyi cevabı aşabilecek aralıklar ortadan ikiye bölünür. C++ ve Java ilk ızgara noktalarını paralel hesaplar; Python aynı arama stratejisini sıralı biçimde uygular.
Sabit bir \(x\) için ilk aktif cepheyi kurmak \(O(x)\) zaman alır; çünkü \(2,3,\dots,\lfloor x/2 \rfloor\) aralığı taranır. Sonrasında seyrek modda bir cephe güncellemesi beklenen \(O(|A_t(x)|)\) zamanda, yoğun modda ise deduplikasyon dizisi güncel modülü kapladığı için \(O(x+t)\) zamanda yapılır. Dolayısıyla \(g(x)\)'in çalışma süresi çıktı-duyarlıdır; belirleyici olan şey bütün olası başlangıç sayısı değil, sönene ya da tek elemana düşünceye kadar biriken cephe boyutlarıdır.
Tek bir \(g(x)\) değerlendirmesinin bellek kullanımı yoğun evrelerde \(O(x+t_{\max})\), seyrek evrelerde ise \(O(|A_t(x)|)\) düzeyindedir. Eğer \(f(n)\) için aralık araması toplam \(m\) farklı \(x\) noktası değerlendirirse, toplam maliyet
$$O\left(m + \sum_{i=1}^{m} T(x_i)\right)$$
olur; burada \(T(x_i)\), \(g(x_i)\)'i hesaplama maliyetidir. En kötü durumda \(m\) hâlâ \(O(n)\) olabilir, fakat aralık üst sınırı pratikte alt aralıkların çoğunu erkenden budar.
Partimos de enteros \(x \ge 2\) y \(y\), y definimos
$$a_0=y,\qquad z_0=x,\qquad a_{t+1}=a_t^2 \bmod z_t,\qquad z_{t+1}=z_t+1.$$
La sucesión se cuenta hasta la primera vez que \(a_t \le 1\). Como \(0\) y \(1\) permanecen fijos al elevar al cuadrado, son estados terminales. Sea \(\ell(x,y)\) el número de términos desde \(a_0\) hasta ese primer término terminal. Entonces
$$g(x)=\max_y \ell(x,y),\qquad f(n)=\max_{2 \le x \le n} g(x).$$
Probar todos los valores iniciales por fuerza bruta es demasiado costoso, así que las implementaciones reorganizan el cálculo alrededor de los residuos distintos que aún pueden seguir vivos después de cada paso.
La observación central es que muchos inicios diferentes caen muy pronto en el mismo residuo. Si seguimos esos residuos compartidos en lugar de cada trayectoria por separado, el problema se reduce de forma drástica.
Para un \(x\) fijo, la primera actualización depende solo de \(y \bmod x\), así que basta considerar \(0 \le y < x\). Además,
$$ (x-y)^2 \equiv y^2 \pmod{x}, $$
de modo que \(y\) y \(x-y\) se fusionan inmediatamente. Para \(x>2\), solo hace falta revisar \(2 \le y \le \lfloor x/2 \rfloor\) y conservar los residuos del primer paso mayores que \(1\). Definimos la primera frontera activa como
$$A_1(x)=\left\{y^2 \bmod x : 2 \le y \le \left\lfloor \frac{x}{2} \right\rfloor,\ y^2 \bmod x > 1\right\}.$$
Si \(A_1(x)=\varnothing\), entonces cualquier inicio no trivial llega a \(0\) o \(1\) tras una sola actualización, y por tanto \(g(x)=2\). La única excepción es \(x=2\), donde incluso el inicio ya es terminal y \(g(2)=1\).
Para \(t \ge 1\), sea \(A_t(x)\) el conjunto de residuos que siguen vivos después de \(t\) actualizaciones. La recurrencia es
$$A_{t+1}(x)=\left\{a^2 \bmod (x+t) : a \in A_t(x),\ a^2 \bmod (x+t) > 1\right\}.$$
Cada actualización del conjunto representa simultáneamente todos los valores iniciales cuyas trayectorias ya se han fusionado en alguno de esos residuos. Cuando \(A_t(x)\) se vuelve vacío, todas las trayectorias han terminado, así que la longitud total es \(t+1\). De este modo, muchos recorridos individuales se sustituyen por una sola transición deduplicada por paso temporal.
Si la frontera se reduce a un único residuo, es decir,
$$A_t(x)=\{v\},$$
entonces todos los inicios que siguen vivos comparten exactamente el mismo futuro. A partir de ese momento ya no hace falta mantener una estructura de conjunto: lo único que queda es la trayectoria individual que empieza con el valor \(v\) y el módulo actual \(x+t\). Una vez ocurre esta coalescencia, la búsqueda sobre muchos inicios se convierte en una sola cadena de cuadrados modulares.
Para calcular \(f(n)\), las implementaciones no recorren todos los \(x\) uno por uno. En su lugar usan una cota superior rigurosa sobre intervalos. Fijemos \(L \le u \le R\). Tomemos cualquier inicio \(y\) para el módulo \(u\) y avancemos exactamente \(R-u\) actualizaciones. En ese instante el módulo actual ya es \(R\), y el valor actual es algún residuo \(b<R\). Por lo tanto, la vida restante no puede exceder \(g(R)\), y obtenemos
$$\ell(u,y) \le (R-u) + g(R).$$
Al maximizar sobre todos los \(y\), resulta
$$g(u) \le (R-u) + g(R) \le (R-L) + g(R).$$
Así, cada intervalo \([L,R]\) tiene la cota válida
$$UB([L,R]) = g(R) + (R-L).$$
Si esa cota ya no puede superar el mejor valor conocido, se puede descartar todo el intervalo con seguridad.
Los primeros residuos distintos y no terminales son
$$A_1(10)=\{2^2,3^2,4^2,5^2\}\bmod 10 \setminus \{0,1\}=\{4,5,6,9\}.$$
Ahora propagamos la frontera:
$$A_2(10)=\{a^2 \bmod 11 : a \in A_1(10)\}\setminus\{0,1\}=\{3,4,5\},$$
$$A_3(10)=\{a^2 \bmod 12 : a \in A_2(10)\}\setminus\{0,1\}=\{4,9\},$$
$$A_4(10)=\{a^2 \bmod 13 : a \in A_3(10)\}\setminus\{0,1\}=\{3\}.$$
En ese punto la frontera ya es un singleton, así que solo queda una cola. Si seguimos desde el valor \(3\) con módulos \(14,15,16,\dots\), obtenemos
$$3 \to 9 \to 6 \to 4 \to 16 \to 4 \to 16 \to 16 \to \cdots \to 8 \to 0.$$
El valor terminal \(0\) aparece justo después del paso módulo \(32\). Por tanto, la sucesión tiene \(24\) términos en total y
$$g(10)=24.$$
Este ejemplo muestra a la vez la simetría del primer paso, la deduplicación de residuos iguales y el cambio a una sola cola cuando todos los inicios supervivientes ya se han fusionado.
Las implementaciones en C++, Python y Java siguen la misma idea. Primero construyen la frontera inicial examinando solo la mitad de los residuos iniciales posibles gracias a la simetría \(y \leftrightarrow x-y\), y descartan los residuos del primer paso iguales a \(0\) o \(1\). Para no recalcular cada cuadrado desde cero durante ese barrido inicial, las implementaciones compiladas actualizan cuadrados consecutivos de manera incremental.
Mientras la frontera contenga más de un residuo, la implementación avanza todo el conjunto un módulo cada vez. Si la frontera es grande, usa un arreglo denso de vistos para deduplicar con rapidez; si es pequeña, usa un contenedor disperso basado en hashing para no tocar todas las clases residuales del módulo. Cuando la frontera queda vacía, la longitud actual ya es la respuesta para ese \(x\). Cuando queda un solo residuo, el resto se sigue mediante cuadrados modulares directos de ese valor.
Para la función exterior \(f(n)\), la implementación primero toma una malla gruesa de valores de \(x\), almacena en caché los \(g(x)\) obtenidos y coloca los intervalos entre puntos muestreados en una cola de prioridad máxima ordenada por \(UB([L,R])\). Después solo biseca los intervalos cuya cota superior todavía puede mejorar la mejor respuesta conocida. Las versiones de C++ y Java calculan en paralelo los puntos iniciales de la malla; la de Python usa la misma estrategia de búsqueda de forma secuencial.
Para un \(x\) fijo, construir la primera frontera cuesta \(O(x)\) tiempo, porque se recorren los valores \(2,3,\dots,\lfloor x/2 \rfloor\). Después, una actualización sparse cuesta \(O(|A_t(x)|)\) en esperanza, mientras que una actualización dense cuesta \(O(x+t)\) porque el arreglo de deduplicación cubre todo el módulo actual. En consecuencia, el tiempo de ejecución de \(g(x)\) depende de la salida real: lo que manda son los tamaños acumulados de las fronteras hasta que desaparecen o se reducen a un singleton.
La memoria de una evaluación de \(g(x)\) es \(O(x+t_{\max})\) en fases dense y \(O(|A_t(x)|)\) en fases sparse. Si la búsqueda por intervalos para \(f(n)\) evalúa \(m\) valores distintos de \(x\), el coste total es
$$O\left(m + \sum_{i=1}^{m} T(x_i)\right),$$
donde \(T(x_i)\) es el coste de calcular \(g(x_i)\). En el peor caso todavía puede ocurrir que \(m=O(n)\), pero en la práctica la cota por intervalos poda la mayoría de los subintervalos mucho antes.
给定整数 \(x \ge 2\) 和 \(y\)，定义
$$a_0=y,\qquad z_0=x,\qquad a_{t+1}=a_t^2 \bmod z_t,\qquad z_{t+1}=z_t+1.$$
我们把序列一直生成到第一次出现 \(a_t \le 1\) 为止。由于 \(0\) 和 \(1\) 在平方后仍然保持不变，它们就是终止状态。记 \(\ell(x,y)\) 为从 \(a_0\) 开始到第一个终止项为止的总项数，则
$$g(x)=\max_y \ell(x,y),\qquad f(n)=\max_{2 \le x \le n} g(x).$$
如果把所有起点 \(y\) 都逐个暴力模拟，代价会非常高。因此实现的核心不是追踪每一条单独轨迹，而是追踪“在某一步之后仍然可能存活的不同余数”。
真正起作用的性质是“合流”。很多不同的起点在很短时间内就会落入同一个余数，于是它们后续的演化完全相同。只要改为维护这些共享状态，而不是维护每个起点本身，计算规模就会大幅缩小。
对于固定的 \(x\)，第一次更新只依赖于 \(y \bmod x\)，所以只需要考虑 \(0 \le y < x\) 的代表元。另外还有一个对称性：
$$ (x-y)^2 \equiv y^2 \pmod{x}. $$
这说明起点 \(y\) 与 \(x-y\) 在第一步之后会立刻合并到同一个余数。因此当 \(x>2\) 时，只需检查
$$2 \le y \le \left\lfloor \frac{x}{2} \right\rfloor$$
这一半区间，并且只保留第一步结果大于 \(1\) 的余数。定义第一层活跃前沿为
$$A_1(x)=\left\{y^2 \bmod x : 2 \le y \le \left\lfloor \frac{x}{2} \right\rfloor,\ y^2 \bmod x > 1\right\}.$$
如果 \(A_1(x)=\varnothing\)，就表示所有非平凡起点在一次更新之后都已经到达 \(0\) 或 \(1\)，于是 \(g(x)=2\)。唯一需要单独指出的是 \(x=2\)：此时一开始就没有非终止状态，因此 \(g(2)=1\)。
对 \(t \ge 1\)，设 \(A_t(x)\) 是经过 \(t\) 次更新后仍然存活的余数集合。则有递推式
$$A_{t+1}(x)=\left\{a^2 \bmod (x+t) : a \in A_t(x),\ a^2 \bmod (x+t) > 1\right\}.$$
这个集合一次性代表了所有已经合并到这些余数上的起点。只要多个起点落在同一个余数上，后续就再也不必分别计算它们。于是每个时间步不再是“很多条轨迹一起跑”，而是“一个去重后的集合做一次更新”。当 \(A_t(x)\) 变为空集时，说明所有可能的轨迹都已经终止，总长度就是 \(t+1\)。
如果某一步之后前沿只剩一个余数，也就是
$$A_t(x)=\{v\},$$
那么所有尚未终止的起点此后都会走完全相同的后缀。此时继续维护集合已经没有意义，因为问题已经退化成“从当前值 \(v\)、当前模数 \(x+t\) 出发的一条普通链”。换句话说，前沿一旦缩成单点，多起点搜索就结束了，后面只需直接做模平方迭代即可。
计算 \(f(n)\) 时，实现并不会从 \(2\) 到 \(n\) 把每个 \(x\) 都算一遍，而是利用一个严格成立的区间上界。设 \(L \le u \le R\)。对模数 \(u\) 的任意起点 \(y\)，把序列先推进恰好 \(R-u\) 步。此时当前模数已经变成 \(R\)，而当前值一定是某个满足 \(b<R\) 的余数。接下来最多还能持续 \(g(R)\) 项，所以
$$\ell(u,y) \le (R-u) + g(R).$$
对所有 \(y\) 取最大值，就得到
$$g(u) \le (R-u) + g(R) \le (R-L) + g(R).$$
因此区间 \([L,R]\) 的有效上界是
$$UB([L,R]) = g(R) + (R-L).$$
如果这个上界已经不可能超过当前最好值，那么整个区间都可以安全剪枝，不必继续细分。
第一步之后所有不同且未终止的余数为
$$A_1(10)=\{2^2,3^2,4^2,5^2\}\bmod 10 \setminus \{0,1\}=\{4,5,6,9\}.$$
然后逐层推进：
$$A_2(10)=\{a^2 \bmod 11 : a \in A_1(10)\}\setminus\{0,1\}=\{3,4,5\},$$
$$A_3(10)=\{a^2 \bmod 12 : a \in A_2(10)\}\setminus\{0,1\}=\{4,9\},$$
$$A_4(10)=\{a^2 \bmod 13 : a \in A_3(10)\}\setminus\{0,1\}=\{3\}.$$
此时前沿已经缩成单点，所以后面只剩一条尾链。继续从数值 \(3\) 出发，并让模数依次取 \(14,15,16,\dots\)，就会得到
$$3 \to 9 \to 6 \to 4 \to 16 \to 4 \to 16 \to 16 \to \cdots \to 8 \to 0.$$
终止值 \(0\) 出现在模 \(32\) 那一步之后，因此整个序列共有 \(24\) 项，也就是
$$g(10)=24.$$
这个例子同时展示了三件事：第一步的对称性、不同起点合并成同一余数的去重效果，以及前沿缩成单点后可以直接切换为单链计算。
C++、Python 和 Java 三个实现遵循同一套思路。它们先利用 \(y \leftrightarrow x-y\) 的对称性，只扫描一半的起始余数，并丢弃第一步结果为 \(0\) 或 \(1\) 的情况，从而构造初始前沿。为了避免在初始化阶段反复从头计算平方，编译型实现还会用递推方式更新相邻起点的平方值。
只要前沿里还有多个余数，实现就把整个集合一起推进到下一个模数。当前沿很大时，用稠密的 seen 数组快速去重；当前沿较小时，改用基于哈希的稀疏容器，避免无谓地扫描整个模空间。当前沿为空时，当前长度就是该 \(x\) 的答案；当前沿只剩一个余数时，后续部分就直接按单条链继续做模平方。
对于外层函数 \(f(n)\)，实现先在一个较粗的 \(x\) 网格上取样，缓存已经算出的 \(g(x)\)，再把相邻采样点之间的区间按 \(UB([L,R])\) 放入最大优先队列。之后只细分那些上界仍有可能改写当前最佳答案的区间。C++ 和 Java 会并行计算初始采样点，Python 则按相同的区间搜索逻辑顺序执行。
对固定的 \(x\)，构造第一层前沿需要 \(O(x)\) 时间，因为要扫描 \(2,3,\dots,\lfloor x/2 \rfloor\)。之后若采用稀疏模式，一次前沿更新的期望代价为 \(O(|A_t(x)|)\)；若采用稠密模式，则因为去重数组覆盖整个当前模数，单次更新代价为 \(O(x+t)\)。因此 \(g(x)\) 的运行时间是输出敏感的：真正决定成本的不是可能起点的总数，而是前沿在消失或缩成单点之前的累计规模。
单次计算 \(g(x)\) 的空间消耗在稠密阶段为 \(O(x+t_{\max})\)，在稀疏阶段为 \(O(|A_t(x)|)\)。如果区间搜索总共评估了 \(m\) 个不同的 \(x\) 值，那么总成本为
$$O\left(m + \sum_{i=1}^{m} T(x_i)\right),$$
其中 \(T(x_i)\) 表示计算 \(g(x_i)\) 的代价。最坏情况下 \(m\) 仍可能达到 \(O(n)\)，但在实际运行中，区间上界通常会在很早的阶段剪掉绝大部分子区间。
Пусть заданы целые числа \(x \ge 2\) и \(y\). Определим
$$a_0=y,\qquad z_0=x,\qquad a_{t+1}=a_t^2 \bmod z_t,\qquad z_{t+1}=z_t+1.$$
Последовательность строится до первого момента, когда \(a_t \le 1\). Значения \(0\) и \(1\) являются терминальными, потому что при возведении в квадрат они не меняются. Обозначим через \(\ell(x,y)\) число членов от \(a_0\) до первого терминального члена включительно. Тогда
$$g(x)=\max_y \ell(x,y),\qquad f(n)=\max_{2 \le x \le n} g(x).$$
Полный перебор всех стартов слишком дорог, поэтому реализации перестраивают задачу: они отслеживают не отдельные начальные значения, а различные остатки, которые еще могут оставаться живыми после каждого шага.
Главное наблюдение состоит в том, что многие разные старты очень быстро попадают в один и тот же остаток. После такого слияния их дальнейшее поведение полностью совпадает. Значит, выгодно отслеживать эти общие состояния, а не все траектории по отдельности.
Для фиксированного \(x\) первое обновление зависит только от \(y \bmod x\), поэтому достаточно рассматривать остатки \(0 \le y < x\). Кроме того, выполняется симметрия
$$ (x-y)^2 \equiv y^2 \pmod{x}. $$
Следовательно, старты \(y\) и \(x-y\) сразу сливаются. При \(x>2\) нужно проверять только диапазон \(2 \le y \le \lfloor x/2 \rfloor\) и сохранять лишь те остатки первого шага, которые больше \(1\). Введем первую активную фронту:
$$A_1(x)=\left\{y^2 \bmod x : 2 \le y \le \left\lfloor \frac{x}{2} \right\rfloor,\ y^2 \bmod x > 1\right\}.$$
Если \(A_1(x)=\varnothing\), то любой нетривиальный старт за один шаг приходит в \(0\) или \(1\), а значит \(g(x)=2\). Единственное исключение: \(x=2\), где уже стартовый уровень терминален и \(g(2)=1\).
Для \(t \ge 1\) обозначим через \(A_t(x)\) множество остатков, которые остаются живыми после \(t\) обновлений. Тогда выполняется рекуррентное соотношение
$$A_{t+1}(x)=\left\{a^2 \bmod (x+t) : a \in A_t(x),\ a^2 \bmod (x+t) > 1\right\}.$$
Одно обновление множества одновременно описывает все стартовые значения, чьи траектории уже слились в один из этих остатков. Когда \(A_t(x)\) становится пустым, все траектории завершились, и общая длина равна \(t+1\). Так много отдельных симуляций заменяются одним дедуплицированным переходом на каждом шаге.
Если активная фронта сжимается до одного остатка, то есть
$$A_t(x)=\{v\},$$
то все еще живые старты имеют абсолютно одинаковое будущее. С этого момента структура множества уже не нужна: остается лишь одна цепочка, начинающаяся со значения \(v\) при текущем модуле \(x+t\). После слияния задача перестает быть поиском по многим стартам и превращается в обычную одиночную цепочку модульных квадратов.
Чтобы вычислить \(f(n)\), реализации не просматривают подряд все \(x\) от \(2\) до \(n\). Вместо этого они используют строгую верхнюю оценку на интервале. Пусть \(L \le u \le R\). Возьмем любой старт \(y\) для модуля \(u\) и продвинем последовательность ровно на \(R-u\) шагов. После этого текущий модуль станет равен \(R\), а текущее значение будет некоторым остатком \(b<R\). Оставшаяся длина не может превышать \(g(R)\), поэтому
$$\ell(u,y) \le (R-u) + g(R).$$
Максимизируя по всем \(y\), получаем
$$g(u) \le (R-u) + g(R) \le (R-L) + g(R).$$
Значит, для интервала \([L,R]\) корректна верхняя оценка
$$UB([L,R]) = g(R) + (R-L).$$
Если эта оценка уже не превосходит текущий лучший найденный результат, весь интервал можно безопасно отбросить.
Первые различные нетерминальные остатки имеют вид
$$A_1(10)=\{2^2,3^2,4^2,5^2\}\bmod 10 \setminus \{0,1\}=\{4,5,6,9\}.$$
Дальше фронта развивается так:
$$A_2(10)=\{a^2 \bmod 11 : a \in A_1(10)\}\setminus\{0,1\}=\{3,4,5\},$$
$$A_3(10)=\{a^2 \bmod 12 : a \in A_2(10)\}\setminus\{0,1\}=\{4,9\},$$
$$A_4(10)=\{a^2 \bmod 13 : a \in A_3(10)\}\setminus\{0,1\}=\{3\}.$$
Здесь фронта уже стала одноэлементной, так что остается единственный хвост. Если продолжить со значением \(3\) при модулях \(14,15,16,\dots\), получится цепочка
$$3 \to 9 \to 6 \to 4 \to 16 \to 4 \to 16 \to 16 \to \cdots \to 8 \to 0.$$
Терминальный ноль появляется сразу после шага по модулю \(32\). Следовательно, общая длина равна \(24\), то есть
$$g(10)=24.$$
Этот пример одновременно показывает симметрию первого шага, дедупликацию совпавших остатков и переход к одиночному хвосту после полного слияния всех выживших стартов.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала они строят начальную фронту, просматривая только половину стартовых остатков благодаря симметрии \(y \leftrightarrow x-y\), и сразу отбрасывают случаи, где первый шаг дает \(0\) или \(1\). Чтобы не пересчитывать каждый квадрат заново на этапе инициализации, компилируемые реализации обновляют последовательные квадраты инкрементально.
Пока во фронте больше одного остатка, реализация продвигает сразу весь набор на следующий модуль. Для больших фронт используется плотный массив отметок seen, который быстро убирает дубликаты; для малых фронт применяется разреженный хеш-контейнер, чтобы не трогать все классы вычетов текущего модуля. Если фронта опустела, текущая длина и есть ответ для данного \(x\). Если остался один остаток, остаток вычисления продолжается как прямая цепочка модульных квадратов этого значения.
Для внешней функции \(f(n)\) реализация сначала берет грубую сетку значений \(x\), кэширует найденные \(g(x)\), а затем помещает интервалы между соседними точками в максимальную очередь с приоритетом по ключу \(UB([L,R])\). После этого делятся пополам только те интервалы, чья верхняя оценка еще может улучшить текущий лучший ответ. Реализации на C++ и Java вычисляют начальные точки сетки параллельно, а версия на Python использует ту же самую стратегию поиска последовательно.
Для фиксированного \(x\) построение первой фронты требует \(O(x)\) времени, поскольку просматриваются значения \(2,3,\dots,\lfloor x/2 \rfloor\). Далее одно разреженное обновление фронты стоит в среднем \(O(|A_t(x)|)\), а одно плотное обновление стоит \(O(x+t)\), потому что массив дедупликации покрывает весь текущий модуль. Следовательно, время работы для \(g(x)\) зависит от реального поведения процесса: его определяют суммарные размеры фронт до вымирания или до сжатия в одно значение.
Память для одного вычисления \(g(x)\) равна \(O(x+t_{\max})\) в плотных фазах и \(O(|A_t(x)|)\) в разреженных. Если интервальный поиск для \(f(n)\) вычисляет \(m\) различных значений \(x\), то общая стоимость равна
$$O\left(m + \sum_{i=1}^{m} T(x_i)\right),$$
где \(T(x_i)\) обозначает цену вычисления \(g(x_i)\). В худшем случае \(m\) все еще может быть порядка \(O(n)\), но на практике интервальная оценка обычно отсеивает большую часть подинтервалов значительно раньше.
نبدأ بعددين صحيحين \(x \ge 2\) و\(y\)، ثم نعرّف
$$a_0=y,\qquad z_0=x,\qquad a_{t+1}=a_t^2 \bmod z_t,\qquad z_{t+1}=z_t+1.$$
نستمر في توليد المتتالية حتى أول مرة يصبح فيها \(a_t \le 1\). وبما أن \(0\) و\(1\) يبقيان كما هما بعد التربيع، فهما حالتان نهائيتان. نرمز بـ \(\ell(x,y)\) إلى عدد الحدود من \(a_0\) حتى أول حد نهائي. بعد ذلك نعرّف
$$g(x)=\max_y \ell(x,y),\qquad f(n)=\max_{2 \le x \le n} g(x).$$
الفحص المباشر لكل قيم البداية مكلف جدًا، لذلك تعتمد التطبيقات على تتبع البواقي المختلفة التي ما زال يمكن أن تبقى حيّة بعد كل خطوة، بدلًا من تتبع كل بداية على حدة.
الفكرة الحاسمة هي أن عددًا كبيرًا من بدايات مختلفة يندمج سريعًا في نفس الباقي. بعد هذا الاندماج يصبح مستقبلها واحدًا تمامًا. لذلك فإن تتبع الحالات المشتركة أكثر كفاءة بكثير من تتبع كل مسار منفصلًا.
عند تثبيت \(x\)، فإن أول تحديث يعتمد فقط على \(y \bmod x\)، ولذلك يكفي فحص الممثلين \(0 \le y < x\). ولدينا أيضًا التناظر
$$ (x-y)^2 \equiv y^2 \pmod{x}. $$
وهذا يعني أن البدايتين \(y\) و\(x-y\) تندمجان فورًا بعد الخطوة الأولى. لذلك عندما يكون \(x>2\)، يكفي فحص المجال
$$2 \le y \le \left\lfloor \frac{x}{2} \right\rfloor$$
والاحتفاظ فقط بالبواقي الناتجة التي تزيد على \(1\). نعرّف الجبهة النشطة الأولى كما يلي:
$$A_1(x)=\left\{y^2 \bmod x : 2 \le y \le \left\lfloor \frac{x}{2} \right\rfloor,\ y^2 \bmod x > 1\right\}.$$
إذا كان \(A_1(x)=\varnothing\)، فهذا يعني أن كل بداية غير تافهة تصل إلى \(0\) أو \(1\) بعد تحديث واحد فقط، وبالتالي \(g(x)=2\). والاستثناء الوحيد هو \(x=2\)، حيث لا توجد حالة غير نهائية أصلًا، ومن ثم \(g(2)=1\).
لكل \(t \ge 1\)، لتكن \(A_t(x)\) مجموعة البواقي التي ما زالت حيّة بعد \(t\) تحديثات. عندئذٍ يكون التكرار
$$A_{t+1}(x)=\left\{a^2 \bmod (x+t) : a \in A_t(x),\ a^2 \bmod (x+t) > 1\right\}.$$
كل تحديث للمجموعة يمثل في وقت واحد جميع قيم البداية التي اندمجت مساراتها بالفعل في إحدى هذه البواقي. وعندما تصبح \(A_t(x)\) فارغة، تكون جميع المسارات قد انتهت، ويكون الطول الكلي مساويًا لـ \(t+1\). بهذه الطريقة نستبدل عددًا كبيرًا من المحاكاة المنفصلة بتحديث واحد لمجموعة منزوعة التكرار في كل زمن.
إذا تقلصت الجبهة إلى باقٍ واحد فقط، أي
$$A_t(x)=\{v\},$$
فإن كل البدايات التي ما زالت حيّة تشترك الآن في المستقبل نفسه تمامًا. عند هذه النقطة لا تعود بنية المجموعة مفيدة؛ فما بقي هو مسار واحد يبدأ من القيمة \(v\) ومعامل التوافق الحالي \(x+t\). أي إن المسألة بعد الاندماج الكامل تتحول من بحث متعدد البدايات إلى سلسلة واحدة عادية من التربيع المعياري.
لحساب \(f(n)\)، لا تقوم التطبيقات بتجربة كل \(x\) من \(2\) إلى \(n\) مباشرة، بل تستخدم حدًا علويًا صحيحًا على كل فترة. خذ \(L \le u \le R\). إذا بدأنا من أي \(y\) مناسب للموديل \(u\) وحرّكنا السلسلة عددًا مقداره \(R-u\) من التحديثات، فسنصل إلى حالة يكون فيها الموديل الحالي مساويًا لـ \(R\)، وتكون القيمة الحالية بعض البواقي \(b<R\). ومن ثم لا يمكن أن يتجاوز العمر المتبقي \(g(R)\)، ولذلك
$$\ell(u,y) \le (R-u) + g(R).$$
وبأخذ القيمة العظمى على جميع \(y\)، نحصل على
$$g(u) \le (R-u) + g(R) \le (R-L) + g(R).$$
إذن يملك كل مجال \([L,R]\) الحد العلوي الصحيح
$$UB([L,R]) = g(R) + (R-L).$$
وإذا كان هذا الحد لا يستطيع تجاوز أفضل قيمة معروفة حاليًا، فيمكن استبعاد المجال كله بأمان.
البواقي المختلفة غير النهائية بعد الخطوة الأولى هي
$$A_1(10)=\{2^2,3^2,4^2,5^2\}\bmod 10 \setminus \{0,1\}=\{4,5,6,9\}.$$
ثم ندفع الجبهة كما يلي:
$$A_2(10)=\{a^2 \bmod 11 : a \in A_1(10)\}\setminus\{0,1\}=\{3,4,5\},$$
$$A_3(10)=\{a^2 \bmod 12 : a \in A_2(10)\}\setminus\{0,1\}=\{4,9\},$$
$$A_4(10)=\{a^2 \bmod 13 : a \in A_3(10)\}\setminus\{0,1\}=\{3\}.$$
هنا أصبحت الجبهة عنصرًا واحدًا، ولذلك لا يبقى إلا ذيل واحد. إذا أكملنا من القيمة \(3\) مع الموديلات \(14,15,16,\dots\)، نحصل على
$$3 \to 9 \to 6 \to 4 \to 16 \to 4 \to 16 \to 16 \to \cdots \to 8 \to 0.$$
تظهر القيمة النهائية \(0\) مباشرة بعد خطوة الموديل \(32\)، ولهذا يكون طول السلسلة الكلي \(24\)، وبالتالي
$$g(10)=24.$$
هذا المثال يوضح في وقت واحد تناظر الخطوة الأولى، وإزالة التكرار بين البواقي المتساوية، والانتقال إلى ذيل أحادي عندما تندمج جميع البدايات الباقية في حالة واحدة.
تتبع تطبيقات C++ وPython وJava المنطق نفسه. فهي تبدأ ببناء الجبهة الأولى عبر فحص نصف البواقي الابتدائية فقط، مستفيدة من التناظر \(y \leftrightarrow x-y\)، ثم تستبعد الحالات التي تعطي \(0\) أو \(1\) بعد الخطوة الأولى. ولتجنب إعادة حساب كل مربع من البداية أثناء هذا المسح الأولي، تقوم التطبيقات المترجمة بتحديث مربعات القيم المتتالية بصورة تراكمية.
ما دامت الجبهة تحتوي على أكثر من باقٍ واحد، فإن التنفيذ يدفع المجموعة كلها إلى الموديل التالي دفعة واحدة. عندما تكون الجبهة كبيرة، يستخدم تمثيلًا كثيفًا قائمًا على مصفوفة seen لإزالة التكرار بسرعة. وعندما تصغر الجبهة، ينتقل إلى حاوية متناثرة مبنية على التجزئة حتى لا يضطر إلى لمس كل فئة باقية في الموديل الحالي. إذا أصبحت الجبهة فارغة فالإجابة لذلك \(x\) هي الطول الحالي. وإذا بقي عنصر واحد فقط، تُحسب بقية السلسلة بتربيع معياري مباشر لتلك القيمة الوحيدة.
أما في حساب \(f(n)\)، فتأخذ الشيفرة أولًا عينة خشنة من قيم \(x\)، وتخزن قيم \(g(x)\) المحسوبة، ثم تضع الفترات بين نقاط العينة في طابور أولوية أعظمي مرتب حسب \(UB([L,R])\). بعد ذلك لا تُقسَّم إلا الفترات التي ما زال حدها العلوي قادرًا على تحسين أفضل جواب معروف. يحسب تنفيذا C++ وJava نقاط العينة الأولى بالتوازي، بينما يستخدم تنفيذ Python الاستراتيجية نفسها ولكن بصورة متسلسلة.
بالنسبة إلى \(x\) ثابت، فإن بناء الجبهة الأولى يحتاج إلى زمن \(O(x)\)، لأننا نفحص القيم \(2,3,\dots,\lfloor x/2 \rfloor\). بعد ذلك، يكلف تحديث واحد في النمط المتناثر \(O(|A_t(x)|)\) في المتوسط، بينما يكلف التحديث في النمط الكثيف \(O(x+t)\) لأن مصفوفة إزالة التكرار تغطي الموديل الحالي كله. لذلك فإن زمن حساب \(g(x)\) حساس للبنية الفعلية للمسار: العامل الحاسم ليس عدد نقاط البداية الممكنة وحده، بل الأحجام التراكمية للجبهات حتى تنقرض أو تنكمش إلى عنصر واحد.
استهلاك الذاكرة لتقييم واحد لـ \(g(x)\) يساوي \(O(x+t_{\max})\) في المراحل الكثيفة و\(O(|A_t(x)|)\) في المراحل المتناثرة. وإذا قامت عملية البحث على الفترات في \(f(n)\) بتقييم \(m\) قيم مختلفة لـ \(x\)، فإن الكلفة الإجمالية تساوي
$$O\left(m + \sum_{i=1}^{m} T(x_i)\right),$$
حيث تمثل \(T(x_i)\) كلفة حساب \(g(x_i)\). وفي أسوأ الأحوال يمكن أن يبقى \(m\) من رتبة \(O(n)\)، لكن حد الفترات العلوي ينجح عمليًا في تقليم معظم المجالات الفرعية قبل الوصول إلى ذلك.