A226593 Largest period of a recurrence sequence of pairs of permutations of length n.

1, 3, 8, 18, 96, 216, 2112, 9720, 39024, 194256, 1116240

Offset

1,2

Comments

The n! permutations (p) of the numbers 1,2,3..n may be paired (allowing duplication) in n!^2 ways. For a pair of permutations (p, p'), let p'' = p x p', p''' = p' x p'', and so on until the starting pair (p, p') is obtained. If p = p', this iterative process gives the Pisano periods. For most other pairs the periods have different lengths. The sequence gives the longest period that (p, p') generates for any p, p' of length n.

Period is invariant with respect to simultaneous conjugation of both p, p'. - Max Alekseyev, Feb 09 2024

Links

Table of n, a(n) for n=1..11.

Russell Walsmith, An investigation of recursive sequences based on pairs of permutations of length n.

Example

For n = 4: 3142 x 2341 = 1423; 2341 x 1423 = 2134... the sequence thus generated is of period = 18.

Prog

(PARI) period(a, b)=my(n=matsize(a)[2], v=vector(n), aa=vector(n, i, a[i]), bb=vector(n, i, b[i]), id, nsteps); while(id!=n, for(i=1, n, v[i]=a[b[i]]); id=sum(i=1, n, b[i]==aa[i] && v[i]==bb[i]); for(i=1, n, a[i]=b[i]; b[i]=v[i]); nsteps++); nsteps
a(n)=my(a, b, m, p); for(k=1, n!, a=numtoperm(n, k); for(l=1, n!, b=numtoperm(n, l); p=period(a, b); if(p>m, m=p))); m \\ Ralf Stephan, Aug 13 2013

Crossrefs

Cf. A001175 (Pisano periods: period of Fibonacci numbers (A000045) mod n).

Cf. A106291 (period of the Lucas sequence (A000032) mod n).

Sequence in context: A307397 A032100 A340729 * A023371 A358984 A124086

Adjacent sequences: A226590 A226591 A226592 * A226594 A226595 A226596

Keyword

nonn,hard,more

Author

Russell Walsmith, Jun 13 2013

Extensions

a(6) from Ralf Stephan, Aug 13 2013

Edited and a(7)-a(11) added by Max Alekseyev, Feb 13 2024

Status

approved