A000793 -id:A000793 - cp's OEIS frontend

A226142 The smallest positive integer k such that the symmetric group S_n is a product of k cyclic groups.

1, 1, 2, 3, 3, 4, 4

Offset: 1

W. Edwin Clark, May 27 2013

Since S_{n+1} is a product of a subgroup isomorphic to S_n and the cyclic group <(1,2,3,...,n+1)> we have a(n+1) <= a(n) + 1. On the other hand it is not clear that a(n) <= a(n+1) for all n. A lower bound is given by A226143(n) = ceiling(log(m)(n!)), m = A000793(n), a sequence that is not nondecreasing.
This sequence was suggested by a posting of L. Edson Jeffery on the seqfans mailing list on May 24, 2013.
Cardinality of the smallest subset(s) X of S_n such that every permutation in S_n can be expressed as a product of some elements in X. - Joerg Arndt, Dec 13 2015

			a(7) = 4 since a factorization of S_7 is given by C_1*C_2*C_3*C_4 where
C_1 = <(1,2,3,4)(5,6,7)>,
C_2 = <(1,4,6)(2,3,5,7)>,
C_3 = <(1,2,5,7)(3,4,6)>,
C_4 = <(1,3,5,6,7)(2,4)>,
and a brute force computation shows that S_7 is not a product of 3 or fewer cyclic subgroups.

Miklós Abért, Symmetric groups as products of Abelian subgroups, Bull. Lond. Math. Soc., Volume 34, Issue 04, July 2002, pp. 451-456.

Cf. A051625, A225788.

A256443 Irregular triangle T(n,k) read by rows: row n gives a smallest partition of n with maximal order (see Comments for precise definition).

Original entry on oeis.org

1, 2, 3, 4, 2, 3, 6, 3, 4, 3, 5, 4, 5, 2, 3, 5, 5, 6, 3, 4, 5, 1, 3, 4, 5, 3, 4, 7, 3, 5, 7, 4, 5, 7, 2, 3, 5, 7, 5, 6, 7, 3, 4, 5, 7, 1, 3, 4, 5, 7, 2, 3, 4, 5, 7, 4, 5, 6, 7, 3, 5, 7, 8, 1, 3, 5, 7, 8, 4, 5, 7, 9, 1, 4, 5, 7, 9, 4, 5, 7, 11, 2, 3, 5, 7, 11

Offset: 1

Bob Selcoe, Mar 29 2015

Consider all partitions of n for which the LCM of the parts is A000793(n) (A000793 is Landau's function g(n), the largest order of a permutation of n elements). Minimize the number of parts. Then take the lexicographically earliest solution. This is row n of the triangle. See A256445 for a partition with the most elements.

			Triangle starts T(1,1) = 1:
1:  1
2:  2
3:  3
4:  4
5:  2,3
6:  6
7:  3,4
8:  3,5
9:  4,5
10: 2,3,5
11: 5,6
12: 3,4,5
13: 1,3,4,5
14: 3,4,7
15: 3,5,7
16: 4,5,7
17: 2,3,5,7
18: 5,6,7
19: 3,4,5,7
20: 1,3,4,5,7
21: 2,3,4,5,7
22: 4,5,6,7
23: 3,5,7,8
T(11,k) = [5,6] rather than [1,2,3,5] because [5,6] has fewer elements.

Cf. A000793, A074064, A256445.

More terms from Alois P. Heinz, Apr 01 2015

A256445 Irregular triangle T(n,k) read by rows: row n gives a largest partition of n with maximal order (see Comments for precise definition).

Original entry on oeis.org

1, 2, 3, 4, 2, 3, 1, 2, 3, 3, 4, 3, 5, 4, 5, 2, 3, 5, 1, 2, 3, 5, 3, 4, 5, 1, 3, 4, 5, 3, 4, 7, 3, 5, 7, 4, 5, 7, 2, 3, 5, 7, 1, 2, 3, 5, 7, 3, 4, 5, 7, 1, 3, 4, 5, 7, 1, 1, 3, 4, 5, 7, 1, 1, 1, 3, 4, 5, 7, 3, 5, 7, 8, 1, 3, 5, 7, 8, 4, 5, 7, 9, 1, 4, 5, 7, 9

Offset: 1

Bob Selcoe, Mar 29 2015

Consider all partitions of n for which the LCM of the parts is A000793(n) (A000793 is Landau's function g(n), the largest order of a permutation of n elements). Maximize the number of parts. Then take the lexicographically earliest solution. This is row n of the triangle. See A256443 for a partition with the fewest elements.

			Triangle starts T(1,1) = 1:
1:  1
2:  2
3:  3
4:  4
5:  2,3
6:  1,2,3
7:  3,4
8;  3,5
9:  4,5
10: 2,3,5
11: 1,2,3,5
12: 3,4,5
13: 1,3,4,5
14: 3,4,7
15: 3,5,7
16: 4,5,7
17: 2,3,5,7
18: 1,2,3,5,7
19: 3,4,5,7
20: 1,3,4,5,7
21: 1,1,3,4,5,7
22: 1,1,1,3,4,5,7
23: 3,5,7,8
T(11,k) = [1,2,3,5] rather than [5,6] because [1,2,3,5] has more elements.

Cf. A000793, A074064, A256443.

More terms from Alois P. Heinz, Apr 01 2015

A319054 Maximum product of an aperiodic integer partition of n.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 18, 24, 36, 54, 72, 108, 162, 216, 324, 486, 648, 972, 1458, 1944, 2916, 4374, 5832, 8748, 13122, 17496, 26244, 39366, 52488, 78732, 118098, 157464, 236196, 354294, 472392, 708588, 1062882, 1417176, 2125764, 3188646, 4251528, 6377292

Offset: 1

Gus Wiseman, Sep 09 2018

nonn

An integer partition is aperiodic if its multiplicities are relatively prime.

			Among the aperiodic partitions of 9, those with maximum product are (432) and (3222), so a(9) = 24. If periodic partitions were allowed, we would have (333) with product 27.

Cf. A000740, A000792, A000793, A000837, A007916, A100953, A281116, A289508, A289509, A296302.

Table[Max[Times@@@Select[IntegerPartitions[n],GCD@@Length/@Split[#]==1&]],{n,30}]

A355572 Largest LCM of partitions of n into odd parts.

Original entry on oeis.org

1, 1, 3, 3, 5, 5, 7, 15, 15, 21, 21, 35, 35, 45, 105, 105, 105, 105, 165, 165, 315, 315, 385, 385, 495, 1155, 1155, 1365, 1365, 1365, 1365, 3465, 3465, 4095, 4095, 5005, 5005, 6435, 15015, 15015, 15015, 15015, 19635, 19635, 45045, 45045, 45045, 45045, 58905, 58905, 69615, 69615

Offset: 1

Torsten Muetze, Jul 07 2022

nonn

The largest LCM is attained for a partition of n into powers of distinct odd primes and 1's.

			The partitions of n=8 into odd parts are 7+1, 5+3, 5+1+1+1, 3+3+1+1, 3+1+1+1+1+1, 1+1+1+1+1+1+1+1, and the partition with largest LCM among those is 5+3, which has LCM(5,3)=5*3=15, so a(8)=15.

Petr Gregor, Arturo Merino, and Torsten Mütze, The Hamilton compression of highly symmetric graphs, arXiv preprint arXiv:2205.08126 [math.CO], 2022.

Cf. A000793, A051593, A355573, A159685.

a(n) = my(x=1); forpart(p=n, if (!#select(x->((x%2)==0), Vec(p)), x = max(x, lcm(Vec(p))))); x; \\ Michel Marcus, Jul 08 2022

A355573 Largest LCM of partitions of n with a nonzero even number of even parts.

Original entry on oeis.org

2, 2, 4, 6, 6, 12, 12, 20, 30, 30, 60, 60, 84, 84, 140, 210, 210, 420, 420, 420, 420, 840, 840, 1260, 1260, 1540, 2310, 2520, 4620, 4620, 5460, 5460, 9240, 9240, 13860, 13860, 16380, 16380, 27720, 30030, 32760, 60060, 60060, 60060, 60060, 120120, 120120, 180180, 180180, 180180, 180180

Offset: 4

Torsten Muetze, Jul 07 2022

nonn

The largest LCM is attained for a partition of n into powers of distinct odd primes, 2^k for some k>0, 2, and 1's.

			The partitions of n=8 with a nonzero even number of even parts are 6+2, 4+4, 4+2+1+1, 3+2+2+1, 2+2+2+2, 2+2+1+1+1+1, and the partition with largest LCM among those is 3+2+2+1, which has LCM(3,2,2,1)=3*2=6, so a(8)=6.

Petr Gregor, Arturo Merino, and Torsten Mütze, The Hamilton compression of highly symmetric graphs, arXiv preprint arXiv:2205.08126 [math.CO], 2022.

Cf. A000793, A051593, A355572, A159685.

A112409 Table read by rows: for each n: the orders of the permutations of n elements, excluding those that are a divisor of the order of another permutation of n elements.

Original entry on oeis.org

1, 2, 2, 3, 3, 4, 4, 5, 6, 4, 5, 6, 7, 10, 12, 8, 10, 12, 15, 8, 9, 12, 14, 15, 20, 8, 9, 12, 14, 20, 21, 30

Offset: 1

Allen Tracht (atracht(AT)ix.netcom.com), Dec 08 2005

			1: 1, 2: 2, 3: 2 3, 4: 3 4, 5: 4 5 6, 6: 4 5 6, 7: 7 10 12...
Permutations of 7 elements have orders of 1, 2, 3, 4, 5, 6, 7, 10, 12, of which 7, 10 and 12 are not factors of any others.

Cf. A000793.

A157656 Maximal possible number of states in a minimal deterministic automaton, equivalent to an n-state nondeterministic automaton over 1-symbol alphabet.

Original entry on oeis.org

2, 3, 6, 11, 18, 27

Offset: 1

Max Alekseyev, Mar 03 2009

Alternative definition: consider a labyrinth consisting of n rooms, one designated as the "start room", connected by a number of one-way corridors. Let R(k) be a set of all rooms that can be reached from the start room after passing through exactly k corridors. We need to construct a labyrinth with the maximal number of distinct R(k), i.e., a set { R(0), R(1), R(2), ... } (that is actually a finite set) must be of the largest possible size. This size is a(n).
For small n, a(n)=A059100(n-1) which corresponds to a labyrinth 1 -> 2 -> 3 -> ... -> n -> 1, n -> 2 with the start room "1".
For large n, a(n) is different from A059100(n-1). In particular, for n=29, there is a labyrinth of the following shape: there are five directed corridors from the start room to five other rooms that belong to disjoint directed cycles of length 2, 3, 5, 7, and 11 respectively (note that 29 = 1+2+3+5+7+11). It gives 1+2*3*5*7*11=2311 distinct R(k)'s, implying that a(29)>=2311>A059100(28).
Conjecture: a(n)=A059100(n-1) holds only for all n<20 as well as n=22 and n=23. (Rustem Aidagulov)
In general, a(n) >= A000793(n-1)+1. The strategy is to partition n-1 into coprime numbers with maximum product and create a cycle for each, then add one more starting node which is connected to all cycles. This also implies that a(n) is Omega(e^sqrt(n log n)). - Martín Muñoz, Dec 10 2023

Author?, Discussion of the problem (in Russian)

Cf. A059100, A000793.

A174554 Smallest k > 2 such that 2|k, 3|k+1, 4|k+2,..., n|k+n-2.

Original entry on oeis.org

4, 8, 14, 62, 62, 422, 842, 2522, 2522, 27722, 27722, 360362, 360362, 360362, 720722, 12252242, 12252242, 232792562, 232792562, 232792562, 232792562, 5354228882, 5354228882, 26771144402, 26771144402, 80313433202, 80313433202

Offset: 2

Michel Lagneau, Mar 22 2010

nonn

We solve the system of n+1 equations : k==2 (mod 2), k==2 (mod 3),...,k==2 (mod n), and then the solutions are k== 2 mod (lcm(2,3,4,...,n)) where lcm(k) is the least common multiple of{1, 2, ..., k}(A003418) .

			a(2) = 4 because 2|4;
a(3) = 8 because 2|8 and 3|9;
a(4) = 14 because 2|14, 3|15 and 4|16;
a(5) = 62 because 2|62, 3|63, 4|64 and 5|65;
a(6) = 62 because 2|62, 3|63, 4|64, 5|65 and 6|66.

Bakir Farhi, An identity involving the least common multiple of binomial coefficients and its application, arXiv:0906.2295 [math.NT], 2009.
Bakir Farhi, An identity involving the least common multiple of binomial coefficients and its application, Amer. Math. Monthly, 116 (2009), 836-839.
Eric Weisstein's World of Mathematics, Least Common Multiple

Cf. A002944, A003990, A051173, A000793, A003418, A048691.

with(numtheory):q:=2:for k from 2 to 100 do :q1:= lcm(q,k):q2 :=2+q1 :print(q2): q :=q1 :od :

a(n) = 2 + lcm(2,3,4,...,n) = A003418(n) + 2.

A358070 Largest order of element in direct product S_n * S_n where S_n is the symmetric group.

Original entry on oeis.org

1, 1, 2, 6, 12, 30, 30, 84, 120, 210, 420, 420, 840, 1260, 2310, 4620, 5460, 5460, 13860, 13860, 27720, 32760, 60060, 60060, 120120, 180180, 180180, 360360, 360360, 510510, 1021020, 1141140, 2042040, 3063060, 3423420, 6126120, 6846840, 6846840, 8953560, 12252240

Offset: 0

Jack Zhang, Oct 29 2022

nonn

Let (P,Q) be two partitions of n and lcm(P) be the LCM of all parts of P, then a(n) = max( lcm(lcm(P), lcm(Q)) ) where the maximum is taken among all pairs (P,Q). - Joerg Arndt, Dec 04 2022

			From _Joerg Arndt_, Dec 04 2022: (Start)
The 15 partitions of 7 are the following:
[ #]  [ partition ]   lcm( parts )
[ 1]  [ 1 1 1 1 1 1 1 ]   1
[ 2]  [ 1 1 1 1 1 2 ]   2
[ 3]  [ 1 1 1 1 3 ]   3
[ 4]  [ 1 1 1 2 2 ]   2
[ 5]  [ 1 1 1 4 ]   4
[ 6]  [ 1 1 2 3 ]   6
[ 7]  [ 1 1 5 ]   5
[ 8]  [ 1 2 2 2 ]   2
[ 9]  [ 1 2 4 ]   4
[10]  [ 1 3 3 ]   3
[11]  [ 1 6 ]   6
[12]  [ 2 2 3 ]   6
[13]  [ 2 5 ]  10
[14]  [ 3 4 ]  12
[15]  [ 7 ]   7
The maximum value attained is 7 * 12, so a(7) = 84.
(End)

Cf. A000793 (largest order of element in S_n).

Cf. A063183.

x=[{1},{1}]
for i in range(2,40):
    u=[]
    for j in range(1,i):
        u.extend([k*j//math.gcd(k,j) for k in x[i-j]])
    x.append(set(u))
xx=[set([i*j//math.gcd(i,j) for i in t for j in t]) for t in x]
print([max(i) for i in xx][2:])

cp's OEIS Frontend

A226142 The smallest positive integer k such that the symmetric group S_n is a product of k cyclic groups.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A256443 Irregular triangle T(n,k) read by rows: row n gives a smallest partition of n with maximal order (see Comments for precise definition).

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A256445 Irregular triangle T(n,k) read by rows: row n gives a largest partition of n with maximal order (see Comments for precise definition).

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A319054 Maximum product of an aperiodic integer partition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A355572 Largest LCM of partitions of n into odd parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A355573 Largest LCM of partitions of n with a nonzero even number of even parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A112409 Table read by rows: for each n: the orders of the permutations of n elements, excluding those that are a divisor of the order of another permutation of n elements.

Views

Author

Keywords

Examples

Crossrefs

A157656 Maximal possible number of states in a minimal deterministic automaton, equivalent to an n-state nondeterministic automaton over 1-symbol alphabet.

Views

Author

Keywords

Comments

Links

Crossrefs

A174554 Smallest k > 2 such that 2|k, 3|k+1, 4|k+2,..., n|k+n-2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A358070 Largest order of element in direct product S_n * S_n where S_n is the symmetric group.

Views

Author

Keywords