login
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
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
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
KEYWORD
nonn
AUTHOR
Jianing Song, Jun 27 2018
STATUS
approved