For every integer \(j\in\{2,\dots,n\}\), write its prime factors in nondecreasing order and treat that ordered list as one pile. One round removes the first factor from every nonempty pile, sorts the extracted factors, and appends them as a new pile. After \(m\) rounds, \(S(n,m)\) is the sum of the products of the factors still remaining in the active piles, taken modulo \(1234567891\). The challenge is that the target round count is \(10^{16}\), so the solution must replace long simulation by a structural description of the stabilized shuffle.
The implementations work with prime-factor lists directly. The key is to separate two layers of the process: the evolution of pile lengths, and the evolution of the sorted factors extracted at each round.
Let the initial pile for \(j\) be the ascending prime-factor list of \(j\). If \(\Omega(j)\) denotes the total number of prime factors of \(j\), counted with multiplicity, then the total number of stored factors is
$$T=\sum_{j=2}^{n}\Omega(j).$$
This quantity never changes. In every round we remove exactly one factor from each active pile, then we create one new pile whose length is exactly the number of active piles in that round. Therefore only the distribution of lengths changes, not the total factor count.
If the current pile lengths are \(\lambda_1,\dots,\lambda_k\), then the next round transforms them into the positive parts of
$$(\lambda_1-1,\dots,\lambda_k-1,k).$$
This is the same length update that appears in Bulgarian solitaire. It explains why the number of relevant pile positions is only on the order of \(\sqrt{T}\): after the transient, the lengths cluster around a staircase shape rather than staying spread across all \(T\) factors.
At round \(t\), let the extracted factors after sorting be
$$E_t=\bigl(a_1(t),a_2(t),\dots,a_{k_t}(t)\bigr),\qquad a_1(t)\le a_2(t)\le \dots \le a_{k_t}(t),$$
where \(k_t\) is the number of active piles at that round. For bookkeeping, extend the definition by setting
$$a_k(t)=1,\quad k>k_t.$$
This padding is harmless because multiplying by \(1\) does not change a pile product.
The new pile created at round \(t\) is exactly the list \(E_t\). One round later its first entry \(a_1(t)\) is removed; two rounds later its second entry \(a_2(t)\) is removed; in general, its \(k\)-th entry is extracted exactly \(k\) rounds after the pile is born.
Once the length dynamics has settled, the shuffle becomes shift-invariant: the same geometric position inside a pile is revisited after a fixed number of rounds. Because the \(k\)-th entry of a newborn pile survives for exactly \(k\) rounds, the \(k\)-th extracted row naturally repeats with period \(k\).
So after a transient time \(t_0\), the implementations use the periodic description
$$a_k(t+k)=a_k(t)\qquad (t\ge t_0),$$
or equivalently
$$a_k(t)=p_k(t\bmod k),$$
where \(p_k\) is the stored cycle for row \(k\). The code does not assume these cycles in advance; it simulates until the last \(k\) values of row \(k\) repeat consistently, then records that row as periodic.
Consider the state after round \(m\). A pile created \(d\) rounds earlier was born at round \(m-1-d\). By then it has already lost its first \(d\) entries, so its remaining product is
$$\prod_{k=d+1}^{K} a_k(m-1-d),$$
where \(K\) is the largest row that is ever nontrivial in the stabilized regime. The pile exists only if it originally had at least \(d+1\) entries, which is equivalent to
$$a_{d+1}(m-1-d)\ne 1.$$
Therefore the total sum is a sum of diagonal suffix-products through the row table:
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(a_{d+1}(m-1-d)\ne 1\bigr)\prod_{k=d+1}^{K} a_k(m-1-d)\pmod{1234567891}.$$
This is the decisive transformation: instead of advancing one round at a time, we can jump directly to the large target round by evaluating finitely many periodic rows.
After the transient, only residue classes inside each row period matter. If \(r_0=m-t_0-1\), then the large-round formula becomes
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(p_{d+1}((r_0-d)\bmod(d+1))\ne 1\bigr)\prod_{k=d+1}^{K} p_k((r_0-d)\bmod k)\pmod{1234567891}.$$
All dependence on the enormous value of \(m\) is now reduced to modular indexing inside short stored cycles.
Start from the four piles coming from \(2,3,4,5\):
$$[2],\ [3],\ [2,2],\ [5].$$
Round 1 extracts \([2,3,2,5]\), which sorts to \([2,2,3,5]\). The piles after the round are \([2]\) and \([2,2,3,5]\), so the sum of residual products is
$$2+(2\cdot 2\cdot 3\cdot 5)=62.$$
Round 2 extracts \([2,2]\). The piles become \([2,3,5]\) and \([2,2]\), giving
$$2\cdot 3\cdot 5+2\cdot 2=30+4=34.$$
Round 3 again extracts \([2,2]\). The remaining piles are \([3,5]\), \([2]\), and \([2,2]\), so
$$S(5,3)=3\cdot 5+2+2\cdot 2=15+2+4=21.$$
This is the first small checkpoint used by the implementations.
The C++, Python, and Java implementations first build a smallest-prime-factor sieve up to \(n\), then factor every integer \(2,3,\dots,n\) into an ascending prime list. That produces the initial piles efficiently.
They then simulate the shuffle while monitoring the \(k\)-th extracted value of each round. For every row \(k\), the implementation stores the last \(k\) observed values and checks whether the current value matches the one from \(k\) rounds earlier; missing entries are treated as \(1\). Once all monitored rows have repeated long enough, the row cycles are recorded.
If the requested round still lies inside the transient, the answer is obtained by direct simulation. Otherwise the implementation evaluates the diagonal formula above, using only modular indexing into the stored cycles. Small checkpoints such as \(S(5,3)=21\) and \(S(10,100)=257\) verify the logic before the final target value is produced.
Let \(T=\sum_{j=2}^{n}\Omega(j)\), and let \(K\) be the highest periodic row that contains a value other than \(1\). Building the smallest-prime-factor sieve takes \(O(n\log\log n)\) time and \(O(n)\) memory, while constructing the initial piles takes \(O(T)\) total factor extractions. If periodicity is detected after \(R\) simulated rounds and \(k_t\) piles are active at round \(t\), the transient costs \(O\!\left(\sum_{t=1}^{R} k_t\log k_t\right)\) because each round sorts the extracted factors. After that, a huge-round query is answered in \(O(K^2)\) time using the diagonal product formula, with \(O(K^2)\) memory for the stored cycles.
Für jede ganze Zahl \(j\in\{2,\dots,n\}\) schreibt man ihre Primfaktoren in nichtabsteigender Reihenfolge auf und behandelt diese geordnete Liste als einen Stapel. In jeder Runde wird aus jedem nichtleeren Stapel der erste Faktor entfernt, alle entnommenen Faktoren werden sortiert und als neuer Stapel angehängt. Nach \(m\) Runden ist \(S(n,m)\) die Summe der Produkte aller noch in den aktiven Stapeln verbleibenden Faktoren modulo \(1234567891\). Die Schwierigkeit ist die Zielrundenzahl \(10^{16}\), daher muss die Lösung die lange Simulation durch eine Strukturformel für das stabilisierte Mischen ersetzen.
Die Implementierungen arbeiten direkt mit Primfaktorlisten. Entscheidend ist, zwei Ebenen des Prozesses zu trennen: die Entwicklung der Stapellängen und die Entwicklung der in jeder Runde entnommenen, sortierten Faktoren.
Der Anfangsstapel zu \(j\) ist die aufsteigende Primfaktorliste von \(j\). Bezeichnet \(\Omega(j)\) die Anzahl der Primfaktoren von \(j\) mit Vielfachheit, dann ist die Gesamtzahl aller gespeicherten Faktoren
$$T=\sum_{j=2}^{n}\Omega(j).$$
Diese Größe ändert sich nie. In jeder Runde entfernt man genau einen Faktor aus jedem aktiven Stapel und erzeugt anschließend genau einen neuen Stapel, dessen Länge der Zahl der aktiven Stapel in dieser Runde entspricht. Damit ändert sich nur die Verteilung der Längen, nicht aber die Gesamtzahl der Faktoren.
Sind die aktuellen Stapellängen \(\lambda_1,\dots,\lambda_k\), dann werden sie in der nächsten Runde zu den positiven Teilen von
$$(\lambda_1-1,\dots,\lambda_k-1,k).$$
Das ist genau dieselbe Längenregel wie bei Bulgarian Solitaire. Dadurch wird verständlich, warum nur etwa \(\sqrt{T}\) Stapelpositionen relevant bleiben: Nach einer Übergangsphase liegen die Längen nahe an einer Treppenform, statt über alle \(T\) Faktoren verteilt zu bleiben.
Seien in Runde \(t\) die nach dem Sortieren entnommenen Faktoren
$$E_t=\bigl(a_1(t),a_2(t),\dots,a_{k_t}(t)\bigr),\qquad a_1(t)\le a_2(t)\le \dots \le a_{k_t}(t),$$
wobei \(k_t\) die Zahl der aktiven Stapel in dieser Runde ist. Zur einheitlichen Notation setzt man außerdem
$$a_k(t)=1,\quad k>k_t.$$
Diese Auffüllung ist unschädlich, weil ein Faktor \(1\) kein Produkt verändert.
Der in Runde \(t\) neu erzeugte Stapel ist genau die Liste \(E_t\). Eine Runde später wird sein erster Eintrag \(a_1(t)\) entfernt, zwei Runden später sein zweiter Eintrag \(a_2(t)\); allgemein wird der \(k\)-te Eintrag genau \(k\) Runden nach der Entstehung dieses Stapels entnommen.
Sobald sich die Längendynamik eingependelt hat, wird der Mischprozess schiebungsinvariant: Dieselbe geometrische Position innerhalb eines Stapels taucht nach einer festen Anzahl von Runden wieder auf. Weil der \(k\)-te Eintrag eines neu entstandenen Stapels genau \(k\) Runden überlebt, wiederholt sich die \(k\)-te Entnahmereihe natürlich mit Periode \(k\).
Nach einer Übergangszeit \(t_0\) verwenden die Implementierungen daher die periodische Beschreibung
$$a_k(t+k)=a_k(t)\qquad (t\ge t_0),$$
oder äquivalent
$$a_k(t)=p_k(t\bmod k),$$
wobei \(p_k\) der gespeicherte Zyklus der \(k\)-ten Reihe ist. Der Code nimmt diese Zyklen nicht im Voraus an, sondern simuliert so lange, bis sich die letzten \(k\) Werte der \(k\)-ten Reihe konsistent wiederholen.
Betrachte den Zustand nach Runde \(m\). Ein Stapel, der \(d\) Runden früher erzeugt wurde, entstand in Runde \(m-1-d\). Zu diesem Zeitpunkt hat er bereits seine ersten \(d\) Einträge verloren. Sein verbleibendes Produkt ist also
$$\prod_{k=d+1}^{K} a_k(m-1-d),$$
wobei \(K\) die größte Reihe ist, die im stabilisierten Bereich jemals von \(1\) verschiedene Werte enthält. Der Stapel existiert genau dann noch, wenn er ursprünglich mindestens \(d+1\) Einträge hatte, also genau dann, wenn
$$a_{d+1}(m-1-d)\ne 1.$$
Damit wird die gesuchte Summe zu einer Summe diagonaler Suffix-Produkte durch die Reihentabelle:
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(a_{d+1}(m-1-d)\ne 1\bigr)\prod_{k=d+1}^{K} a_k(m-1-d)\pmod{1234567891}.$$
Das ist die entscheidende Umformung: Statt Runde für Runde weiterzurechnen, springt man direkt zur großen Zielrunde und wertet nur endlich viele periodische Reihen aus.
Nach der Übergangsphase spielen nur noch Restklassen innerhalb jeder Zeilenperiode eine Rolle. Mit \(r_0=m-t_0-1\) wird die Formel für große Runden zu
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(p_{d+1}((r_0-d)\bmod(d+1))\ne 1\bigr)\prod_{k=d+1}^{K} p_k((r_0-d)\bmod k)\pmod{1234567891}.$$
Die Abhängigkeit von der riesigen Zahl \(m\) wird damit vollständig auf modulare Indizes in kurzen gespeicherten Zyklen reduziert.
Man startet mit den vier Stapeln zu \(2,3,4,5\):
$$[2],\ [3],\ [2,2],\ [5].$$
In Runde 1 werden \([2,3,2,5]\) entnommen und zu \([2,2,3,5]\) sortiert. Danach bleiben die Stapel \([2]\) und \([2,2,3,5]\), also ist die Summe der Restprodukte
$$2+(2\cdot 2\cdot 3\cdot 5)=62.$$
In Runde 2 wird \([2,2]\) entnommen. Die Stapel sind nun \([2,3,5]\) und \([2,2]\), also
$$2\cdot 3\cdot 5+2\cdot 2=30+4=34.$$
In Runde 3 wird erneut \([2,2]\) entnommen. Übrig bleiben \([3,5]\), \([2]\) und \([2,2]\), daher
$$S(5,3)=3\cdot 5+2+2\cdot 2=15+2+4=21.$$
Genau dieser kleine Kontrollwert wird von den Implementierungen verwendet.
Die C++-, Python- und Java-Implementierungen bauen zuerst ein Sieb der kleinsten Primfaktoren bis \(n\) auf und zerlegen dann jede Zahl \(2,3,\dots,n\) in eine aufsteigende Primfaktorliste. So entstehen die Anfangsstapel effizient.
Anschließend simulieren sie den Mischprozess und überwachen dabei den \(k\)-ten entnommenen Wert jeder Runde. Für jede Reihe \(k\) speichert die Implementierung die letzten \(k\) beobachteten Werte und prüft, ob der aktuelle Wert mit dem Wert von vor \(k\) Runden übereinstimmt; fehlende Einträge werden als \(1\) behandelt. Sobald sich alle beobachteten Reihen lange genug wiederholt haben, werden ihre Zyklen gespeichert.
Liegt die gewünschte Runde noch in der Übergangsphase, wird direkt simuliert. Andernfalls wertet die Implementierung die obige Diagonalformel aus und benutzt nur modulare Indizierung in den gespeicherten Zyklen. Kleine Kontrollwerte wie \(S(5,3)=21\) und \(S(10,100)=257\) bestätigen vorher die Logik.
Sei \(T=\sum_{j=2}^{n}\Omega(j)\), und sei \(K\) die höchste periodische Reihe mit einem von \(1\) verschiedenen Wert. Das Sieb der kleinsten Primfaktoren benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher; der Aufbau der Anfangsstapel kostet insgesamt \(O(T)\) Faktorextraktionen. Wird die Periodizität nach \(R\) simulierten Runden erkannt und sind in Runde \(t\) jeweils \(k_t\) Stapel aktiv, dann kostet die Übergangsphase \(O\!\left(\sum_{t=1}^{R} k_t\log k_t\right)\), weil in jeder Runde die entnommenen Faktoren sortiert werden. Danach beantwortet die Diagonalformel eine sehr große Runde in \(O(K^2)\) Zeit bei \(O(K^2)\) Zusatzspeicher für die gespeicherten Zyklen.
Her \(j\in\{2,\dots,n\}\) tam sayısı için asal çarpanlar küçükten büyüğe yazılır ve bu sıralı liste bir yığın kabul edilir. Her turda boş olmayan her yığından ilk çarpan alınır, alınan çarpanlar sıralanır ve yeni bir yığın olarak sona eklenir. \(m\) tur sonunda \(S(n,m)\), aktif yığınlarda kalan çarpanların çarpımlarının toplamıdır ve sonuç \(1234567891\) modunda istenir. Asıl zorluk, hedef tur sayısının \(10^{16}\) olmasıdır; bu yüzden çözüm uzun simülasyonu, kararlı fazın matematiksel yapısıyla değiştirmek zorundadır.
İmplementasyonlar doğrudan asal çarpan listeleriyle çalışır. Ana fikir, süreci iki katmanda incelemektir: yığın uzunluklarının evrimi ve her turda çekilen sıralı asal çarpanların evrimi.
\(j\) sayısının başlangıç yığını, \(j\)'nin artan asal çarpan listesidir. \(\Omega(j)\), \(j\)'nin katlarıyla birlikte toplam asal çarpan sayısı olsun. O zaman sistemdeki toplam çarpan sayısı
$$T=\sum_{j=2}^{n}\Omega(j).$$
Bu değer hiç değişmez. Her turda her aktif yığından tam bir çarpan çıkarılır; sonra uzunluğu o turdaki aktif yığın sayısına eşit olan tek bir yeni yığın oluşturulur. Dolayısıyla değişen şey toplam çarpan sayısı değil, yalnızca uzunlukların dağılımıdır.
O andaki yığın uzunlukları \(\lambda_1,\dots,\lambda_k\) ise bir sonraki turda uzunluklar
$$(\lambda_1-1,\dots,\lambda_k-1,k)$$
çoklu kümesindeki pozitif terimlere dönüşür. Bu, Bulgarian solitaire olarak bilinen bölüşüm dinamiğinin aynısıdır. Böylece neden yalnızca yaklaşık \(\sqrt{T}\) kadar konumun önemli kaldığı anlaşılır: geçiş fazından sonra uzunluklar tüm \(T\) çarpana dağılmak yerine merdiven benzeri bir şekil etrafında toplanır.
\(t\) turunda, sıralama sonrası çekilen çarpanlar
$$E_t=\bigl(a_1(t),a_2(t),\dots,a_{k_t}(t)\bigr),\qquad a_1(t)\le a_2(t)\le \dots \le a_{k_t}(t),$$
şeklinde olsun; burada \(k_t\), o turdaki aktif yığın sayısıdır. Notasyonu tek biçimde tutmak için ayrıca
$$a_k(t)=1,\quad k>k_t.$$
tanımı yapılır. Bu doldurma güvenlidir; çünkü \(1\) ile çarpmak yığın çarpımını değiştirmez.
\(t\) turunda oluşturulan yeni yığın tam olarak \(E_t\) listesidir. Bir tur sonra ilk eleman \(a_1(t)\), iki tur sonra ikinci eleman \(a_2(t)\) çıkarılır; genel olarak bu yeni yığının \(k\). elemanı tam \(k\) tur sonra çekilir.
Uzunluk dinamiği dengelendikten sonra karıştırma işlemi kaydırma altında değişmez hale gelir: bir yığın içindeki aynı geometrik konum, sabit sayıda tur sonra yeniden ziyaret edilir. Yeni doğmuş bir yığının \(k\). elemanı tam \(k\) tur yaşadığı için, \(k\). çekim satırı doğal olarak \(k\) periyotlu hale gelir.
Bu nedenle geçici fazın sonundan itibaren, implementasyonlar
$$a_k(t+k)=a_k(t)\qquad (t\ge t_0)$$
veya eşdeğer olarak
$$a_k(t)=p_k(t\bmod k)$$
biçimindeki gösterimi kullanır. Burada \(p_k\), \(k\). satır için saklanan çevrimdir. Kod bu çevrimleri peşinen varsaymaz; \(k\). satırın son \(k\) değeri yeterince uzun süre tekrar ettiğinde o satırı periyodik kabul eder.
\(m\) turu sonrasındaki durumu düşünelim. \(d\) tur önce doğmuş bir yığın, \(m-1-d\) turunda oluşturulmuştur. Bu sırada ilk \(d\) elemanı zaten çıkarılmış olacağından geriye kalan çarpımı
$$\prod_{k=d+1}^{K} a_k(m-1-d)$$
olur; burada \(K\), kararlı fazda \(1\) dışında değer üreten en büyük satır indeksidir. Bu yığının gerçekten var olması için başlangıçta en az \(d+1\) elemanlı olması gerekir; bu da
$$a_{d+1}(m-1-d)\ne 1$$
koşuluna denktir. Böylece toplam, satır tablosu üzerindeki çapraz kuyruk-çarpımlarının toplamına dönüşür:
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(a_{d+1}(m-1-d)\ne 1\bigr)\prod_{k=d+1}^{K} a_k(m-1-d)\pmod{1234567891}.$$
Kritik dönüşüm budur: her turu tek tek ilerletmek yerine, son derece büyük hedef tur birkaç periyodik satır üzerinden doğrudan hesaplanır.
Geçici fazdan sonra her satır için yalnızca periyot içindeki kalan sınıf önemlidir. \(r_0=m-t_0-1\) dersek büyük tur formülü
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(p_{d+1}((r_0-d)\bmod(d+1))\ne 1\bigr)\prod_{k=d+1}^{K} p_k((r_0-d)\bmod k)\pmod{1234567891}$$
haline gelir. Böylece devasa \(m\) değeri, kısa saklanmış çevrimlerdeki modüler indekslemeye indirgenmiş olur.
Başlangıçta \(2,3,4,5\) sayılarından gelen dört yığın vardır:
$$[2],\ [3],\ [2,2],\ [5].$$
1. turda \([2,3,2,5]\) çekilir ve \([2,2,3,5]\) olarak sıralanır. Tur sonunda yığınlar \([2]\) ve \([2,2,3,5]\) olur; dolayısıyla kalan çarpımlar toplamı
$$2+(2\cdot 2\cdot 3\cdot 5)=62$$
çıkar.
2. turda \([2,2]\) çekilir. Yığınlar \([2,3,5]\) ve \([2,2]\) olur; bu da
$$2\cdot 3\cdot 5+2\cdot 2=30+4=34$$
verir.
3. turda yine \([2,2]\) çekilir. Geriye \([3,5]\), \([2]\) ve \([2,2]\) kalır. O halde
$$S(5,3)=3\cdot 5+2+2\cdot 2=15+2+4=21.$$
İmplementasyonların kullandığı ilk küçük doğrulama değeri budur.
C++, Python ve Java implementasyonları önce \(n\)'e kadar en küçük asal bölen süzgeci kurar, sonra \(2,3,\dots,n\) sayılarının her birini artan asal çarpan listesine ayırır. Böylece başlangıç yığınları verimli biçimde elde edilir.
Daha sonra karıştırma süreci simüle edilirken her turdaki \(k\). çekilen değer izlenir. Her satır \(k\) için implementasyon son \(k\) gözlemi saklar ve mevcut değerin \(k\) tur önceki değerle aynı olup olmadığını denetler; eksik satırlar \(1\) ile doldurulur. Tüm izlenen satırlar yeterince uzun süre tekrar ettiğinde çevrimler kaydedilir.
İstenen tur hâlâ geçici faz içindeyse cevap doğrudan simülasyonla bulunur. Aksi halde implementasyon yukarıdaki çapraz formülü kullanır ve sadece saklanan çevrimlerde modüler indeksleme yapar. \(S(5,3)=21\) ve \(S(10,100)=257\) gibi küçük kontrol değerleri, son hedef hesaplanmadan önce mantığı doğrular.
\(T=\sum_{j=2}^{n}\Omega(j)\) ve \(K\), \(1\)'den farklı değer içeren en yüksek periyodik satır olsun. En küçük asal bölen süzgeci \(O(n\log\log n)\) zaman ve \(O(n)\) bellek gerektirir; başlangıç yığınlarını kurmak toplam \(O(T)\) faktör çıkarımı maliyetine sahiptir. Periyodiklik \(R\) simüle edilmiş tur sonra bulunuyor ve \(t\) turunda \(k_t\) aktif yığın varsa, geçiş fazının maliyeti her tur çekilen değerler sıralandığı için \(O\!\left(\sum_{t=1}^{R} k_t\log k_t\right)\) olur. Bundan sonra çok büyük bir tur, çapraz çarpım formülü sayesinde \(O(K^2)\) zamanda ve saklanan çevrimler için \(O(K^2)\) ek bellekle cevaplanır.
Para cada entero \(j\in\{2,\dots,n\}\), se escriben sus factores primos en orden no decreciente y esa lista ordenada se toma como una pila. En cada ronda se elimina el primer factor de cada pila no vacía, se ordenan los factores extraídos y se añaden como una pila nueva. Tras \(m\) rondas, \(S(n,m)\) es la suma de los productos de los factores que aún quedan en las pilas activas, todo módulo \(1234567891\). La dificultad real es que el número objetivo de rondas es \(10^{16}\), así que la solución necesita reemplazar una simulación larguísima por una descripción estructural del régimen estabilizado.
Las implementaciones trabajan directamente con listas de factores primos. La idea clave es separar dos capas del proceso: la evolución de las longitudes de las pilas y la evolución de los factores ordenados que se extraen en cada ronda.
La pila inicial de \(j\) es la lista ascendente de factores primos de \(j\). Si \(\Omega(j)\) denota el número total de factores primos de \(j\), contando multiplicidades, entonces el número total de factores almacenados es
$$T=\sum_{j=2}^{n}\Omega(j).$$
Esta cantidad nunca cambia. En cada ronda se extrae exactamente un factor de cada pila activa y después se crea una sola pila nueva cuya longitud es el número de pilas activas en esa ronda. Por tanto, lo único que cambia es la distribución de longitudes, no la cantidad total de factores.
Si las longitudes actuales son \(\lambda_1,\dots,\lambda_k\), la siguiente ronda las transforma en las partes positivas de
$$(\lambda_1-1,\dots,\lambda_k-1,k).$$
Esta es exactamente la misma dinámica de longitudes que aparece en Bulgarian solitaire. Eso explica por qué solo importan unas \(O(\sqrt{T})\) posiciones: después de la fase transitoria, las longitudes se concentran alrededor de una forma escalonada en vez de seguir dispersas por los \(T\) factores.
En la ronda \(t\), sean los factores extraídos tras ordenar
$$E_t=\bigl(a_1(t),a_2(t),\dots,a_{k_t}(t)\bigr),\qquad a_1(t)\le a_2(t)\le \dots \le a_{k_t}(t),$$
donde \(k_t\) es el número de pilas activas en esa ronda. Para uniformar la notación, se prolonga la definición mediante
$$a_k(t)=1,\quad k>k_t.$$
Este relleno es inocuo porque multiplicar por \(1\) no altera el producto de una pila.
La pila nueva creada en la ronda \(t\) es exactamente la lista \(E_t\). Una ronda más tarde se elimina su primer elemento \(a_1(t)\), dos rondas más tarde su segundo elemento \(a_2(t)\); en general, el \(k\)-ésimo elemento se extrae exactamente \(k\) rondas después del nacimiento de esa pila.
Una vez que la dinámica de longitudes se estabiliza, la mezcla se vuelve invariante por traslación: la misma posición geométrica dentro de una pila reaparece tras un número fijo de rondas. Como el \(k\)-ésimo elemento de una pila recién creada sobrevive exactamente \(k\) rondas, la \(k\)-ésima fila extraída pasa a tener de forma natural periodo \(k\).
Así, después de un tiempo transitorio \(t_0\), las implementaciones usan la descripción periódica
$$a_k(t+k)=a_k(t)\qquad (t\ge t_0),$$
o de manera equivalente
$$a_k(t)=p_k(t\bmod k),$$
donde \(p_k\) es el ciclo almacenado de la fila \(k\). El código no supone estos ciclos de antemano; simula hasta que los últimos \(k\) valores de la fila \(k\) se repiten de forma consistente y entonces registra esa periodicidad.
Consideremos el estado después de la ronda \(m\). Una pila creada \(d\) rondas antes nació en la ronda \(m-1-d\). Para entonces ya perdió sus primeros \(d\) elementos, de modo que su producto restante es
$$\prod_{k=d+1}^{K} a_k(m-1-d),$$
donde \(K\) es la fila más alta que sigue siendo no trivial en el régimen estabilizado. La pila existe solo si originalmente tenía al menos \(d+1\) elementos, es decir, solo si
$$a_{d+1}(m-1-d)\ne 1.$$
Por tanto, la suma buscada se convierte en una suma de productos de sufijos a lo largo de diagonales de la tabla de filas:
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(a_{d+1}(m-1-d)\ne 1\bigr)\prod_{k=d+1}^{K} a_k(m-1-d)\pmod{1234567891}.$$
Esta es la transformación decisiva: en vez de avanzar ronda por ronda, se salta directamente a la ronda enorme evaluando solo un número finito de filas periódicas.
Después del transitorio, solo importan las clases residuales dentro del periodo de cada fila. Si \(r_0=m-t_0-1\), la fórmula para una ronda enorme queda
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(p_{d+1}((r_0-d)\bmod(d+1))\ne 1\bigr)\prod_{k=d+1}^{K} p_k((r_0-d)\bmod k)\pmod{1234567891}.$$
Toda la dependencia de la inmensa cantidad \(m\) queda reducida a indexación modular dentro de ciclos cortos ya almacenados.
Se empieza con las cuatro pilas provenientes de \(2,3,4,5\):
$$[2],\ [3],\ [2,2],\ [5].$$
En la ronda 1 se extrae \([2,3,2,5]\), que ordenado da \([2,2,3,5]\). Las pilas pasan a ser \([2]\) y \([2,2,3,5]\), así que la suma de productos residuales es
$$2+(2\cdot 2\cdot 3\cdot 5)=62.$$
En la ronda 2 se extrae \([2,2]\). Las pilas se convierten en \([2,3,5]\) y \([2,2]\), dando
$$2\cdot 3\cdot 5+2\cdot 2=30+4=34.$$
En la ronda 3 vuelve a extraerse \([2,2]\). Quedan \([3,5]\), \([2]\) y \([2,2]\), por lo que
$$S(5,3)=3\cdot 5+2+2\cdot 2=15+2+4=21.$$
Ese es el primer punto de control pequeño usado por las implementaciones.
Las implementaciones en C++, Python y Java construyen primero una criba del menor factor primo hasta \(n\) y luego descomponen cada entero \(2,3,\dots,n\) en una lista ascendente de factores primos. Así obtienen de forma eficiente las pilas iniciales.
Después simulan la mezcla mientras vigilan el \(k\)-ésimo valor extraído en cada ronda. Para cada fila \(k\), la implementación guarda los últimos \(k\) valores observados y comprueba si el valor actual coincide con el de hace \(k\) rondas; las entradas faltantes se tratan como \(1\). Cuando todas las filas vigiladas se han repetido durante suficiente tiempo, se guardan sus ciclos.
Si la ronda pedida aún cae dentro del transitorio, la respuesta se obtiene por simulación directa. En caso contrario, la implementación evalúa la fórmula diagonal anterior usando solo indexación modular sobre los ciclos almacenados. Comprobaciones pequeñas como \(S(5,3)=21\) y \(S(10,100)=257\) validan la lógica antes del cálculo final.
Sea \(T=\sum_{j=2}^{n}\Omega(j)\), y sea \(K\) la fila periódica más alta que contiene un valor distinto de \(1\). Construir la criba del menor factor primo cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria, mientras que formar las pilas iniciales cuesta \(O(T)\) extracciones de factores en total. Si la periodicidad se detecta tras \(R\) rondas simuladas y hay \(k_t\) pilas activas en la ronda \(t\), la fase transitoria cuesta \(O\!\left(\sum_{t=1}^{R} k_t\log k_t\right)\) porque en cada ronda se ordenan los factores extraídos. Después, una consulta con una ronda gigantesca se responde en \(O(K^2)\) tiempo mediante la fórmula diagonal, con \(O(K^2)\) memoria para los ciclos almacenados.
对每个 \(j\in\{2,\dots,n\}\)，把它的素因子按不降序写成一个有序列表，并把这个列表视为一堆。每一轮都从每个非空堆中取走第一个因子，把所有取出的因子整体排序，再把排好序的结果作为一堆新堆追加到末尾。经过 \(m\) 轮之后，\(S(n,m)\) 定义为所有活动堆中剩余因子的乘积之和，并对 \(1234567891\) 取模。真正的难点在于目标轮数是 \(10^{16}\)，因此解法不能靠暴力推进，而必须抓住洗牌过程在稳定阶段的结构。
实现直接在素因子列表上工作。关键是把整个过程拆成两个层面：一是堆长度如何变化，二是每一轮取出的有序素因子如何变化。
\(j\) 的初始堆就是 \(j\) 的升序素因子列表。若 \(\Omega(j)\) 表示 \(j\) 的素因子总个数（按重数计算），那么系统中保存的因子总数为
$$T=\sum_{j=2}^{n}\Omega(j).$$
这个量始终不变。每一轮都会从每个活动堆中恰好拿走一个因子，然后新建一堆，其长度正好等于该轮活动堆的数量。因此变化的只是长度分布，而不是总因子数。
若当前各堆长度为 \(\lambda_1,\dots,\lambda_k\)，则下一轮的长度集合就是
$$(\lambda_1-1,\dots,\lambda_k-1,k)$$
中所有正数项组成的多重集合。这与 Bulgarian solitaire 的长度更新规则完全一致。也正因为如此，真正需要关注的位置只有大约 \(\sqrt{T}\) 个：过渡阶段之后，堆长度会围绕“阶梯形”分布，而不会继续在全部 \(T\) 个因子上发散。
设第 \(t\) 轮排序后的抽取结果为
$$E_t=\bigl(a_1(t),a_2(t),\dots,a_{k_t}(t)\bigr),\qquad a_1(t)\le a_2(t)\le \dots \le a_{k_t}(t),$$
其中 \(k_t\) 是该轮活动堆的数量。为了统一写法，再规定
$$a_k(t)=1,\quad k>k_t.$$
这种补 \(1\) 的做法不会影响结果，因为乘积里乘上 \(1\) 没有任何变化。
第 \(t\) 轮新生成的那一堆，恰好就是列表 \(E_t\)。一轮之后，它的第一个元素 \(a_1(t)\) 会被取走；两轮之后，第二个元素 \(a_2(t)\) 会被取走；一般地，这个新堆的第 \(k\) 个元素会在它出生后的第 \(k\) 轮被抽走。
一旦长度动力学稳定下来，整个洗牌过程就具有“平移不变”的味道：堆中同一种几何位置，会在固定轮数之后再次出现。由于一个新堆的第 \(k\) 个元素恰好会存活 \(k\) 轮，所以第 \(k\) 行抽取值自然会形成周期为 \(k\) 的循环。
因此在某个过渡时间 \(t_0\) 之后，实现采用下面的周期描述：
$$a_k(t+k)=a_k(t)\qquad (t\ge t_0),$$
也可以等价地写成
$$a_k(t)=p_k(t\bmod k),$$
其中 \(p_k\) 是第 \(k\) 行保存下来的循环。程序并不是预先假设这些周期，而是持续模拟，直到第 \(k\) 行最近的 \(k\) 个值能够稳定重复，才把该行记录为周期行。
现在看第 \(m\) 轮之后的状态。一个在 \(d\) 轮之前生成的堆，出生于第 \(m-1-d\) 轮。到第 \(m\) 轮为止，它的前 \(d\) 个元素已经被取走，因此该堆剩余部分的乘积为
$$\prod_{k=d+1}^{K} a_k(m-1-d),$$
其中 \(K\) 表示稳定阶段中最后一个仍然可能不是 \(1\) 的行号。这个堆存在的前提是它最初至少有 \(d+1\) 个元素，也就是
$$a_{d+1}(m-1-d)\ne 1.$$
于是，总和就变成了行表中的“对角线后缀乘积”之和：
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(a_{d+1}(m-1-d)\ne 1\bigr)\prod_{k=d+1}^{K} a_k(m-1-d)\pmod{1234567891}.$$
这一步是整个解法的核心。它把“逐轮推进”变成了“直接读取有限条周期行”，从而可以直接跳到极大的目标轮数。
过渡阶段之后，每一行真正重要的只是它在本行周期中的余数位置。令 \(r_0=m-t_0-1\)，则大轮数公式可以写成
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(p_{d+1}((r_0-d)\bmod(d+1))\ne 1\bigr)\prod_{k=d+1}^{K} p_k((r_0-d)\bmod k)\pmod{1234567891}.$$
这样一来，对巨大 \(m\) 的依赖完全被压缩成若干个短周期中的模索引访问。
先从 \(2,3,4,5\) 对应的四个初始堆开始：
$$[2],\ [3],\ [2,2],\ [5].$$
第 1 轮抽出 \([2,3,2,5]\)，排序后得到 \([2,2,3,5]\)。这一轮之后的堆为 \([2]\) 和 \([2,2,3,5]\)，所以剩余乘积和是
$$2+(2\cdot 2\cdot 3\cdot 5)=62.$$
第 2 轮抽出 \([2,2]\)。此时堆变成 \([2,3,5]\) 与 \([2,2]\)，于是
$$2\cdot 3\cdot 5+2\cdot 2=30+4=34.$$
第 3 轮再次抽出 \([2,2]\)。剩下的堆是 \([3,5]\)、\([2]\) 和 \([2,2]\)，因此
$$S(5,3)=3\cdot 5+2+2\cdot 2=15+2+4=21.$$
这正是实现中使用的第一个小型校验值。
C++、Python 和 Java 实现首先构造到 \(n\) 为止的最小素因子表，然后把每个整数 \(2,3,\dots,n\) 分解成升序素因子列表，从而高效得到初始堆。
接着程序一边模拟洗牌，一边监控每一轮的第 \(k\) 个抽取值。对于每个行号 \(k\)，实现都会保存最近的 \(k\) 个观测值，并检查当前值是否等于 \(k\) 轮之前的值；如果某一轮没有这么高的行，就用 \(1\) 填充。当所有被监控的行都重复足够久之后，这些行的周期就被记录下来。
如果所求轮数仍处在过渡阶段，答案直接由模拟得到；否则实现使用上面的对角线公式，只通过对保存周期做模索引来求值。在真正计算目标值之前，还会先验证 \(S(5,3)=21\) 和 \(S(10,100)=257\) 这样的较小检查点。
设 \(T=\sum_{j=2}^{n}\Omega(j)\)，\(K\) 是最后一个会出现非 \(1\) 值的周期行。构造最小素因子表需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 内存，建立初始堆总共需要 \(O(T)\) 次因子提取。若在 \(R\) 轮模拟之后检测到周期性，第 \(t\) 轮有 \(k_t\) 个活动堆，那么过渡阶段的代价是 \(O\!\left(\sum_{t=1}^{R} k_t\log k_t\right)\)，因为每一轮都要对抽取出的因子排序。进入周期阶段后，一次超大轮数查询只需 \(O(K^2)\) 时间来计算对角线乘积，并用 \(O(K^2)\) 额外内存保存周期行。
Для каждого числа \(j\in\{2,\dots,n\}\) выписываются его простые множители в неубывающем порядке, и этот упорядоченный список рассматривается как одна куча. На каждом ходе из каждой непустой кучи удаляется первый множитель, все извлечённые множители сортируются и добавляются как новая куча. После \(m\) ходов величина \(S(n,m)\) равна сумме произведений множителей, оставшихся в активных кучах, по модулю \(1234567891\). Главная трудность в том, что целевое число ходов равно \(10^{16}\), поэтому длинную симуляцию нужно заменить структурным описанием установившегося режима.
Реализации работают непосредственно со списками простых множителей. Ключевой шаг состоит в разделении процесса на два уровня: как меняются длины куч и как меняются отсортированные множители, извлекаемые на каждом ходе.
Начальная куча для числа \(j\) — это возрастающий список его простых множителей. Пусть \(\Omega(j)\) обозначает число простых множителей \(j\) с учётом кратности. Тогда общее число сохранённых множителей равно
$$T=\sum_{j=2}^{n}\Omega(j).$$
Эта величина никогда не меняется. На каждом ходе мы убираем ровно по одному множителю из каждой активной кучи, а затем создаём новую кучу длины, равной числу активных куч на этом ходе. Значит, меняется только распределение длин, но не общее число множителей.
Если текущие длины куч равны \(\lambda_1,\dots,\lambda_k\), то на следующем ходе они переходят в положительные части набора
$$(\lambda_1-1,\dots,\lambda_k-1,k).$$
Это ровно то же правило длин, которое возникает в Bulgarian solitaire. Отсюда понятно, почему существенных позиций остаётся лишь порядка \(\sqrt{T}\): после переходного этапа длины собираются около «лестничной» формы, а не размазываются по всем \(T\) множителям.
Пусть на ходе \(t\) после сортировки извлечённые множители равны
$$E_t=\bigl(a_1(t),a_2(t),\dots,a_{k_t}(t)\bigr),\qquad a_1(t)\le a_2(t)\le \dots \le a_{k_t}(t),$$
где \(k_t\) — число активных куч на этом ходе. Для удобства также договоримся, что
$$a_k(t)=1,\quad k>k_t.$$
Такое дополнение безвредно, потому что умножение на \(1\) не меняет произведение кучи.
Новая куча, созданная на ходе \(t\), в точности равна списку \(E_t\). Через один ход из неё исчезает первый элемент \(a_1(t)\), через два хода — второй элемент \(a_2(t)\); вообще говоря, \(k\)-й элемент извлекается ровно через \(k\) ходов после рождения этой кучи.
Когда динамика длин стабилизируется, перемешивание становится инвариантным относительно сдвига: одна и та же геометрическая позиция внутри кучи появляется снова через фиксированное число ходов. Поскольку \(k\)-й элемент новой кучи живёт ровно \(k\) ходов, \(k\)-я строка извлечений естественным образом приобретает период \(k\).
Поэтому после некоторого переходного момента \(t_0\) реализации используют периодическое описание
$$a_k(t+k)=a_k(t)\qquad (t\ge t_0),$$
или эквивалентно
$$a_k(t)=p_k(t\bmod k),$$
где \(p_k\) — сохранённый цикл для строки \(k\). Код не предполагает эти циклы заранее: он продолжает симуляцию, пока последние \(k\) значений \(k\)-й строки не начнут надёжно повторяться.
Рассмотрим состояние после хода \(m\). Куча, созданная \(d\) ходов назад, родилась на ходе \(m-1-d\). К этому моменту у неё уже удалены первые \(d\) элементов, поэтому произведение оставшегося хвоста равно
$$\prod_{k=d+1}^{K} a_k(m-1-d),$$
где \(K\) — наибольшая строка, которая в установившемся режиме когда-либо содержит значение, отличное от \(1\). Такая куча вообще существует только тогда, когда изначально имела хотя бы \(d+1\) элементов, то есть тогда и только тогда, когда
$$a_{d+1}(m-1-d)\ne 1.$$
Следовательно, искомая сумма превращается в сумму диагональных произведений хвостов по таблице строк:
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(a_{d+1}(m-1-d)\ne 1\bigr)\prod_{k=d+1}^{K} a_k(m-1-d)\pmod{1234567891}.$$
Это и есть ключевое преобразование: вместо пошагового продвижения по времени достаточно вычислить конечное число периодических строк.
После переходной фазы важны только остатки по модулю периода каждой строки. Если \(r_0=m-t_0-1\), то формула для большого номера хода принимает вид
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(p_{d+1}((r_0-d)\bmod(d+1))\ne 1\bigr)\prod_{k=d+1}^{K} p_k((r_0-d)\bmod k)\pmod{1234567891}.$$
Вся зависимость от огромного \(m\) сводится к модульной адресации внутри коротких сохранённых циклов.
Начинаем с четырёх куч, соответствующих числам \(2,3,4,5\):
$$[2],\ [3],\ [2,2],\ [5].$$
На первом ходе извлекается \([2,3,2,5]\), после сортировки это \([2,2,3,5]\). После хода остаются кучи \([2]\) и \([2,2,3,5]\), поэтому сумма произведений равна
$$2+(2\cdot 2\cdot 3\cdot 5)=62.$$
На втором ходе извлекается \([2,2]\). Кучи становятся \([2,3,5]\) и \([2,2]\), откуда
$$2\cdot 3\cdot 5+2\cdot 2=30+4=34.$$
На третьем ходе снова извлекается \([2,2]\). Остаются \([3,5]\), \([2]\) и \([2,2]\), поэтому
$$S(5,3)=3\cdot 5+2+2\cdot 2=15+2+4=21.$$
Это первый малый контрольный пример, используемый реализациями.
Реализации на C++, Python и Java сначала строят таблицу наименьших простых делителей до \(n\), а затем раскладывают каждое число \(2,3,\dots,n\) в возрастающий список простых множителей. Так начальные кучи строятся эффективно.
После этого программа симулирует перемешивание и одновременно отслеживает \(k\)-е извлечённое значение на каждом ходе. Для каждой строки \(k\) реализация хранит последние \(k\) наблюдений и проверяет, совпадает ли текущее значение со значением \(k\) ходов назад; отсутствующие значения считаются равными \(1\). Когда все отслеживаемые строки достаточно долго повторяются, их циклы сохраняются.
Если нужный ход ещё лежит внутри переходной фазы, ответ берётся из прямой симуляции. Иначе реализация вычисляет приведённую выше диагональную формулу, используя только модульные индексы в сохранённых циклах. Перед финальным вычислением дополнительно проверяются маленькие значения вроде \(S(5,3)=21\) и \(S(10,100)=257\).
Пусть \(T=\sum_{j=2}^{n}\Omega(j)\), а \(K\) — максимальная периодическая строка, содержащая значение, отличное от \(1\). Построение таблицы наименьших простых делителей требует \(O(n\log\log n)\) времени и \(O(n)\) памяти, а формирование начальных куч стоит в сумме \(O(T)\) извлечений факторов. Если периодичность обнаруживается после \(R\) смоделированных ходов и на ходе \(t\) активно \(k_t\) куч, то переходная фаза стоит \(O\!\left(\sum_{t=1}^{R} k_t\log k_t\right)\), потому что на каждом ходе надо сортировать извлечённые множители. После этого запрос для огромного \(m\) обрабатывается за \(O(K^2)\) времени по диагональной формуле и требует \(O(K^2)\) памяти для хранения циклов.
لكل عدد صحيح \(j\in\{2,\dots,n\}\)، نكتب عوامله الأولية بترتيب غير تنازلي ونتعامل مع هذه القائمة المرتبة على أنها كومة واحدة. في كل جولة نزيل العامل الأول من كل كومة غير فارغة، ثم نرتب العوامل المسحوبة ونضيفها ككومة جديدة. بعد \(m\) جولات، تكون \(S(n,m)\) هي مجموع جداءات العوامل الباقية في الأكوام النشطة، وذلك بترديد \(1234567891\). الصعوبة الحقيقية أن عدد الجولات المطلوب هو \(10^{16}\)، ولهذا لا يمكن الاعتماد على المحاكاة الطويلة، بل يجب وصف البنية التي يصل إليها الخلط بعد الاستقرار.
التنفيذات تعمل مباشرة على قوائم العوامل الأولية. والفكرة الأساسية هي فصل العملية إلى مستويين: كيف تتغير أطوال الأكوام، وكيف تتغير العوامل المرتبة التي تُسحب في كل جولة.
الكومة الابتدائية للعدد \(j\) هي القائمة الصاعدة لعوامله الأولية. إذا كانت \(\Omega(j)\) تمثل عدد العوامل الأولية للعدد \(j\) مع احتساب التكرار، فإن العدد الكلي للعوامل المخزنة يساوي
$$T=\sum_{j=2}^{n}\Omega(j).$$
هذه الكمية لا تتغير أبداً. ففي كل جولة نحذف عاملاً واحداً بالضبط من كل كومة نشطة، ثم ننشئ كومة جديدة طولها يساوي عدد الأكوام النشطة في تلك الجولة. لذلك الذي يتغير هو توزيع الأطوال فقط، لا العدد الكلي للعوامل.
إذا كانت أطوال الأكوام الحالية هي \(\lambda_1,\dots,\lambda_k\)، فإن الأطوال في الجولة التالية تصبح الأجزاء الموجبة من
$$(\lambda_1-1,\dots,\lambda_k-1,k).$$
هذه هي قاعدة الأطوال نفسها المعروفة في Bulgarian solitaire. ومن هنا يتضح لماذا يبقى عدد المواضع المهمة في حدود \(\sqrt{T}\): فبعد المرحلة الانتقالية تتجمع الأطوال حول شكل سلّمي بدلاً من التشتت عبر جميع العوامل \(T\).
لنفرض أن العوامل المسحوبة بعد الترتيب في الجولة \(t\) هي
$$E_t=\bigl(a_1(t),a_2(t),\dots,a_{k_t}(t)\bigr),\qquad a_1(t)\le a_2(t)\le \dots \le a_{k_t}(t),$$
حيث \(k_t\) هو عدد الأكوام النشطة في تلك الجولة. ولتوحيد الصياغة نعرّف أيضاً
$$a_k(t)=1,\quad k>k_t.$$
هذا الإكمال غير ضار، لأن الضرب في \(1\) لا يغير جداء أي كومة.
الكومة الجديدة التي تولد في الجولة \(t\) هي بالضبط القائمة \(E_t\). بعد جولة واحدة يُسحب العنصر الأول \(a_1(t)\)، وبعد جولتين يُسحب العنصر الثاني \(a_2(t)\)، وبصورة عامة فإن العنصر رقم \(k\) يُسحب بعد \(k\) جولات تماماً من ولادة تلك الكومة.
عندما تستقر ديناميكا الأطوال، تصبح عملية الخلط ثابتة تحت الإزاحة: فالموضع الهندسي نفسه داخل الكومة يعاد زيارته بعد عدد ثابت من الجولات. وبما أن العنصر رقم \(k\) في كومة وليدة يعيش \(k\) جولات تماماً، فإن صف القيم المسحوبة رقم \(k\) يكتسب بصورة طبيعية دوراً مقداره \(k\).
لذلك بعد زمن انتقالي \(t_0\) تستخدم التنفيذات الوصف الدوري
$$a_k(t+k)=a_k(t)\qquad (t\ge t_0),$$
أو بصورة مكافئة
$$a_k(t)=p_k(t\bmod k),$$
حيث \(p_k\) هي الدورة المخزنة للصف \(k\). ولا يفترض البرنامج هذه الدورات مسبقاً؛ بل يواصل المحاكاة حتى تتكرر آخر \(k\) قيم في الصف \(k\) بصورة مستقرة، ثم يسجل ذلك الصف على أنه دوري.
لننظر إلى الحالة بعد الجولة \(m\). الكومة التي وُلدت قبل \(d\) جولات قد أُنشئت في الجولة \(m-1-d\). عندئذ تكون قد فقدت بالفعل أول \(d\) عناصر منها، ومن ثم يكون جداء ما تبقى فيها هو
$$\prod_{k=d+1}^{K} a_k(m-1-d),$$
حيث \(K\) هو أكبر صف يبقى غير تافه في المرحلة المستقرة. وتوجد هذه الكومة فقط إذا كان طولها الأصلي لا يقل عن \(d+1\)، وهذا يكافئ الشرط
$$a_{d+1}(m-1-d)\ne 1.$$
إذن يصبح المجموع المطلوب عبارة عن مجموع جداءات ذيول على أقطار جدول الصفوف:
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(a_{d+1}(m-1-d)\ne 1\bigr)\prod_{k=d+1}^{K} a_k(m-1-d)\pmod{1234567891}.$$
وهذه هي النقلة الحاسمة في الحل: بدلاً من التقدم جولة بعد جولة، نستطيع القفز مباشرة إلى الجولة الضخمة المطلوبة عبر تقييم عدد منتهٍ من الصفوف الدورية.
بعد المرحلة الانتقالية لا يهم في كل صف إلا باقي القسمة داخل دورته. فإذا وضعنا \(r_0=m-t_0-1\)، فإن صيغة الجولة الكبيرة تصبح
$$S(n,m)=\sum_{d=0}^{K-1}\mathbf{1}\!\bigl(p_{d+1}((r_0-d)\bmod(d+1))\ne 1\bigr)\prod_{k=d+1}^{K} p_k((r_0-d)\bmod k)\pmod{1234567891}.$$
وبذلك تختزل تبعية العدد الضخم \(m\) إلى فهرسة دورية قصيرة باستخدام الحساب بترديد.
نبدأ بالأكوام الأربع الناتجة من \(2,3,4,5\):
$$[2],\ [3],\ [2,2],\ [5].$$
في الجولة الأولى تُسحب \([2,3,2,5]\)، وبعد ترتيبها نحصل على \([2,2,3,5]\). تصبح الأكوام بعد ذلك \([2]\) و\([2,2,3,5]\)، لذا فإن مجموع الجداءات الباقية يساوي
$$2+(2\cdot 2\cdot 3\cdot 5)=62.$$
في الجولة الثانية تُسحب \([2,2]\). وتصبح الأكوام \([2,3,5]\) و\([2,2]\)، ومن ثم
$$2\cdot 3\cdot 5+2\cdot 2=30+4=34.$$
في الجولة الثالثة تُسحب \([2,2]\) مرة أخرى. المتبقي هو \([3,5]\) و\([2]\) و\([2,2]\)، ولذلك
$$S(5,3)=3\cdot 5+2+2\cdot 2=15+2+4=21.$$
وهذه هي أول قيمة تحقق صغيرة تستخدمها التنفيذات.
تنفيذات C++ وPython وJava تبني أولاً جدولا لأصغر قاسم أولي حتى \(n\)، ثم تفكك كل عدد من \(2\) إلى \(n\) إلى قائمة صاعدة من عوامله الأولية. بهذه الطريقة تتكون الأكوام الابتدائية بكفاءة.
بعد ذلك يحاكي البرنامج عملية الخلط مع مراقبة القيمة المسحوبة رقم \(k\) في كل جولة. ولكل صف \(k\)، تحتفظ التنفيذات بآخر \(k\) قيم مرصودة، ثم تفحص هل تساوي القيمة الحالية القيمة التي ظهرت قبل \(k\) جولات؛ أما الصفوف غير الموجودة فتُملأ بالقيمة \(1\). وعندما تتكرر جميع الصفوف المراقبة مدة كافية، تُسجل دوراتها.
إذا كانت الجولة المطلوبة ما تزال داخل المرحلة الانتقالية، فالجواب يأتي من المحاكاة المباشرة. أما إذا تجاوزناها، فتستخدم التنفيذات الصيغة القطرية السابقة وتكتفي بالفهرسة بترديد داخل الدورات المخزنة. كما تُفحص أولاً قيم صغيرة مثل \(S(5,3)=21\) و\(S(10,100)=257\) للتأكد من صحة المنطق قبل إنتاج القيمة النهائية.
ليكن \(T=\sum_{j=2}^{n}\Omega(j)\)، ولتكن \(K\) أعلى صف دوري يحتوي على قيمة تختلف عن \(1\). بناء جدول أصغر قاسم أولي يحتاج إلى \(O(n\log\log n)\) زمناً و\(O(n)\) ذاكرة، بينما تكوين الأكوام الابتدائية يحتاج في المجمل إلى \(O(T)\) عمليات استخراج للعوامل. إذا اكتُشفت الدورية بعد \(R\) جولات محاكاة وكان عدد الأكوام النشطة في الجولة \(t\) هو \(k_t\)، فإن كلفة المرحلة الانتقالية هي \(O\!\left(\sum_{t=1}^{R} k_t\log k_t\right)\) لأن العوامل المسحوبة تُرتب في كل جولة. وبعد ذلك يمكن الإجابة عن جولة ضخمة في \(O(K^2)\) زمنًا باستخدام الصيغة القطرية، مع \(O(K^2)\) ذاكرة إضافية لتخزين الدورات.