Project Euler Problem 523

Solution

Answer: 37125450.44

Let $f(n)=E(n)$, the expected number of executions of step $2a$ over all permutations of ${1,\dots,n}$.

The key observation is:

Insert the element $n$ into a random permutation of size $n-1$.
If $n$ is inserted at the end, no new operations are created.
If it is inserted before $k$ elements, then during the sorting process it will eventually generate exactly $2^k-1$ additional moves.

A standard recurrence follows:

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

Since

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

we obtain

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

With $E(1)=0$,

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

This matches the given values:

$$E(4)=3.25, \qquad E(10)=115.725.$$

Now compute $E(30)$.

from decimal import Decimal, getcontext

getcontext().prec = 50

E30 = sum((Decimal(2) ** (k - 1) - 1) / Decimal(k)
          for k in range(1, 31))

print(E30)
print(round(E30, 2))

This gives

$$E(30)=37125450.435701798\ldots$$

Rounded to two decimal places:

Answer: 37125450.44