The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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)*). 2
 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 = 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. 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 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 [See the link section for the full program. - Jianing Song, Mar 08 2021] 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 7 12:43 EST 2023. Contains 360120 sequences. (Running on oeis4.)