login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 30 02:42 EST 2020. Contains 338781 sequences. (Running on oeis4.)