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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A316089 Number of ordered (k_1, k_2, ..., k_r) such that (Z/nZ)* is isomorphic to C_{k_1} X C_{k_2} X ... X C_{k_r}. Here (Z/nZ)* is the multiplicative group of integers modulo n, r = rank((Z/nZ)*). 3
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 4, 2, 1, 1, 4, 3, 1, 2, 1, 2, 4, 1, 1, 3, 1, 1, 2, 4, 1, 1, 4, 3, 2, 1, 1, 3, 1, 1, 1, 2, 2, 2, 1, 2, 2, 4, 1, 3, 1, 1, 4, 2, 4, 4, 1, 3, 1, 1, 1, 3, 2, 1, 4 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,15

COMMENTS

The rank of a finitely generated group rank(G) is defined as the size of the minimal generating sets (the generating sets with the least elements) of G. By convention a(1) = a(2) = 1, since the multiplicative group of integers modulo 1 or 2 has rank 0, and the empty direct product yields the trivial group.

This sequence is related to the number of minimal generating sets {x_1, x_2, ..., x_r} of (Z/nZ)* such that Product_{i=1..r} x_i^e_i == 1 (mod n) implies that x_i^e_i == 1 (mod n) for 1 <= i <= r. See A302257.

For n >= 3, also the number of ordered (k_1, k_2, ..., k_r) such that (Z/nZ)* is isomorphic to C_{k_1} X C_{k_2} X ... X C_{k_r} and gcd(k_1, k_2, ..., k_r) > 1.

a(n) = 1 iff there exists an integer m such that (Z/nZ)* = (C_m)^r, that is, n is a term in A033948 or A305236 or n = 24.

First occurrence of k, or -1 if k never occurs: 1, 15, 40, 35, -1, 160, -1, 143, 104, -1, -1, 480, -1, -1, -1, ... It's easy to show that prime number >= 5 never occurs.

In general, let (Z/nZ)* = C_(Product_{j=1..k} p_j^e_1j) X C_(Product_{j=1..k} p_j^e_2j) X ... X C_(Product_{j=1..k} p_j^e_rj) where p_1, p_2, ..., p_k are different primes, 0 <= e_1j <= e_2j <= ... <= e_rj for 1 <= j <= k (for n = 1 or 2, (Z/nZ)* is the trivial group, thus r = k = 0), then a(n) is the number of matrices C = (c_ij) such that (c_1j, c_2j, ..., c_rj) is a permutation of (e_1j, e_2j, ..., e_rj) for 1 <= j <= k. - Jianing Song, Feb 04 2019

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Wikipedia, Multiplicative group of integers modulo n

FORMULA

Let (Z/nZ)* = C_(Product_{j=1..k} p_j^e_1j) X C_(Product_{j=1..k} p_j^e_2j) X ... X C_(Product_{j=1..k} p_j^e_rj) where p_1, p_2, ..., p_k are different primes, 0 <= e_1j <= e_2j <= ... <= e_rj for 1 <= j <= k. Define b_ij = max{1 <= t <= r | e_tj = e_ij} - min{1 <= t <= r | e_tj = e_ij} + 1, then a(n) = (r!)^k/Product_{i=1..r, j=1..k} (b_ij)!^(1/b_ij).

EXAMPLE

For n = 35, rank((Z/35Z)*) = 2, and (Z/35Z)* = C_2 X C_12 = C_12 X C_2 = C_4 X C_6 = C_6 X C_4, so a(35) = 4. Also, (Z/35Z)* = C_(2^1*3^0) X C_(2^2*3^1), e_11 = 1, e_12 = 0, e_21 = 2, e_22 = 1, so b_11 = b_12 = b_21 = b_22 = 1, then a(35) = (2!)^2 = 4.

For n = 105, rank((Z/105Z)*) = 3, and (Z/105Z)* = C_2 X C_2 X C_12 (along with its two permutations) = C_2 X C_4 X C_6 (along with its five permutations), so a(105) = 9. Also, (Z/35Z)* = C_(2^1*3^0) X C_(2^1*3^0) X C_(2^2*3^1), e_11 = 1, e_12 = 0, e_21 = 1, e_22 = 0, e_31 = 2, e_32 = 1, so b_11 = b_12 = b_21 = b_22 = 2, b_31 = b_32 = 1, then a(105) = (3!)^2/(2!*2!) = 9.

PROG

(PARI)

zp(g)={sum(i=1, #g, my(f=factor(g[i])); sum(j=1, #f~, x^f[j, 1]*(y^f[j, 2]-1)))}

a(n)={my(g=znstar(n).cyc); my(p=zp(g), r=#g); prod(i=1, poldegree(p), my(u=Vec(r + polcoeff(p, i))); r!/prod(j=1, #u, u[j]!))} \\ Andrew Howroyd, Jun 30 2018

CROSSREFS

Cf. A033948, A302257, A305236.

Sequence in context: A052494 A317756 A039998 * A000999 A175921 A303828

Adjacent sequences:  A316086 A316087 A316088 * A316090 A316091 A316092

KEYWORD

nonn

AUTHOR

Jianing Song, Jun 27 2018

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 September 22 20:09 EDT 2020. Contains 337291 sequences. (Running on oeis4.)