|
%I #34 Feb 14 2019 16:11:48
%S 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,
%T 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,
%U 2,4,1,3,1,1,4,2,4,4,1,3,1,1,1,3,2,1,4
%N 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)*).
%C 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.
%C 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.
%C 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.
%C 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.
%C 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.
%C 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
%H Andrew Howroyd, <a href="/A316089/b316089.txt">Table of n, a(n) for n = 1..10000</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>
%F 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).
%e 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.
%e 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.
%o (PARI)
%o zp(g)={sum(i=1, #g, my(f=factor(g[i])); sum(j=1, #f~, x^f[j,1]*(y^f[j,2]-1)))}
%o 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
%Y Cf. A033948, A302257, A305236.
%K nonn
%O 1,15
%A _Jianing Song_, Jun 27 2018
|
