IBM Ponder This #134 · June 2009

Let π be a permutation on 14 elements. Define Ni as the minimal number of times the permutation π should be applied to get i back into its original place. What is the remainder, modulo 1299, of the sum over all possible 14! permutations of 4 to the power of the product of (2+the parity of Ni)? I.e, what is

$$\left(\sum _{\pi \in S_{14}}{4}^{\prod _{i=1}^{14}(2+(N_{i}mod2))}\right)mod1299$$

Formula typeset from the official statement.

As we will show in the solution, it can be computed almost on the back an envelope.

Update (06/01): Note that a fixed point (i -=> i) is considered odd (Ni=1, parity=1), and a transposition (i -=> j -=> i) is considered even (Ni=2, parity=0).

Solution

Best opened after a real attempt

To be added.