cp's OEIS Frontend

A258446 Irregular triangular array read by rows. Row n gives the decomposition of the multiplicative group of integers modulo n as a direct product of cyclic groups C_1 X C_2 X ... X C_k, where |C_i| divides |C_j|, i>j.

%I A258446 #23 Feb 16 2025 08:33:25
%S A258446 1,2,2,4,2,6,2,2,6,4,10,2,2,12,6,4,2,4,2,16,6,18,4,2,6,2,10,22,2,2,2,
%T A258446 20,12,18,6,2,28,4,2,30,8,2,10,2,16,12,2,6,2,36,18,12,2,4,2,2,40,6,2,
%U A258446 42,10,2,12,2,22,46,4,2,2,42,20
%N A258446 Irregular triangular array read by rows.  Row n gives the decomposition of the multiplicative group of integers modulo n as a direct product of cyclic groups C_1 X C_2 X ... X C_k, where |C_i| divides |C_j|, i>j.
%C A258446 Row lengths are A046072.
%C A258446 The products of the terms in each row are A000010.
%C A258446 First column is A002322.
%C A258446 Row 2^k is [2, 2^(k-2)] for k > 2. - _Tom Edgar_, May 31 2015
%C A258446 Row p^k (and row 2*p^k) is [(p-1)*p^(k-1)] for odd prime p. - _Tom Edgar_, May 31 2015
%C A258446 The number of distinct groups over numbers less than or equal to 10^k for k=1,2,3,4,5,6 is  5, 50, 447, 4060, 36655, 335714.
%D A258446 Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 92-93, 1993.
%H A258446 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ModuloMultiplicationGroup.html">Modulo Multiplication Group</a>
%H A258446 Wikipedia, <a href="http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative Group of Integers Modulo n.</a>
%e A258446 1;
%e A258446 2;
%e A258446 2;
%e A258446 4;
%e A258446 2;
%e A258446 6;
%e A258446 2, 2;
%e A258446 6;
%e A258446 4;
%e A258446 10;
%e A258446 2, 2;
%e A258446 12;
%e A258446 6;
%e A258446 4, 2;
%e A258446 4, 2;
%e A258446 16;
%e A258446 6;
%e A258446 18;
%e A258446 4, 2;
%e A258446 6, 2;
%e A258446 10;
%e A258446 22;
%e A258446 2, 2, 2;
%e A258446 The row for n=8 reads: 2,2 because the multiplicative group mod 8 is isomorphic to C_2 X C_2.
%t A258446 f[{p_, e_}] := {FactorInteger[p - 1][[All, 1]]^
%t A258446    FactorInteger[p - 1][[All, 2]],
%t A258446   FactorInteger[p^(e - 1)][[All, 1]]^
%t A258446    FactorInteger[p^(e - 1)][[All, 2]]};
%t A258446 fun[lst_] :=
%t A258446 Module[{int, num, res},
%t A258446   int = Sort /@ GatherBy[Join @@ (FactorInteger /@ lst), First];
%t A258446   num = Times @@ Power @@@ (Last@# & /@ int);
%t A258446   res = Flatten[Map[Power @@ # &, Most /@ int, {2}]];
%t A258446   {num, res}]
%t A258446 rec[lt_] :=
%t A258446 First@NestWhile[{Append[#[[1]], fun[#[[2]]][[1]]],
%t A258446      fun[#[[2]]][[2]]} &, {{}, lt}, Length[#[[2]]] > 0 &];
%t A258446 Table[If[! IntegerQ[n/8],
%t A258446     DeleteCases[rec[Flatten[Map[f, FactorInteger[n]]]], 1],
%t A258446     DeleteCases[
%t A258446      rec[Join[{2, 2^(FactorInteger[n][[1, 2]] - 2)},
%t A258446        Flatten[Map[f, Drop[FactorInteger[n], 1]]]]], 1]], {n, 2,
%t A258446     50}] /. {} -> {1} // Grid
%K A258446 nonn,tabf
%O A258446 2,2
%A A258446 _Geoffrey Critzer_ and Mark Dooris, May 30 2015