Detailed mathematical approach

Problem Summary

Start with a random permutation of \(\{1,2,\dots,n\}\). One first-sort move finds the first entry that is smaller than the entry immediately to its left and moves that entry to the front. If \(E(n)\) denotes the expected number of moves needed to reach the increasing permutation, the task is to evaluate \(E(30)\) exactly and then print the result rounded to two decimal places.

The solution does not simulate permutations. Instead, it uses an exact recurrence for \(E(n)\), turns that recurrence into a linear-time dynamic program, and keeps every intermediate value as an exact rational number.

Mathematical Approach

The C++, Python, and Java implementations all rely on the same expectation recurrence. Once that identity is available, the rest of the work is careful bookkeeping: prefix sums for speed and a common denominator for exact arithmetic.

Step 1: Write the recurrence for the expectation

Let \(E(0)=0\). The first-sort analysis used by the implementations gives the averaged form

$E(n)=\frac{1}{n}\sum_{k=0}^{n-1}\left(E(k)+2^k-1\right),\qquad n\ge 1.$

Summing the geometric correction term yields

$\sum_{k=0}^{n-1}(2^k-1)=\left(\sum_{k=0}^{n-1}2^k\right)-n=2^n-n-1,$

so the same recurrence can be written more compactly as

$E(n)=\frac{\sum_{k=0}^{n-1}E(k)+(2^n-n-1)}{n}.$

This identity is the mathematical core of the entire solution.

Step 2: Replace the long sum by a prefix sum

Define

$P(n)=\sum_{k=0}^{n}E(k).$

Then the recurrence becomes

$E(n)=\frac{P(n-1)+(2^n-n-1)}{n},$

followed by the update

$P(n)=P(n-1)+E(n).$

So once \(P(n-1)\) is known, the next expectation is obtained in constant time. This is why the implementations only need a single forward sweep from \(1\) to \(30\).

Step 3: Derive an equivalent first-difference formula

The recurrence also has a useful telescoping form. From

$nE(n)=P(n-1)+2^n-n-1$

and

$(n-1)E(n-1)=P(n-2)+2^{n-1}-n,$

together with \(P(n-1)=P(n-2)+E(n-1)\), we obtain

$nE(n)-nE(n-1)=2^{n-1}-1.$

Therefore

$E(n)=E(n-1)+\frac{2^{n-1}-1}{n}.$

Summing these increments from \(1\) to \(n\) gives the closed form

$E(n)=\sum_{j=1}^{n}\frac{2^{j-1}-1}{j}.$

This form makes the denominator structure completely transparent: every term has denominator dividing \(j\).

Step 4: Use one common denominator for exact arithmetic

Let

$D=\operatorname{lcm}(1,2,\dots,N),\qquad N=30.$

Because the closed form is a sum of terms with denominators \(1,2,\dots,n\), every value \(E(n)\) has denominator dividing \(D\). Hence we may store

$A(n)=D\,E(n)$

as an integer for every \(n\le N\). Multiplying the recurrence by \(D\) gives

$A(n)=\frac{\sum_{k=0}^{n-1}A(k)+D(2^n-n-1)}{n}.$

The numerator here is exactly \(nD\,E(n)\), so the division by \(n\) is exact. This removes all floating-point error from the computation.

Step 5: Worked example

The first few values come out immediately:

$E(1)=\frac{E(0)+(2^1-1-1)}{1}=0,$

$E(2)=\frac{E(0)+E(1)+(2^2-2-1)}{2}=\frac{1}{2},$

$E(3)=\frac{E(0)+E(1)+E(2)+(2^3-3-1)}{3}=\frac{\frac{1}{2}+4}{3}=\frac{3}{2},$

$E(4)=\frac{E(0)+E(1)+E(2)+E(3)+(2^4-4-1)}{4}=\frac{0+0+\frac{1}{2}+\frac{3}{2}+11}{4}=\frac{13}{4}.$

This reproduces the checkpoint \(E(4)=13/4\). Continuing the same process gives the second checkpoint

$E(10)=\frac{4629}{40}.$

How the Code Works

The implementations first build the common denominator \(D=\operatorname{lcm}(1,2,\dots,30)\) by repeated gcd/lcm updates. They then store the exact scaled expectations \(A(n)=D\,E(n)\) in an array and maintain the running prefix sum \(\sum_{k=0}^{n-1}A(k)\).

For each \(n=1,2,\dots,30\), the implementation computes the correction term \(2^n-n-1\), combines it with the scaled prefix sum, and divides by \(n\) to obtain the next exact scaled expectation. The same recurrence is used in C++, Python, and Java; only the integer machinery differs.

After the table is built, the known values \(E(4)=13/4\) and \(E(10)=4629/40\) serve as checkpoints. The final step multiplies \(E(30)\) by \(100\), performs one exact half-up rounding by comparing the remainder with \(D/2\), and prints the decimal result with exactly two digits after the decimal point.

Complexity Analysis

The dynamic program performs one pass from \(1\) to \(N\), so the recurrence evaluation is \(O(N)\) arithmetic steps. Constructing the common denominator requires \(N\) gcd/lcm updates. The implementations store the table of scaled expectations, so the memory usage is \(O(N)\), although the recurrence itself only needs a running prefix sum. For the actual target \(N=30\), all of this is tiny.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=523
2. Expected value: Wikipedia - Expected value
3. Recurrence relation: Wikipedia - Recurrence relation
4. Least common multiple: Wikipedia - Least common multiple