← Complete problem index

PROJECT EULER · #0902

Permutation Powers

Statement only · UnsolvedOriginal problem ↗

A permutation π of {1,,n} can be represented in one-line notation as π(1),,π(n). If all n! permutations are written in lexicographic order then rank(π) is the position of π in this 1-based list.

For example, rank(2,1,3)=3 because the six permutations of {1,2,3} in lexicographic order are: 1,2,31,3,22,1,32,3,13,1,23,2,1

For a positive integer m, we define the following permutation of {1,,n} with n=m(m+1)2: σ(i)={k(k1)2+1if i=k(k+1)2 for k{1,,m};i+1otherwise;τ(i)=((109+7)imodn)+1π(i)=τ1(σ(τ(i))) where τ1 is the inverse permutation of τ.

Define P(m)=k=1m!rank(πk), where πk is the permutation arising from applying π k times.
For example, P(2)=4, P(3)=780 and P(4)=38810300.

Find P(100). Give your answer modulo (109+7).

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.