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

Author

Russell Walsmith, Jun 13 2013

Keywords

• nonn
• hard
• more

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

Examples

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

Links

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

Crossrefs

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

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

Programs

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

Extensions

a(6) from Ralf Stephan, Aug 13 2013

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