Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Replace permutations by cycle multiplicities

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.

Step 2: Dynamic programming over used length and current lcm

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.

Step 3: Transition for one cycle length

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.

Step 4: Group cycle lengths by largest prime factor

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\).

Step 5: Absorb the finished prime into the weight

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.

Step 6: Worked example for \(n=3\)

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.

Step 7: Final formula

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=483
2. Permutations and cycle notation: Wikipedia — Permutation
3. Order of a permutation as an lcm of cycle lengths: Wikipedia — Order of a group element
4. Least common multiple: Wikipedia — Least common multiple
5. Prime factorization: Wikipedia — Prime factor