A327791 Number of ways, up to order, of decomposing (Z/nZ)* as the internal direct product of r cyclic subgroups, where r = rank((Z/nZ)*).

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 4, 4, 1, 1, 1, 4, 6, 1, 1, 28, 1, 1, 1, 6, 1, 4, 1, 4, 6, 1, 8, 6, 1, 1, 8, 48, 1, 6, 1, 6, 8, 1, 1, 48, 1, 1, 4, 8, 1, 1, 8, 84, 6, 1, 1, 48, 1, 1, 36, 4, 24, 6, 1, 4, 6, 8, 1, 84, 1, 1, 8, 6, 12, 8, 1, 192, 1, 1, 1, 84, 16, 1, 8, 84, 1, 8

Offset: 1

Author

Jianing Song, Sep 25 2019

Keywords

• nonn

Comments

In general, let G be a finite abelian group and r = rank(G), let s be the number of arrays (k_1, k_2, ..., k_r) such that G = C_(k_1) X C_(k_2) X ... X C_(k_r). We can see from A302257 that:

(a) Given (k'1, k'_2, ..., k'_r) such that G = C(k'1) X C(k'2) X ... X C(k'_r), the number of arrays (a_1, a_2, ..., a_r) such that G = X X ... and that ord(a_i) = k'_i is |Aut(G)|, where is the subgroup of G generated by a. This is because if one group of such (a_1, a_2, ..., a_r) is found, all the others can be found by group automorphism. As a result, the number of sets {a_1, a_2, ..., a_r} such that G = X X ... is |Aut(G)|*s/r!. As (k'_1, k'_2, ..., k'_r) runs through all the s possible choices, each array (a_1, a_2, ..., a_r) such that G = X X ... occurs exactly once, giving a total of |Aut(G)|*s arrays. But the elements in a set are unordered, so the number of sets is |Aut(G)|*s/r!;

(b) Let M = Product_{i=1..r} phi(k_i), then the number of sets {H_1, H_2, ..., H_r} such that G = H_1 X H_2 X ... X H_r is (|Aut(G)|*s/r!)/M. Given {H_1, H_2, ..., H_r} such that G = H_1 X H_2 X ... X H_r, there are phi(|H_i|) ways to choose a generator of H_i, that is, there are Product_{i=1..r} phi(|H_i|) sets {a_1, a_2, ..., a_r} such that = H_i. From (a), the total number of sets {a_1, a_2, ..., a_r} as {H_1, H_2, ..., H_r} runs through all possible choices is |Aut(G)|*s/r!. Note that Product_{i=1..r} phi(|H_i|) is always equal to M regardless of the choice of {H_1, H_2, ..., H_r}. That is to say, each set of cyclic subgroups {H_1, H_2, ..., H_r} corresponds to M sets of generators {a_1, a_2, ..., a_r}. Thus, the number of sets {H_1, H_2, ..., H_r} is (|Aut(G)|*s/r!)/M.

Examples

			n = 8: (Z/8Z)* = {1, 3} X {1, 5} = {1, 3} X {1, 7} = {1, 5} X {1, 7}, so a(8) = 3;
n = 16: (Z/16Z)* = {1, 3, 9, 11} X {1, 7} = {1, 3, 9, 11} X {1, 15} = {1, 5, 9, 13} X {1, 7} = {1, 5, 9, 13} X {1, 15}, so a(16) = 4;
n = 35: (Z/35Z)* = {1, 2, 4, 8, 9, 11, 16, 18, 22, 23, 29, 32} X {1, 6} = {1, 2, 4, 8, 9, 11, 16, 18, 22, 23, 29, 32} X {1, 34} = {1, 3, 4, 9, 11, 12, 13, 16, 17, 27, 29, 33} X {1, 6} = {1, 3, 4, 9, 11, 12, 13, 16, 17, 27, 29, 33} X {1, 34} = {1, 8, 22, 29} X {1, 11, 16, 19, 24, 34} = {1, 8, 22, 29} X {1, 6, 11, 16, 26, 31} = {1, 13, 27, 29} X {1, 11, 16, 19, 24, 34} = {1, 13, 27, 29} X {1, 6, 11, 16, 26, 31}, so a(35) = 8.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000
• Jianing Song, The full PARI program
• The Group Properties Wiki, Internal direct product
• Wikipedia, Multiplicative group of integers modulo n

Crossrefs

Cf. A302257, A327790.

Programs

PARI

a(n) = A302257(n)/A327790(n) \\ See A302257 and A327790 for their programs [See the link section for the full program. - Jianing Song, Mar 08 2021]

Formula

a(n) = A302257(n)/A327790(n).