A333468 Length of the largest disjoint cycle of the permutation that results from the composition of first n circular shifts.

1, 2, 2, 3, 5, 6, 3, 4, 9, 4, 7, 10, 9, 14, 4, 5, 7, 18, 8, 10, 7, 7, 14, 11, 6, 26, 12, 9, 29, 30, 5, 6, 33, 11, 21, 6, 11, 15, 22, 27, 41, 6, 17, 8, 8, 7, 22, 24, 15, 50, 28, 8, 53, 18, 22, 14, 25, 9, 15, 55, 14, 50, 6, 7, 65, 11, 19, 34, 69, 23, 35, 14, 22, 74, 10

Offset: 1

Author

Richard Locke Peterson, Mar 22 2020

Keywords

• nonn

Comments

Size of the largest part of the partition of n that is associated with the cycle structure of the permutation given by the permutation product (1)*(1,2)*(1,2,3)*...*(1,2,3,...n) after the product is rewritten as the product of disjoint cycles, where * means functional composition, and the permutations are written in cycle form.

Also see Circular shift on Wikipedia.

For n>1, a(n) is always greater than 1, since the given product can never be the identity permutation on the set {1,2,...,n}, which is the only permutation associated with the partition <1,1,...,1> (1 repeated n times).

Connections: The image of 1 in each resulting permutation appears to be the same as the numbers in A003602. The number of parts in the partition associated with each resulting permutation appear to match the numbers in A006694.

The LCM of all cycle lengths gives A051732(n+1). - Alois P. Heinz, Apr 08 2020

Examples

			For n=3, the permutation (1)*(1,2)*(1,2,3)=(1)*(2,3), which is associated with the partition <2,1> of 3. The size of the largest part is 2, so a(3)=2.
For n=11, the permutation (1)*(1,2)*..*(1,2,..11)=(1,2,7,5)*(3,4,8,10,11,6,9) when rewritten as the product of disjoint cycles, which is associated with the partition <7,4> of 11. The size of the largest part is 7, so a(11)=7.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..3000
• Wikipedia, Circular shift

Crossrefs

Cf. A003602, A006694, A051732, A071642, A163782.

Programs

PARI

Follow(s, f)={my(t=f(s), k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
mkp(n)={my(v=vector(n,i,i)); for(k=1, n, my(t=v[1]); for(i=1, k-1, v[i]=v[i+1]); v[k]=t); v}
a(n)={my(v=mkp(n), m=0); for(i=1, n, m=max(m, Follow(i, j->v[j]))); m} \\ Andrew Howroyd, Mar 27 2020

Formula

a(n) = n <=> n in { A163782 } union { 1 }. - Alois P. Heinz, Apr 08 2020

Extensions

Terms a(20) and beyond from Andrew Howroyd, Mar 27 2020