

A327791


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,8


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 = <a_1> X <a_2> X ... <a_r> and that ord(a_i) = k'_i is Aut(G), where <a> 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 = <a_1> X <a_2> X ... <a_r> 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 = <a_1> X <a_2> X ... <a_r> 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 <a_i> = 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.


LINKS

Table of n, a(n) for n=1..90.
Wikipedia, Multiplicative group of integers modulo n


FORMULA

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


EXAMPLE

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.


PROG

(PARI) a(n) = A302257(n)/A327790(n) \\ See A302257 and A327790 for their programs


CROSSREFS

Cf. A302257, A327790.
Sequence in context: A260626 A155828 A226203 * A051997 A155744 A086869
Adjacent sequences: A327788 A327789 A327790 * A327792 A327793 A327794


KEYWORD

nonn


AUTHOR

Jianing Song, Sep 25 2019


STATUS

approved



