A289625 a(n) = prime factorization encoding of the structure of the multiplicative group of integers modulo n.

1, 1, 4, 4, 16, 4, 64, 36, 64, 16, 1024, 36, 4096, 64, 144, 144, 65536, 64, 262144, 144, 576, 1024, 4194304, 900, 1048576, 4096, 262144, 576, 268435456, 144, 1073741824, 2304, 9216, 65536, 36864, 576, 68719476736, 262144, 36864, 3600, 1099511627776, 576, 4398046511104, 9216, 36864, 4194304, 70368744177664, 3600, 4398046511104, 1048576, 589824, 36864

Offset: 1

Author

Antti Karttunen, Jul 17 2017

Keywords

• nonn

Comments

Here multiplicative group of integers modulo n is decomposed as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i > j, like PARI-function znstar does. a(n) is then 2^{k_1} * 3^{k_2} * 5^{k_3} * ... * prime(m)^{k_m}.

Examples

			For n=5, the multiplicative group modulo 5 is isomorphic to C_4, which does not factorize to smaller subgroups, thus a(5) = 2^4 = 16.
For n=8, the multiplicative group modulo 8 is isomorphic to C_2 x C_2, thus a(8) = 2^2 * 3^2 = 36.
For n=15, the multiplicative group modulo 15 is isomorphic to C_4 x C_2, thus a(15) = 2^4 * 3^2 = 144.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..1024
• The PARI group, Catalogue of GP/PARI Functions: Arithmetic functions, function znstar
• Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
• Wikipedia, Multiplicative group of integers modulo n

Crossrefs

Cf. A000010, A002322, A046072.

Cf. A033948 (positions of terms that are powers of 2).

Cf. A289626 (rgs-transform of this sequence).

Programs

PARI

A289625(n) = { my(m=1,p=2,v=znstar(n)[2]); for(i=1,length(v),m *= p^v[i]; p = nextprime(p+1)); (m); };

Formula

A005361(a(n)) = A000010(n).

A072411(a(n)) = A002322(n).

A007814(a(n)) = A002322(n) for n > 2.

A001221(a(n)) = A046072(n) for n > 2.