cp's OEIS Frontend

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

%I A289625 #21 Feb 16 2025 08:33:48
%S A289625 1,1,4,4,16,4,64,36,64,16,1024,36,4096,64,144,144,65536,64,262144,144,
%T A289625 576,1024,4194304,900,1048576,4096,262144,576,268435456,144,
%U A289625 1073741824,2304,9216,65536,36864,576,68719476736,262144,36864,3600,1099511627776,576,4398046511104,9216,36864,4194304,70368744177664,3600,4398046511104,1048576,589824,36864
%N A289625 a(n) = prime factorization encoding of the structure of the multiplicative group of integers modulo n.
%C A289625 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}.
%H A289625 Antti Karttunen, <a href="/A289625/b289625.txt">Table of n, a(n) for n = 1..1024</a>
%H A289625 The PARI group, <a href="https://pari.math.u-bordeaux.fr/dochtml/html-stable/Arithmetic_functions.html#znstar">Catalogue of GP/PARI Functions: Arithmetic functions, function znstar</a>
%H A289625 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ModuloMultiplicationGroup.html">Modulo Multiplication Group.</a>
%H A289625 Wikipedia, <a href="https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>
%F A289625 A005361(a(n)) = A000010(n).
%F A289625 A072411(a(n)) = A002322(n).
%F A289625 A007814(a(n)) = A002322(n) for n > 2.
%F A289625 A001221(a(n)) = A046072(n) for n > 2.
%e A289625 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.
%e A289625 For n=8, the multiplicative group modulo 8 is isomorphic to C_2 x C_2, thus a(8) = 2^2 * 3^2 = 36.
%e A289625 For n=15, the multiplicative group modulo 15 is isomorphic to C_4 x C_2, thus a(15) = 2^4 * 3^2 = 144.
%o A289625 (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); };
%Y A289625 Cf. A000010, A002322, A046072.
%Y A289625 Cf. A033948 (positions of terms that are powers of 2).
%Y A289625 Cf. A289626 (rgs-transform of this sequence).
%K A289625 nonn
%O A289625 1,3
%A A289625 _Antti Karttunen_, Jul 17 2017