Project Euler 523 - First Sort I

Official link:

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

After brute forcing the first 10 values we get

With no apparent pattern, I decided to plug the numerators into OEIS and to my complete surprise I found (The denominators are 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)