Project Euler 523 - First Sort I

Official link: https://projecteuler.net/problem=523

Thought Process

E(n) can be brute forced for a few small values by just taking all permutations of [1, 2, ..., n] and performing the sorting algorithm and counting the number of times step 2a is performed.

For example if n = 2, we have 2! = 2 permutations

1. [1, 2]

   1. List is sorted, step 2a is applied 0 times

2. [2, 1]

   1. Step 2a is applied once to get sorted list

3. Therefore, E(2) = (0 + 1)/2 = 1/2

After brute forcing the first 10 values we get

1. E(2) = 1/2

2. E(3) = 3/2

3. E(4) = 13/4

4. E(5) = 25/4

5. E(6) = 137/12

6. E(7) = 245/12

7. E(8) = 871/24

8. E(9) = 517/8

9. E(10) = 4629/40

With no apparent pattern, I decided to plug the numerators into OEIS and to my complete surprise I found https://oeis.org/A330718 (The denominators are https://oeis.org/A330719) this directly gives us a closed form for E(n) and the problem is solved, but this was not a very satisfying answer, below I detail how to get the closed form, and it is actually really simple!

I outline the proof below (while leaving a few gaps for the reader to solve)

Interactive Code

Enter an Integer (yourinput)

Code will output E(yourinput)