For a permutation \(\sigma\in S_n\), let \(\operatorname{ord}(\sigma)\) be the smallest positive integer \(k\) such that \(\sigma^k=\mathrm{id}\). Since the order of a permutation is the least common multiple of its cycle lengths, the problem asks for
$$g(n)=\mathbb{E}_{\sigma\in S_n}\!\left[\operatorname{ord}(\sigma)^2\right]=\frac{1}{n!}\sum_{\sigma\in S_n}\operatorname{ord}(\sigma)^2.$$
Enumerating all \(n!\) permutations is impossible for large \(n\). The efficient method works with cycle types instead, then compresses completed prime factors so that the lcm states remain small enough to handle.
The implementation never iterates over permutations directly. It sums over cycle multiplicities, tracks the current total length, and stores only the information still needed for the final squared order.
If a permutation has \(m_c\) cycles of length \(c\), then its cycle type satisfies
$$\sum_{c\ge 1} c\,m_c=n.$$
The number of permutations with this cycle type is
$$\frac{n!}{\prod_{c\ge 1} c^{m_c}m_c!},$$
and the order of every permutation of that type is
$$\operatorname{ord}(\sigma)=\operatorname{lcm}\{\,c:m_c>0\,\}.$$
After dividing by \(n!\), the expectation becomes
$$g(n)=\sum_{\substack{m_1,m_2,\dots\ge 0\\ \sum c\,m_c=n}}\frac{\operatorname{lcm}\{\,c:m_c>0\,\}^2}{\prod_{c\ge 1} c^{m_c}m_c!}.$$
So each cycle type contributes its exact probability weight times the square of its order.
At any stage of the algorithm, let \(H_t(\ell)\) denote the accumulated weight of the already processed cycle lengths whose total used size is \(t\) and whose current lcm is \(\ell\). Formally, each state stores sums of terms of the form
$$\frac{1}{\prod c^{m_c}m_c!}$$
for partial cycle selections with total length \(t\) and current lcm \(\ell\).
Fixed points are handled from the start. If we use only cycles of length \(1\), then for every \(t\)
$$H_t(1)=\frac{1}{t!},$$
because \(t\) one-cycles contribute \(1/(1^t t!)\). These values form the initial histogram before longer cycles are inserted.
Fix a cycle length \(c\). If we add \(m\) cycles of length \(c\), then the used length increases by \(mc\), the weight is multiplied by
$$\frac{1}{c^m m!},$$
and the lcm becomes \(\operatorname{lcm}(\ell,c)\) whenever \(m\ge 1\). Therefore each old state \((t,\ell)\) contributes
$$H_t(\ell)\frac{1}{c^m m!}$$
to the new bucket \((t+mc,\operatorname{lcm}(\ell,c))\). When \(m=0\), the state is copied unchanged. Trying every allowed multiplicity \(m\) for every cycle length exactly reproduces the sum over all cycle types.
If the exact lcm were kept forever, the state space would become too large. The key optimization is to process cycle lengths in descending order of their largest prime factor. Let \(P(c)\) denote that largest prime.
Once all lengths \(c\) with \(P(c)=p\) have been processed, no future cycle length is divisible by \(p\). So if the current key is
$$\ell=p^a u,\qquad p\nmid u,$$
then the exponent \(a\) is already final. Later updates can still change \(u\), but they can never add another factor of \(p\).
The final answer uses the square of the permutation order, so the completed factor \(p^a\) contributes a permanent multiplier \(p^{2a}\). We may therefore replace the key \(\ell=p^a u\) by \(u\) and multiply its stored weight by \(p^{2a}\).
Indeed, if a state currently contributes \(\ell^2w\), then
$$\ell^2w=(p^a u)^2w=u^2\bigl(w\,p^{2a}\bigr).$$
So the final total is unchanged after the replacement. For example, just after the block for \(p=5\), a state with key \(60=2^2\cdot 3\cdot 5\) can be rewritten as key \(12\) with its weight multiplied by \(25\). This merging step is what keeps the histogram maps under control.
The cycle types of \(S_3\) are
$$1+1+1,\qquad 2+1,\qquad 3.$$
Their probability weights are
$$\frac{1}{1^3 3!}=\frac{1}{6},\qquad \frac{1}{2^1 1!\,1^1 1!}=\frac{1}{2},\qquad \frac{1}{3^1 1!}=\frac{1}{3},$$
and their orders are \(1\), \(2\), and \(3\). Therefore
$$g(3)=1^2\cdot\frac{1}{6}+2^2\cdot\frac{1}{2}+3^2\cdot\frac{1}{3}=\frac{31}{6}.$$
This matches the first numerical checkpoint. The same dynamic program reproduces it automatically by starting from the fixed-point weights \(1/t!\), then inserting one 2-cycle or one 3-cycle wherever the total length still fits.
After all cycle lengths up to \(n\) have been processed, the histogram at total length \(n\) contains exactly the weighted distribution needed for the expectation. Summing over its remaining keys gives
$$g(n)=\sum_{\ell}\ell^2 H_n(\ell).$$
Because completed prime powers have already been absorbed into the weights block by block, this final sum is small enough to evaluate directly.
The C++, Python, and Java implementations first build a table of the largest prime factor of every integer from \(2\) to \(n\). They then allocate one histogram map for each total length \(0,1,\dots,n\). The initial maps contain only the fixed-point contribution \(1/t!\) at lcm \(1\).
For each prime \(p\) in descending order, the implementation processes every cycle length whose largest prime factor is exactly \(p\). For a chosen length \(c\), it tries all multiplicities \(m\) with \(mc\le n\), applies the factor \(1/(c^m m!)\), updates the total length by \(mc\), and replaces each existing key \(\ell\) by \(\operatorname{lcm}(\ell,c)\) when \(m\ge 1\).
After the full \(p\)-block is finished, every histogram is traversed again. All powers of \(p\) are stripped from each key, the corresponding weight is multiplied by the required factor \(p^{2a}\), and states that collapse to the same smaller key are merged by addition. The final value is taken from the histogram at length \(n\), and the built-in checkpoints at \(n=3\), \(n=5\), and \(n=20\) confirm that the derivation matches the implementation.
The sieve for largest prime factors costs \(O(n\log\log n)\) time and \(O(n)\) memory. The dynamic program dominates the runtime: for each cycle length \(c\), the implementation loops over all multiplicities \(0\le m\le \lfloor n/c\rfloor\), all reachable total lengths, and all active lcm keys in the relevant histogram maps.
If \(M_t\) denotes the number of active keys at total length \(t\), one cycle length contributes roughly
$$\sum_{m=0}^{\lfloor n/c\rfloor}\sum_{t=0}^{n-mc} M_t$$
map updates. There is no substantially sharper closed worst-case formula, because the number of distinct lcm keys depends on how much merging occurs after each prime block. In practice, that prime-sweep compression is the decisive optimization: it keeps both time and memory manageable, whereas storing raw lcm values throughout would grow far too quickly.
Für eine Permutation \(\sigma\in S_n\) sei \(\operatorname{ord}(\sigma)\) die kleinste positive Zahl \(k\) mit \(\sigma^k=\mathrm{id}\). Da die Ordnung einer Permutation das kleinste gemeinsame Vielfache ihrer Zykluslängen ist, sucht das Problem den Wert
$$g(n)=\mathbb{E}_{\sigma\in S_n}\!\left[\operatorname{ord}(\sigma)^2\right]=\frac{1}{n!}\sum_{\sigma\in S_n}\operatorname{ord}(\sigma)^2.$$
Alle \(n!\) Permutationen direkt zu durchlaufen ist für große \(n\) ausgeschlossen. Die effiziente Methode arbeitet deshalb mit Zyklustypen und komprimiert abgeschlossene Primfaktoren, damit die kgV-Zustände beherrschbar bleiben.
Die Implementierung betrachtet nicht einzelne Permutationen, sondern Summen über Zyklusmultiplizitäten. Verfolgt werden nur die bisher belegte Gesamtlänge und genau die kgV-Information, die für das Endergebnis noch relevant ist.
Hat eine Permutation \(m_c\) Zyklen der Länge \(c\), dann gilt
$$\sum_{c\ge 1} c\,m_c=n.$$
Die Anzahl der Permutationen mit diesem Zyklustyp ist
$$\frac{n!}{\prod_{c\ge 1} c^{m_c}m_c!},$$
und ihre Ordnung ist
$$\operatorname{ord}(\sigma)=\operatorname{lcm}\{\,c:m_c>0\,\}.$$
Nach Division durch \(n!\) wird der Erwartungswert zu
$$g(n)=\sum_{\substack{m_1,m_2,\dots\ge 0\\ \sum c\,m_c=n}}\frac{\operatorname{lcm}\{\,c:m_c>0\,\}^2}{\prod_{c\ge 1} c^{m_c}m_c!}.$$
Jeder Zyklustyp liefert also genau sein Wahrscheinlichkeitsgewicht multipliziert mit dem Quadrat seiner Ordnung.
Während des Algorithmus bezeichne \(H_t(\ell)\) das aufsummierte Gewicht der bereits verarbeiteten Zykluslängen, deren bisherige Gesamtlänge \(t\) ist und deren aktuelles kgV gleich \(\ell\) ist. Jeder Zustand sammelt also Terme der Form
$$\frac{1}{\prod c^{m_c}m_c!}$$
für partielle Zyklusauswahlen mit Länge \(t\) und kgV \(\ell\).
Fixpunkte werden von Anfang an berücksichtigt. Verwendet man nur Zyklen der Länge \(1\), dann gilt für jedes \(t\)
$$H_t(1)=\frac{1}{t!},$$
denn \(t\) Eins-Zyklen tragen den Faktor \(1/(1^t t!)\) bei. Genau diese Werte bilden die Initialisierung der Histogramme.
Fixiere eine Zykluslänge \(c\). Fügt man \(m\) Zyklen dieser Länge hinzu, dann wächst die belegte Länge um \(mc\), das Gewicht wird mit
$$\frac{1}{c^m m!}$$
multipliziert, und das kgV wird für \(m\ge 1\) zu \(\operatorname{lcm}(\ell,c)\). Damit liefert ein alter Zustand \((t,\ell)\) den Beitrag
$$H_t(\ell)\frac{1}{c^m m!}$$
zum neuen Zustand \((t+mc,\operatorname{lcm}(\ell,c))\). Der Fall \(m=0\) kopiert den Zustand unverändert. Wenn für jede Zykluslänge alle zulässigen Multiplizitäten ausprobiert werden, erhält man exakt die Summe über alle Zyklustypen.
Würde man das exakte kgV dauerhaft als Schlüssel speichern, würde der Zustandsraum zu stark anwachsen. Die entscheidende Optimierung ist deshalb, die Zykluslängen in absteigender Reihenfolge ihres größten Primfaktors zu verarbeiten. Sei \(P(c)\) dieser größte Primfaktor.
Sobald alle Längen \(c\) mit \(P(c)=p\) abgearbeitet sind, kann keine spätere Zykluslänge mehr durch \(p\) teilbar sein. Ist also der aktuelle Schlüssel
$$\ell=p^a u,\qquad p\nmid u,$$
dann steht der Exponent \(a\) bereits endgültig fest. Spätere Updates können noch \(u\) verändern, aber nie mehr einen weiteren Faktor \(p\) hinzufügen.
Im Endergebnis steht das Quadrat der Permutationsordnung. Der bereits feststehende Faktor \(p^a\) liefert daher dauerhaft den Multiplikator \(p^{2a}\). Man darf also den Schlüssel \(\ell=p^a u\) durch \(u\) ersetzen und das gespeicherte Gewicht mit \(p^{2a}\) multiplizieren.
Tatsächlich gilt für einen Zustand mit Beitrag \(\ell^2w\)
$$\ell^2w=(p^a u)^2w=u^2\bigl(w\,p^{2a}\bigr).$$
Der Gesamtwert ändert sich dadurch nicht. Ein konkretes Beispiel: Direkt nach dem Block für \(p=5\) kann ein Zustand mit Schlüssel \(60=2^2\cdot 3\cdot 5\) als Schlüssel \(12\) mit um \(25\) vergrößertem Gewicht gespeichert werden. Dieses Zusammenführen hält die Histogramme klein.
Die Zyklustypen von \(S_3\) sind
$$1+1+1,\qquad 2+1,\qquad 3.$$
Ihre Wahrscheinlichkeitsgewichte lauten
$$\frac{1}{1^3 3!}=\frac{1}{6},\qquad \frac{1}{2^1 1!\,1^1 1!}=\frac{1}{2},\qquad \frac{1}{3^1 1!}=\frac{1}{3},$$
und ihre Ordnungen sind \(1\), \(2\) und \(3\). Also
$$g(3)=1^2\cdot\frac{1}{6}+2^2\cdot\frac{1}{2}+3^2\cdot\frac{1}{3}=\frac{31}{6}.$$
Das ist genau der erste numerische Kontrollwert. Dasselbe Ergebnis erzeugt die dynamische Programmierung automatisch, indem sie mit den Fixpunktgewichten \(1/t!\) startet und dann passend einen 2-Zyklus oder 3-Zyklus einfügt.
Nachdem alle Zykluslängen bis \(n\) verarbeitet wurden, enthält das Histogramm zur Gesamtlänge \(n\) genau die gewichtete Verteilung, die für den Erwartungswert benötigt wird. Die Endsumme lautet
$$g(n)=\sum_{\ell}\ell^2 H_n(\ell).$$
Da abgeschlossene Primzahlpotenzen blockweise bereits in die Gewichte eingearbeitet wurden, bleibt diese Summe direkt auswertbar.
Die C++-, Python- und Java-Implementierungen bauen zuerst eine Tabelle des größten Primfaktors für alle Zahlen von \(2\) bis \(n\) auf. Danach wird für jede Gesamtlänge \(0,1,\dots,n\) eine Histogramm-Map angelegt. Anfangs enthält jede Map nur den Fixpunktbeitrag \(1/t!\) beim kgV \(1\).
Für jedes Prim \(p\) in absteigender Reihenfolge verarbeitet die Implementierung dann alle Zykluslängen, deren größter Primfaktor genau \(p\) ist. Für eine gewählte Länge \(c\) werden alle Multiplizitäten \(m\) mit \(mc\le n\) ausprobiert, der Faktor \(1/(c^m m!)\) angesetzt, die Gesamtlänge um \(mc\) erhöht und jeder vorhandene Schlüssel \(\ell\) für \(m\ge 1\) durch \(\operatorname{lcm}(\ell,c)\) ersetzt.
Nach Abschluss des gesamten \(p\)-Blocks werden alle Histogramme noch einmal durchlaufen. Dabei werden sämtliche Potenzen von \(p\) aus jedem Schlüssel entfernt, das entsprechende Gewicht mit \(p^{2a}\) multipliziert und Zustände mit demselben reduzierten Schlüssel werden addiert. Der Endwert wird aus dem Histogramm der Länge \(n\) gelesen. Die eingebauten Kontrollwerte für \(n=3\), \(n=5\) und \(n=20\) bestätigen, dass die Herleitung exakt zur Implementierung passt.
Das Sieb für die größten Primfaktoren kostet \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Die dynamische Programmierung dominiert die Laufzeit: Für jede Zykluslänge \(c\) durchläuft die Implementierung alle Multiplizitäten \(0\le m\le \lfloor n/c\rfloor\), alle erreichbaren Gesamtlängen und alle aktiven kgV-Schlüssel in den betreffenden Histogrammen.
Bezeichnet \(M_t\) die Anzahl aktiver Schlüssel bei Gesamtlänge \(t\), dann verursacht eine Zykluslänge ungefähr
$$\sum_{m=0}^{\lfloor n/c\rfloor}\sum_{t=0}^{n-mc} M_t$$
Map-Aktualisierungen. Eine deutlich schärfere geschlossene Worst-Case-Formel gibt es hier nicht, weil die Zahl verschiedener kgV-Schlüssel davon abhängt, wie stark die Primblock-Kompression Zustände zusammenführt. In der Praxis ist genau diese Kompression entscheidend: Sie hält sowohl Laufzeit als auch Speicherverbrauch in einem handhabbaren Bereich.
\(\sigma\in S_n\) bir permütasyon olsun. \(\operatorname{ord}(\sigma)\), \(\sigma^k=\mathrm{id}\) eşitliğini sağlayan en küçük pozitif \(k\) sayısıdır. Bir permütasyonun mertebesi çevrim uzunluklarının EKOK'u olduğundan, problem şu değeri ister:
$$g(n)=\mathbb{E}_{\sigma\in S_n}\!\left[\operatorname{ord}(\sigma)^2\right]=\frac{1}{n!}\sum_{\sigma\in S_n}\operatorname{ord}(\sigma)^2.$$
Büyük \(n\) için tüm \(n!\) permütasyonu tek tek dolaşmak imkansızdır. Verimli çözüm bunun yerine çevrim tipleriyle çalışır ve tamamlanmış asal çarpanları ağırlığa aktararak EKOK durumlarının patlamasını engeller.
Uygulama permütasyonları tek tek üretmez. Onların yerine çevrim çoklukları üzerinde toplama yapar; durum olarak da yalnızca kullanılan toplam uzunluğu ve nihai mertebe karesi için hâlâ gerekli olan EKOK bilgisini tutar.
Bir permütasyonda uzunluğu \(c\) olan çevrim sayısı \(m_c\) ise
$$\sum_{c\ge 1} c\,m_c=n$$
olur. Bu çevrim tipine sahip permütasyon sayısı
$$\frac{n!}{\prod_{c\ge 1} c^{m_c}m_c!}$$
ve bu tipteki her permütasyonun mertebesi
$$\operatorname{ord}(\sigma)=\operatorname{lcm}\{\,c:m_c>0\,\}$$
şeklindedir. Böylece \(n!\)'ye bölünmüş beklenti
$$g(n)=\sum_{\substack{m_1,m_2,\dots\ge 0\\ \sum c\,m_c=n}}\frac{\operatorname{lcm}\{\,c:m_c>0\,\}^2}{\prod_{c\ge 1} c^{m_c}m_c!}$$
olur. Yani her çevrim tipi, kendi olasılık ağırlığıyla mertebenin karesini çarparak katkı verir.
Algoritmanın herhangi bir aşamasında \(H_t(\ell)\), şimdiye kadar işlenmiş çevrim uzunlukları arasından toplam uzunluğu \(t\) olan ve mevcut EKOK'u \(\ell\) olan kısmi seçimlerin toplam ağırlığı olsun. Her durum, biçim olarak
$$\frac{1}{\prod c^{m_c}m_c!}$$
şeklindeki terimlerin toplamını tutar.
Sabit noktalar baştan hesaba katılır. Yalnızca uzunluğu \(1\) olan çevrimler kullanılırsa her \(t\) için
$$H_t(1)=\frac{1}{t!}$$
elde edilir; çünkü \(t\) tane 1-çevrimin ağırlığı \(1/(1^t t!)\)'dir. Başlangıç histogramı tam olarak bu değerlerle kurulur.
Sabit bir \(c\) çevrim uzunluğu alalım. Uzunluğu \(c\) olan \(m\) adet çevrim eklenirse kullanılan toplam uzunluk \(mc\) kadar artar, ağırlık
$$\frac{1}{c^m m!}$$
ile çarpılır ve \(m\ge 1\) olduğunda EKOK \(\operatorname{lcm}(\ell,c)\) olur. Dolayısıyla eski \((t,\ell)\) durumu
$$H_t(\ell)\frac{1}{c^m m!}$$
katkısını yeni \((t+mc,\operatorname{lcm}(\ell,c))\) kovasına yollar. \(m=0\) durumu ise eski halin aynen taşınmasıdır. Her uzunluk için tüm uygun çokluklar denenince, tüm çevrim tipleri eksiksiz taranmış olur.
EKOK değeri ham haliyle tutulursa durum sayısı çok hızlı büyür. Temel optimizasyon, çevrim uzunluklarını en büyük asal bölenlerine göre azalan sırayla işlemekten gelir. \(P(c)\), \(c\)'nin en büyük asal böleni olsun.
\(P(c)=p\) olan bütün uzunluklar işlendiğinde, artık sonraki hiçbir çevrim uzunluğu \(p\)'ye bölünemez. Bu yüzden mevcut anahtar
$$\ell=p^a u,\qquad p\nmid u$$
şeklindeyse, \(a\) üssü artık kesinleşmiştir. Daha sonra \(u\) değişebilir ama \(p\)'nin üssü bir daha artamaz.
Sonuçta mertebenin karesi kullanıldığı için kesinleşmiş \(p^a\) çarpanı da kalıcı olarak \(p^{2a}\) katkısı yapar. Bu nedenle \(\ell=p^a u\) anahtarını \(u\) ile değiştirmek ve ağırlığı \(p^{2a}\) ile çarpmak tamamen güvenlidir.
Gerçekten, katkı \(\ell^2 w\) ise
$$\ell^2 w=(p^a u)^2w=u^2\bigl(w\,p^{2a}\bigr)$$
olur. Toplam değişmez. Örneğin \(p=5\) bloğu bittikten hemen sonra anahtar \(60=2^2\cdot 3\cdot 5\) olan bir durum, ağırlığı \(25\) ile çarpılarak anahtar \(12\) biçiminde saklanabilir. Histogramları pratikte kontrol altında tutan adım budur.
\(S_3\)'ün çevrim tipleri
$$1+1+1,\qquad 2+1,\qquad 3$$
şeklindedir. Olasılık ağırlıkları
$$\frac{1}{1^3 3!}=\frac{1}{6},\qquad \frac{1}{2^1 1!\,1^1 1!}=\frac{1}{2},\qquad \frac{1}{3^1 1!}=\frac{1}{3}$$
ve mertebeleri sırasıyla \(1\), \(2\), \(3\)'tür. Bu yüzden
$$g(3)=1^2\cdot\frac{1}{6}+2^2\cdot\frac{1}{2}+3^2\cdot\frac{1}{3}=\frac{31}{6}$$
elde edilir. Bu, uygulamanın kullandığı ilk kontrol değeridir. Aynı sonuç, DP'nin önce \(1/t!\) sabit nokta ağırlıklarıyla başlayıp sonra sığdığı yerde bir 2-çevrim ya da 3-çevrim eklemesiyle otomatik olarak çıkar.
\(n\)'e kadar olan tüm çevrim uzunlukları işlendiğinde, toplam uzunluğu \(n\) olan histogram tam olarak istenen ağırlıklı dağılımı içerir. Son toplam
$$g(n)=\sum_{\ell}\ell^2 H_n(\ell)$$
şeklindedir. Tamamlanmış asal kuvvetler blok blok ağırlığa aktarıldığı için bu toplam doğrudan hesaplanabilir.
C++, Python ve Java uygulamaları önce \(2\) ile \(n\) arasındaki her sayı için en büyük asal böleni veren bir tablo kurar. Sonra toplam uzunluk \(0,1,\dots,n\) için birer histogram haritası ayırır. Başlangıçta her haritada EKOK \(1\) için yalnızca \(1/t!\) sabit nokta katkısı bulunur.
Daha sonra azalan asal sırasıyla her \(p\) için, en büyük asal böleni tam olarak \(p\) olan bütün çevrim uzunlukları işlenir. Seçilen bir \(c\) için \(mc\le n\) koşulunu sağlayan tüm \(m\) çoklukları denenir, \(1/(c^m m!)\) katsayısı uygulanır, toplam uzunluk \(mc\) kadar büyütülür ve \(m\ge 1\) ise mevcut her \(\ell\) anahtarı \(\operatorname{lcm}(\ell,c)\) ile güncellenir.
Bir \(p\)-bloğu tamamlanınca tüm histogramlar tekrar dolaşılır. Her anahtardan \(p\)'nin bütün kuvvetleri çıkarılır, gerekli \(p^{2a}\) çarpanı ağırlığa eklenir ve aynı küçülmüş anahtara düşen durumlar toplanır. Son değer toplam uzunluğu \(n\) olan histogramdan alınır. \(n=3\), \(n=5\) ve \(n=20\) için yerleşik kontrol değerleri, bu türetmenin uygulamayla tam uyumlu olduğunu gösterir.
En büyük asal bölen tablosunu kuran elek \(O(n\log\log n)\) zamanda ve \(O(n)\) bellekte çalışır. Asıl maliyeti dinamik programlama belirler: her çevrim uzunluğu \(c\) için uygulama \(0\le m\le \lfloor n/c\rfloor\) çokluklarını, erişilebilir toplam uzunlukları ve ilgili histogramlardaki aktif EKOK anahtarlarını dolaşır.
Toplam uzunluk \(t\) için aktif anahtar sayısı \(M_t\) ise, tek bir çevrim uzunluğu yaklaşık
$$\sum_{m=0}^{\lfloor n/c\rfloor}\sum_{t=0}^{n-mc} M_t$$
adet harita güncellemesi üretir. Bundan daha keskin kapalı bir worst-case formülü yazmak zordur; çünkü farklı EKOK anahtarlarının sayısı, her asal bloğundan sonra ne kadar birleşme olduğuna bağlıdır. Pratikte belirleyici optimizasyon tam olarak bu asal-bazlı sıkıştırmadır; hem zamanı hem belleği yönetilebilir düzeyde tutar.
Para una permutación \(\sigma\in S_n\), sea \(\operatorname{ord}(\sigma)\) el menor entero positivo \(k\) tal que \(\sigma^k=\mathrm{id}\). Como el orden de una permutación es el mínimo común múltiplo de las longitudes de sus ciclos, el problema pide calcular
$$g(n)=\mathbb{E}_{\sigma\in S_n}\!\left[\operatorname{ord}(\sigma)^2\right]=\frac{1}{n!}\sum_{\sigma\in S_n}\operatorname{ord}(\sigma)^2.$$
Recorrer las \(n!\) permutaciones es imposible cuando \(n\) es grande. La solución eficiente trabaja con tipos de ciclo y, además, va absorbiendo factores primos ya fijados dentro del peso para que los estados de m.c.m. no crezcan sin control.
La implementación no enumera permutaciones una por una. En su lugar suma sobre multiplicidades de ciclos, y solo mantiene la longitud total ya usada y la parte del m.c.m. que todavía importa para el cuadrado final del orden.
Si una permutación tiene \(m_c\) ciclos de longitud \(c\), entonces
$$\sum_{c\ge 1} c\,m_c=n.$$
El número de permutaciones con ese tipo de ciclo es
$$\frac{n!}{\prod_{c\ge 1} c^{m_c}m_c!},$$
y el orden de cualquiera de ellas es
$$\operatorname{ord}(\sigma)=\operatorname{lcm}\{\,c:m_c>0\,\}.$$
Al dividir por \(n!\), el valor esperado se convierte en
$$g(n)=\sum_{\substack{m_1,m_2,\dots\ge 0\\ \sum c\,m_c=n}}\frac{\operatorname{lcm}\{\,c:m_c>0\,\}^2}{\prod_{c\ge 1} c^{m_c}m_c!}.$$
Así, cada tipo de ciclo aporta exactamente su peso probabilístico multiplicado por el cuadrado de su orden.
En cualquier etapa del algoritmo, \(H_t(\ell)\) representa el peso acumulado de las longitudes de ciclo ya procesadas cuya longitud total usada es \(t\) y cuyo m.c.m. actual es \(\ell\). Cada estado guarda sumas de términos de la forma
$$\frac{1}{\prod c^{m_c}m_c!}$$
para selecciones parciales de ciclos con longitud total \(t\) y m.c.m. \(\ell\).
Los puntos fijos se incorporan desde el principio. Si solo usamos ciclos de longitud \(1\), entonces para todo \(t\)
$$H_t(1)=\frac{1}{t!},$$
porque \(t\) ciclos de longitud \(1\) aportan \(1/(1^t t!)\). Esos valores forman el histograma inicial antes de insertar ciclos más largos.
Fijemos una longitud de ciclo \(c\). Si añadimos \(m\) ciclos de longitud \(c\), la longitud usada aumenta en \(mc\), el peso se multiplica por
$$\frac{1}{c^m m!},$$
y el m.c.m. pasa a ser \(\operatorname{lcm}(\ell,c)\) cuando \(m\ge 1\). Por tanto, cada estado antiguo \((t,\ell)\) aporta
$$H_t(\ell)\frac{1}{c^m m!}$$
al nuevo cubo \((t+mc,\operatorname{lcm}(\ell,c))\). El caso \(m=0\) simplemente copia el estado anterior. Recorriendo todas las multiplicidades permitidas para cada longitud de ciclo se reproduce exactamente la suma sobre todos los tipos de ciclo.
Si se conservara siempre el m.c.m. exacto como clave, el número de estados crecería demasiado. La optimización central consiste en procesar las longitudes de ciclo en orden decreciente de su mayor factor primo. Denotemos ese primo por \(P(c)\).
Una vez procesadas todas las longitudes \(c\) con \(P(c)=p\), ninguna longitud futura será divisible por \(p\). Por eso, si la clave actual es
$$\ell=p^a u,\qquad p\nmid u,$$
el exponente \(a\) ya quedó fijado para siempre. Las actualizaciones posteriores todavía pueden cambiar \(u\), pero ya no pueden añadir otra potencia de \(p\).
Como el resultado final usa el cuadrado del orden, el factor ya decidido \(p^a\) aporta de forma permanente \(p^{2a}\). Por ello podemos sustituir la clave \(\ell=p^a u\) por \(u\) y multiplicar el peso almacenado por \(p^{2a}\).
En efecto, si un estado contribuye actualmente \(\ell^2 w\), entonces
$$\ell^2 w=(p^a u)^2w=u^2\bigl(w\,p^{2a}\bigr).$$
El total final no cambia. Por ejemplo, justo después del bloque de \(p=5\), una clave \(60=2^2\cdot 3\cdot 5\) puede reemplazarse por la clave \(12\) y su peso se multiplica por \(25\). Esa fusión de estados es la razón principal por la que el método sigue siendo práctico.
Los tipos de ciclo de \(S_3\) son
$$1+1+1,\qquad 2+1,\qquad 3.$$
Sus pesos probabilísticos son
$$\frac{1}{1^3 3!}=\frac{1}{6},\qquad \frac{1}{2^1 1!\,1^1 1!}=\frac{1}{2},\qquad \frac{1}{3^1 1!}=\frac{1}{3},$$
y sus órdenes son \(1\), \(2\) y \(3\). Luego
$$g(3)=1^2\cdot\frac{1}{6}+2^2\cdot\frac{1}{2}+3^2\cdot\frac{1}{3}=\frac{31}{6}.$$
Ese valor coincide con la primera comprobación numérica. La misma programación dinámica lo obtiene de forma automática partiendo de los pesos de puntos fijos \(1/t!\) y añadiendo después un 2-ciclo o un 3-ciclo cuando la longitud total todavía lo permite.
Después de procesar todas las longitudes de ciclo hasta \(n\), el histograma en longitud total \(n\) contiene exactamente la distribución ponderada necesaria para el valor esperado. La suma final es
$$g(n)=\sum_{\ell}\ell^2 H_n(\ell).$$
Como las potencias primas ya terminadas se han absorbido bloque por bloque dentro de los pesos, esta suma final puede evaluarse directamente.
Las implementaciones en C++, Python y Java construyen primero una tabla con el mayor factor primo de cada entero entre \(2\) y \(n\). Después reservan un mapa-histograma para cada longitud total \(0,1,\dots,n\). Al principio, cada mapa contiene solo la contribución de puntos fijos \(1/t!\) con m.c.m. igual a \(1\).
Para cada primo \(p\) en orden descendente, la implementación procesa todas las longitudes de ciclo cuyo mayor factor primo es exactamente \(p\). Para una longitud \(c\) fija, prueba todas las multiplicidades \(m\) con \(mc\le n\), aplica el factor \(1/(c^m m!)\), aumenta la longitud total en \(mc\) y sustituye cada clave existente \(\ell\) por \(\operatorname{lcm}(\ell,c)\) cuando \(m\ge 1\).
Cuando termina el bloque completo de \(p\), todos los histogramas se recorren otra vez. Se eliminan de cada clave todas las potencias de \(p\), se multiplica el peso por el factor correspondiente \(p^{2a}\) y se suman los estados que colapsan a la misma clave reducida. El valor final se extrae del histograma de longitud \(n\), y las comprobaciones incorporadas en \(n=3\), \(n=5\) y \(n=20\) validan la derivación matemática.
La criba para mayores factores primos cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. El tiempo dominante lo aporta la programación dinámica: para cada longitud de ciclo \(c\), la implementación recorre todas las multiplicidades \(0\le m\le \lfloor n/c\rfloor\), todas las longitudes totales alcanzables y todas las claves activas de m.c.m. en los histogramas implicados.
Si \(M_t\) es el número de claves activas en la longitud total \(t\), una sola longitud de ciclo genera aproximadamente
$$\sum_{m=0}^{\lfloor n/c\rfloor}\sum_{t=0}^{n-mc} M_t$$
actualizaciones de mapas. No hay una cota cerrada mucho más precisa que esta, porque el número real de claves de m.c.m. depende de cuánto se fusionen después de cada bloque primo. En la práctica, esa compresión por primos es la optimización decisiva: mantiene bajo control tanto el tiempo como la memoria.
对任意置换 \(\sigma\in S_n\)，记 \(\operatorname{ord}(\sigma)\) 为满足 \(\sigma^k=\mathrm{id}\) 的最小正整数 \(k\)。置换的阶等于其所有循环长度的最小公倍数，因此本题要求的是
$$g(n)=\mathbb{E}_{\sigma\in S_n}\!\left[\operatorname{ord}(\sigma)^2\right]=\frac{1}{n!}\sum_{\sigma\in S_n}\operatorname{ord}(\sigma)^2.$$
当 \(n\) 很大时，直接枚举全部 \(n!\) 个置换根本不可行。高效做法是改为枚举循环型，并且在某个素数的贡献已经完全确定后，立刻把它吸收到权重里，从而避免最小公倍数状态无限膨胀。
实现并不会逐个生成置换，而是对循环长度的出现次数求和。整个动态规划只跟踪两类信息：目前已经使用了多少总长度，以及当前还需要保留的最小公倍数部分。
如果一个置换中长度为 \(c\) 的循环有 \(m_c\) 个，那么必然满足
$$\sum_{c\ge 1} c\,m_c=n.$$
具有该循环型的置换个数是
$$\frac{n!}{\prod_{c\ge 1} c^{m_c}m_c!},$$
而这种循环型对应的置换阶为
$$\operatorname{ord}(\sigma)=\operatorname{lcm}\{\,c:m_c>0\,\}.$$
于是除以 \(n!\) 以后，期望值可以写成
$$g(n)=\sum_{\substack{m_1,m_2,\dots\ge 0\\ \sum c\,m_c=n}}\frac{\operatorname{lcm}\{\,c:m_c>0\,\}^2}{\prod_{c\ge 1} c^{m_c}m_c!}.$$
这说明每一种循环型的贡献，正好等于它在均匀随机置换下的概率乘以该循环型阶的平方。
在算法的任意阶段，记 \(H_t(\ell)\) 为“已经处理过的循环长度”所形成的部分结构中，总长度恰好为 \(t\)、当前最小公倍数为 \(\ell\) 的所有情况的总权重。每个状态累积的项都形如
$$\frac{1}{\prod c^{m_c}m_c!}$$
也就是部分循环选择对应的概率权重。
长度为 \(1\) 的循环，也就是不动点，会在一开始直接放进去。如果只使用 1-循环，那么对每个 \(t\) 都有
$$H_t(1)=\frac{1}{t!},$$
因为 \(t\) 个 1-循环的权重就是 \(1/(1^t t!)\)。这正是初始直方图的来源。
固定某个循环长度 \(c\)。如果加入 \(m\) 个长度为 \(c\) 的循环，那么总长度增加 \(mc\)，权重乘上
$$\frac{1}{c^m m!},$$
而当 \(m\ge 1\) 时，新的最小公倍数变成 \(\operatorname{lcm}(\ell,c)\)。因此，旧状态 \((t,\ell)\) 会向新状态 \((t+mc,\operatorname{lcm}(\ell,c))\) 贡献
$$H_t(\ell)\frac{1}{c^m m!}.$$
当 \(m=0\) 时，这个状态只是原样保留。对每个循环长度都尝试所有允许的 \(m\)，就等价于把所有循环型都完整地累加了一遍。
如果一直把完整的最小公倍数当作状态键保存，状态数量会增长得非常快。关键优化是：按照“最大素因子”从大到小处理循环长度。记 \(P(c)\) 为 \(c\) 的最大素因子。
一旦所有满足 \(P(c)=p\) 的长度都处理完，以后还没处理的任何循环长度都不可能再被 \(p\) 整除。于是如果当前键写成
$$\ell=p^a u,\qquad p\nmid u,$$
那么其中 \(p\) 的指数 \(a\) 已经最终确定。后续转移仍然可能改变 \(u\)，但再也不会新增一个 \(p\) 因子。
最终答案使用的是阶的平方，所以已经确定的 \(p^a\) 会永久贡献一个因子 \(p^{2a}\)。因此我们可以把键 \(\ell=p^a u\) 改写成 \(u\)，同时把该状态的权重乘以 \(p^{2a}\)。
原因非常直接：如果某个状态当前贡献的是 \(\ell^2 w\)，那么
$$\ell^2 w=(p^a u)^2w=u^2\bigl(w\,p^{2a}\bigr).$$
也就是说，把 \(p^a\) 从键里删掉、再把 \(p^{2a}\) 放进权重，最终总和完全不变。例如在 \(p=5\) 这一组处理结束后，键 \(60=2^2\cdot 3\cdot 5\) 的状态可以改写为键 \(12\)，同时把权重乘以 \(25\)。这一步会把很多不同的键合并起来，是整个算法能跑到 \(n=350\) 的核心原因。
\(S_3\) 的循环型只有三种：
$$1+1+1,\qquad 2+1,\qquad 3.$$
它们的概率权重分别为
$$\frac{1}{1^3 3!}=\frac{1}{6},\qquad \frac{1}{2^1 1!\,1^1 1!}=\frac{1}{2},\qquad \frac{1}{3^1 1!}=\frac{1}{3},$$
对应的阶分别是 \(1\)、\(2\)、\(3\)。因此
$$g(3)=1^2\cdot\frac{1}{6}+2^2\cdot\frac{1}{2}+3^2\cdot\frac{1}{3}=\frac{31}{6}.$$
这正好是程序里的第一个校验值。动态规划也会自动得到同样的结果：先用 \(1/t!\) 初始化全部不动点情况，再在长度允许的位置加入一个 2-循环或一个 3-循环即可。
当所有不超过 \(n\) 的循环长度都处理完成后，总长度为 \(n\) 的直方图就已经包含了计算期望所需的完整加权分布。最后只需做
$$g(n)=\sum_{\ell}\ell^2 H_n(\ell).$$
由于每个已经结束的素数块都提前把对应的平方贡献吸收进了权重里，这个最终求和就可以直接完成。
C++、Python 和 Java 实现首先会构造一个表，记录 \(2\) 到 \(n\) 每个整数的最大素因子。然后为总长度 \(0,1,\dots,n\) 各建立一个映射型直方图。初始化时，每个长度 \(t\) 只有一个键 \(\ell=1\)，其权重为不动点贡献 \(1/t!\)。
接着按素数从大到小枚举。对每个素数 \(p\)，实现会处理所有最大素因子恰好等于 \(p\) 的循环长度。固定某个长度 \(c\) 后，会尝试所有满足 \(mc\le n\) 的出现次数 \(m\)，乘上 \(1/(c^m m!)\)，把总长度增加 \(mc\)，并在 \(m\ge 1\) 时把原来的键 \(\ell\) 更新为 \(\operatorname{lcm}(\ell,c)\)。
当整个 \(p\)-块处理完以后，所有直方图都会再扫描一遍：把每个键中的 \(p\) 因子全部除掉，把相应的 \(p^{2a}\) 补到权重里，然后把缩成同一个新键的状态相加。最终答案来自总长度 \(n\) 的那张直方图，而 \(n=3\)、\(n=5\)、\(n=20\) 这些校验值说明数学推导与实现细节完全一致。
最大素因子筛法需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。真正主导运行时间的是动态规划部分：对每一个循环长度 \(c\)，实现都要遍历所有 \(0\le m\le \lfloor n/c\rfloor\) 的出现次数、所有仍可达的总长度，以及这些长度对应映射中的全部活跃最小公倍数键。
如果记总长度 \(t\) 处的活跃键数量为 \(M_t\)，那么单个循环长度大约会产生
$$\sum_{m=0}^{\lfloor n/c\rfloor}\sum_{t=0}^{n-mc} M_t$$
次映射更新。这里很难再给出一个明显更紧的封闭最坏情况上界，因为不同最小公倍数键的数量取决于每个素数块结束后到底合并了多少状态。实践中，按最大素因子进行的这一步压缩是决定性的优化，没有它，时间和内存都会增长得过快。
Для перестановки \(\sigma\in S_n\) обозначим через \(\operatorname{ord}(\sigma)\) наименьшее положительное число \(k\), для которого \(\sigma^k=\mathrm{id}\). Поскольку порядок перестановки равен НОК длин её циклов, задача требует вычислить
$$g(n)=\mathbb{E}_{\sigma\in S_n}\!\left[\operatorname{ord}(\sigma)^2\right]=\frac{1}{n!}\sum_{\sigma\in S_n}\operatorname{ord}(\sigma)^2.$$
Перебирать все \(n!\) перестановок невозможно уже при умеренно больших \(n\). Поэтому решение переходит к типам циклов и затем по мере возможности переносит завершённые простые множители из ключа НОК в вес состояния.
Реализация не строит перестановки по одной. Вместо этого она суммирует по кратностям циклов и хранит только использованную суммарную длину и ту часть НОК, которая ещё важна для окончательного квадрата порядка.
Если в перестановке число циклов длины \(c\) равно \(m_c\), то
$$\sum_{c\ge 1} c\,m_c=n.$$
Число перестановок с таким цикловым типом равно
$$\frac{n!}{\prod_{c\ge 1} c^{m_c}m_c!},$$
а их порядок равен
$$\operatorname{ord}(\sigma)=\operatorname{lcm}\{\,c:m_c>0\,\}.$$
После деления на \(n!\) математическое ожидание принимает вид
$$g(n)=\sum_{\substack{m_1,m_2,\dots\ge 0\\ \sum c\,m_c=n}}\frac{\operatorname{lcm}\{\,c:m_c>0\,\}^2}{\prod_{c\ge 1} c^{m_c}m_c!}.$$
То есть вклад каждого циклового типа равен его вероятности для случайной перестановки, умноженной на квадрат порядка.
На любой стадии алгоритма \(H_t(\ell)\) обозначает накопленный вес уже обработанных длин циклов, для которых суммарная использованная длина равна \(t\), а текущий НОК равен \(\ell\). Каждый такой вес является суммой слагаемых вида
$$\frac{1}{\prod c^{m_c}m_c!}$$
для частичных наборов циклов с общей длиной \(t\) и НОК \(\ell\).
Неподвижные точки учитываются сразу. Если используются только циклы длины \(1\), то для любого \(t\)
$$H_t(1)=\frac{1}{t!},$$
потому что \(t\) одноциклов дают вес \(1/(1^t t!)\). Именно это инициализирует стартовые гистограммы.
Зафиксируем длину цикла \(c\). Если добавить \(m\) циклов этой длины, то суммарная длина увеличится на \(mc\), вес умножится на
$$\frac{1}{c^m m!},$$
а НОК при \(m\ge 1\) станет равным \(\operatorname{lcm}(\ell,c)\). Значит, старое состояние \((t,\ell)\) даёт вклад
$$H_t(\ell)\frac{1}{c^m m!}$$
в новое состояние \((t+mc,\operatorname{lcm}(\ell,c))\). Случай \(m=0\) просто переносит состояние без изменений. Перебор всех допустимых кратностей для каждой длины цикла точно воспроизводит сумму по всем цикловым типам.
Если хранить полный НОК без сжатия, число состояний станет слишком большим. Ключевая оптимизация состоит в том, чтобы обрабатывать длины циклов в порядке убывания их наибольшего простого делителя. Обозначим его через \(P(c)\).
После того как обработаны все длины \(c\) с \(P(c)=p\), ни одна будущая длина уже не делится на \(p\). Поэтому если текущий ключ имеет вид
$$\ell=p^a u,\qquad p\nmid u,$$
то показатель \(a\) уже окончательно зафиксирован. Позднейшие переходы могут менять \(u\), но не способны увеличить \(p\)-адическую степень.
В конце требуется квадрат порядка, значит уже зафиксированный множитель \(p^a\) навсегда даёт вклад \(p^{2a}\). Следовательно, ключ \(\ell=p^a u\) можно заменить на \(u\), а сохранённый вес умножить на \(p^{2a}\).
Действительно, если текущее состояние вносит \(\ell^2 w\), то
$$\ell^2 w=(p^a u)^2w=u^2\bigl(w\,p^{2a}\bigr).$$
Итоговая сумма при этом не меняется. Например, сразу после блока для \(p=5\) состояние с ключом \(60=2^2\cdot 3\cdot 5\) можно переписать как ключ \(12\), умножив вес на \(25\). Именно это объединение состояний и делает алгоритм практически выполнимым.
Цикловые типы группы \(S_3\) таковы:
$$1+1+1,\qquad 2+1,\qquad 3.$$
Их вероятностные веса равны
$$\frac{1}{1^3 3!}=\frac{1}{6},\qquad \frac{1}{2^1 1!\,1^1 1!}=\frac{1}{2},\qquad \frac{1}{3^1 1!}=\frac{1}{3},$$
а порядки равны \(1\), \(2\) и \(3\). Поэтому
$$g(3)=1^2\cdot\frac{1}{6}+2^2\cdot\frac{1}{2}+3^2\cdot\frac{1}{3}=\frac{31}{6}.$$
Это совпадает с первой встроенной проверкой. Та же динамика получает этот ответ автоматически: она стартует с весов неподвижных точек \(1/t!\), а затем добавляет один 2-цикл или один 3-цикл там, где это позволяет общая длина.
После обработки всех длин циклов до \(n\) гистограмма для суммарной длины \(n\) содержит ровно то взвешенное распределение, которое нужно для ожидания. Остаётся просуммировать
$$g(n)=\sum_{\ell}\ell^2 H_n(\ell).$$
Так как завершённые простые степени уже по блокам перенесены в веса, эта финальная сумма остаётся компактной.
Реализации на C++, Python и Java сначала строят таблицу наибольших простых делителей для всех чисел от \(2\) до \(n\). Затем для каждой суммарной длины \(0,1,\dots,n\) создаётся отдельная гистограмма-словарь. В начале в ней есть только вклад неподвижных точек \(1/t!\) при ключе НОК, равном \(1\).
Далее для каждого простого \(p\) в порядке убывания обрабатываются все длины циклов, у которых наибольший простой делитель равен именно \(p\). Для выбранной длины \(c\) перебираются все кратности \(m\), удовлетворяющие \(mc\le n\), применяется множитель \(1/(c^m m!)\), суммарная длина увеличивается на \(mc\), а при \(m\ge 1\) каждый текущий ключ \(\ell\) заменяется на \(\operatorname{lcm}(\ell,c)\).
После завершения всего блока по \(p\) все гистограммы обходятся повторно. Из каждого ключа удаляются все множители \(p\), вес умножается на нужный коэффициент \(p^{2a}\), а состояния с одинаковым сокращённым ключом складываются. Итог берётся из гистограммы длины \(n\), а контрольные значения для \(n=3\), \(n=5\) и \(n=20\) подтверждают правильность вывода.
Решето для наибольших простых делителей требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Основное время работы тратится на динамику: для каждой длины цикла \(c\) реализация перебирает все кратности \(0\le m\le \lfloor n/c\rfloor\), все достижимые суммарные длины и все активные ключи НОК в соответствующих словарях.
Если \(M_t\) обозначает число активных ключей при суммарной длине \(t\), то одна длина цикла даёт примерно
$$\sum_{m=0}^{\lfloor n/c\rfloor}\sum_{t=0}^{n-mc} M_t$$
обновлений словарей. Более точную универсальную замкнутую оценку здесь дать трудно, потому что число различных ключей НОК зависит от того, насколько сильно они сливаются после каждого простого блока. На практике именно это сжатие по наибольшему простому делителю и является решающим: без него и время, и память росли бы слишком быстро.
إذا كانت \(\sigma\in S_n\) تبديلة، فإن \(\operatorname{ord}(\sigma)\) هو أصغر عدد صحيح موجب \(k\) يحقق \(\sigma^k=\mathrm{id}\). وبما أن رتبة التبديلة تساوي \(\operatorname{lcm}\) لأطوال دوراتها، فإن المطلوب هو حساب
$$g(n)=\mathbb{E}_{\sigma\in S_n}\!\left[\operatorname{ord}(\sigma)^2\right]=\frac{1}{n!}\sum_{\sigma\in S_n}\operatorname{ord}(\sigma)^2.$$
المرور على جميع التبديلات وعددها \(n!\) مستحيل عندما يكبر \(n\). لذلك يعتمد الحل الفعال على أنواع الدورات بدلًا من التبديلات نفسها، ثم ينقل قوى العوامل الأولية التي حُسمت نهائيًا إلى الوزن حتى لا تتضخم حالات \(\operatorname{lcm}\).
التنفيذ لا يولد التبديلات واحدة واحدة. بدلًا من ذلك يجمع على عدد الدورات من كل طول، ويحفظ فقط الطول الكلي المستخدم والجزء من \(\operatorname{lcm}\) الذي ما زال مؤثرًا في مربع الرتبة النهائي.
إذا كان عدد الدورات ذات الطول \(c\) هو \(m_c\)، فلابد أن
$$\sum_{c\ge 1} c\,m_c=n.$$
وعدد التبديلات التي تملك هذا النمط الدوري هو
$$\frac{n!}{\prod_{c\ge 1} c^{m_c}m_c!},$$
أما رتبة أي تبديلة من هذا النمط فهي
$$\operatorname{ord}(\sigma)=\operatorname{lcm}\{\,c:m_c>0\,\}.$$
وبعد القسمة على \(n!\) يصبح المتوسط المطلوب
$$g(n)=\sum_{\substack{m_1,m_2,\dots\ge 0\\ \sum c\,m_c=n}}\frac{\operatorname{lcm}\{\,c:m_c>0\,\}^2}{\prod_{c\ge 1} c^{m_c}m_c!}.$$
إذن مساهمة كل نمط دوري هي وزنه الاحتمالي الدقيق مضروبًا في مربع رتبته.
في أي مرحلة من الخوارزمية، نرمز بـ \(H_t(\ell)\) إلى الوزن المتراكم لاختيارات الأطوال التي عولجت بالفعل، بحيث يكون الطول الكلي المستعمل هو \(t\) و\(\operatorname{lcm}\) الحالي هو \(\ell\). كل حالة تجمع حدودًا من الشكل
$$\frac{1}{\prod c^{m_c}m_c!}$$
لاختيارات جزئية من الدورات ذات طول كلي \(t\) و\(\operatorname{lcm}\) يساوي \(\ell\).
النقاط الثابتة تدخل منذ البداية. فإذا استُعملت فقط دورات الطول \(1\)، فعند كل \(t\) نحصل على
$$H_t(1)=\frac{1}{t!},$$
لأن \(t\) دورات أحادية الطول تعطي الوزن \(1/(1^t t!)\). وهذه بالضبط هي قيم التهيئة الأولى للخرائط.
لنثبت طول دورة \(c\). إذا أضفنا \(m\) دورات من هذا الطول، فإن الطول الكلي يزداد بمقدار \(mc\)، والوزن يُضرب في
$$\frac{1}{c^m m!},$$
كما أن \(\operatorname{lcm}\) يصبح \(\operatorname{lcm}(\ell,c)\) عندما يكون \(m\ge 1\). لذلك فإن الحالة القديمة \((t,\ell)\) تسهم بالقيمة
$$H_t(\ell)\frac{1}{c^m m!}$$
في الحالة الجديدة \((t+mc,\operatorname{lcm}(\ell,c))\). أما عندما \(m=0\) فالحالة تُنقل كما هي. وتكرار ذلك لكل طول ولكل تعدد ممكن يعيد بدقة الجمع على جميع الأنماط الدورية.
لو احتفظنا بقيمة \(\operatorname{lcm}\) الكاملة كـمفتاح طوال الوقت، فإن عدد الحالات سيكبر بسرعة كبيرة. التحسين الحاسم هو معالجة أطوال الدورات تنازليًا بحسب أكبر عامل أولي لها. ولتكن \(P(c)\) هي أكبر عامل أولي في \(c\).
بعد الانتهاء من جميع الأطوال التي تحقق \(P(c)=p\)، لن يبقى أي طول مستقبلي يقبل القسمة على \(p\). لذلك إذا كان المفتاح الحالي
$$\ell=p^a u,\qquad p\nmid u,$$
فإن الأس \(a\) صار نهائيًا. قد تتغير \(u\) لاحقًا، لكن لا يمكن أن تظهر قوة إضافية للعدد \(p\).
بما أن الناتج النهائي يعتمد على مربع الرتبة، فإن العامل الثابت \(p^a\) يساهم دائمًا بالمضاعف \(p^{2a}\). ولهذا يمكن استبدال المفتاح \(\ell=p^a u\) بالمفتاح \(u\)، مع ضرب الوزن المخزن في \(p^{2a}\).
فإذا كانت مساهمة الحالة الحالية هي \(\ell^2 w\)، فإن
$$\ell^2 w=(p^a u)^2w=u^2\bigl(w\,p^{2a}\bigr).$$
أي أن المجموع النهائي لا يتغير. مثال عملي: بعد إنهاء الكتلة الخاصة بـ \(p=5\)، يمكن تحويل المفتاح \(60=2^2\cdot 3\cdot 5\) إلى المفتاح \(12\)، مع ضرب الوزن في \(25\). هذا الدمج بين الحالات هو ما يجعل الخوارزمية عملية فعلًا.
أنماط الدورات في \(S_3\) هي
$$1+1+1,\qquad 2+1,\qquad 3.$$
وأوزانها الاحتمالية هي
$$\frac{1}{1^3 3!}=\frac{1}{6},\qquad \frac{1}{2^1 1!\,1^1 1!}=\frac{1}{2},\qquad \frac{1}{3^1 1!}=\frac{1}{3},$$
أما رتبها فهي \(1\) و\(2\) و\(3\) على الترتيب. ومن ثم
$$g(3)=1^2\cdot\frac{1}{6}+2^2\cdot\frac{1}{2}+3^2\cdot\frac{1}{3}=\frac{31}{6}.$$
وهذا يطابق أول قيمة تحقق عددية. والبرمجة الديناميكية تصل إلى النتيجة نفسها تلقائيًا: تبدأ من أوزان النقاط الثابتة \(1/t!\)، ثم تضيف دورة بطول 2 أو بطول 3 كلما سمح الطول الكلي بذلك.
بعد معالجة جميع أطوال الدورات حتى \(n\)، تصبح الخريطة الخاصة بالطول الكلي \(n\) حاملةً للتوزيع الموزون الكامل اللازم لحساب المتوسط. وعندها نحسب
$$g(n)=\sum_{\ell}\ell^2 H_n(\ell).$$
ولأن قوى العوامل الأولية المكتملة قد نُقلت مسبقًا إلى الأوزان كتلةً بعد كتلة، تبقى هذه الخطوة النهائية مباشرة.
تبدأ تطبيقات C++ وPython وJava ببناء جدول يحفظ أكبر عامل أولي لكل عدد من \(2\) حتى \(n\). بعد ذلك تُنشأ خريطة-هيستوغرام لكل طول كلي \(0,1,\dots,n\). في البداية تحتوي كل خريطة فقط على مساهمة النقاط الثابتة \(1/t!\) عند المفتاح \(\ell=1\).
ثم تُعالَج الأعداد الأولية ترتيبًا تنازليًا. ولكل \(p\)، تعالج الشيفرة كل طول دورة يكون أكبر عامل أولي له هو \(p\) بالضبط. وعند تثبيت طول \(c\)، تُجرَّب كل القيم \(m\) التي تحقق \(mc\le n\)، ويُطبَّق العامل \(1/(c^m m!)\)، ويزداد الطول الكلي بمقدار \(mc\)، كما يُستبدل كل مفتاح حالي \(\ell\) بـ \(\operatorname{lcm}(\ell,c)\) عندما \(m\ge 1\).
بعد اكتمال كتلة \(p\) كلها، تُمسح جميع الخرائط مرة أخرى. تزال كل قوى \(p\) من كل مفتاح، ويُضرب الوزن في العامل التعويضي \(p^{2a}\)، ثم تُجمَع الحالات التي صارت لها المفاتيح المختصرة نفسها. وتُستخرج النتيجة النهائية من خريطة الطول \(n\)، بينما تؤكد قيم التحقق عند \(n=3\) و\(n=5\) و\(n=20\) صحة الاشتقاق الرياضي.
بناء جدول أكبر عامل أولي يحتاج إلى \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة. أما الجزء المهيمن فهو البرمجة الديناميكية: فلكل طول دورة \(c\)، تمر الشيفرة على جميع التعدادات \(0\le m\le \lfloor n/c\rfloor\)، وعلى جميع الأطوال الكلية الممكنة، وعلى كل مفاتيح \(\operatorname{lcm}\) النشطة داخل الخرائط المعنية.
إذا رمزنا بعدد المفاتيح النشطة عند الطول الكلي \(t\) بالرمز \(M_t\)، فإن طول دورة واحدًا يولد تقريبًا
$$\sum_{m=0}^{\lfloor n/c\rfloor}\sum_{t=0}^{n-mc} M_t$$
عملية تحديث للخرائط. ولا توجد هنا صيغة أسوأ حالة مغلقة أبسط بكثير من هذا الوصف، لأن عدد مفاتيح \(\operatorname{lcm}\) المختلفة يعتمد على مقدار الدمج الذي يحدث بعد كل كتلة أولية. عمليًا، هذا الضغط حسب أكبر عامل أولي هو العامل الحاسم الذي يجعل الزمن والذاكرة ضمن حدود مقبولة.