A272595 -id:A272595 - cp's OEIS frontend

A046072 Decompose multiplicative group of integers modulo n 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; then a(n) = m.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, 2, 2, 2, 1, 2, 3, 1, 1, 2, 2, 1, 2

Offset: 1

Eric W. Weisstein

The multiplicative group modulo n can be written as the direct product of a(n) (but not fewer) cyclic groups. - Joerg Arndt, Dec 25 2014
a(n) = 1 (that is, the multiplicative group modulo n is cyclic) iff n is in A033948, or equivalently iff A034380(n)=1. - Max Alekseyev, Jan 07 2015
This sequence gives the minimal number of generators of the multiplicative group of integers modulo n which is isomorphic to the Galois group Gal(Q(zeta_n)/Q), with zeta_n =exp(2*Pi*I/n). See, e.g., Theorem 9.1.11., p. 235 of the Cox reference. See also the table of the Wikipedia link. - Wolfdieter Lang, Feb 28 2017
In this factorization the trivial group C_1 = {1} is allowed as a factor only for n = 0 and 1 (otherwise one could have arbitrarily many leading C_1 factors for n >= 3). - Wolfdieter Lang, Mar 07 2017

David A. Cox, Galois Theory, John Wiley & Sons, Hoboken, New Jrsey, 2004, 235.
Daniel Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 92-93, 1993.

Joerg Arndt, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
Wikipedia, Multiplicative group of integers modulo n. See the table at the end.

Cf. A001221, A046073 (number of squares in multiplicative group modulo n), A077761, A281855, A282625 (for total factorization).

a(n)=k iff n is in: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

f[n_] := Which[OddQ[n], PrimeNu[n], EvenQ[n] && ! IntegerQ[n/4],
  PrimeNu[n] - 1, IntegerQ[n/4] && ! IntegerQ[n/8], PrimeNu[n],
  IntegerQ[n/8], PrimeNu[n] + 1]; Join[{1, 1},
Table[f[n], {n, 3, 102}]] (* Geoffrey Critzer, Dec 24 2014 *)

a(n)=if(n<=2, 1, #znstar(n)[3]); \\ Joerg Arndt, Aug 26 2014

a(n) = A001221(n) - 1 if n > 2 is divisible by 2 and not by 4, a(n) = A001221(n) + 1 if n is divisible by 8, a(n) = A001221(n) in other cases. - Ivan Neretin, Aug 01 2016

Sum_{k=1..n} a(k) = n * (log(log(n)) + B - 1/8) + O(n/log(n)), where B is Mertens's constant (A077761). - Amiram Eldar, Sep 21 2024

A272592 Numbers n such that the multiplicative group modulo n is the direct product of 2 cyclic groups.

Original entry on oeis.org

8, 12, 15, 16, 20, 21, 28, 30, 32, 33, 35, 36, 39, 42, 44, 45, 51, 52, 55, 57, 63, 64, 65, 66, 68, 69, 70, 75, 76, 77, 78, 85, 87, 90, 91, 92, 93, 95, 99, 100, 102, 108, 110, 111, 114, 115, 116, 117, 119, 123, 124, 126, 128, 129, 130, 133, 135, 138, 141, 143, 145, 147, 148, 150, 153, 154, 155, 159, 161

Offset: 1

Joerg Arndt, May 03 2016

nonn

Numbers n such that A046072(n) = 2.

Numbers are of the form p^e*q^f, 2*p^e*q^f, 4p^e, or 2^(e+2) where p and q are distinct odd primes and e,f >= 1. - Charles R Greathouse IV, Jan 09 2022

Cf. A046072.
Supersequence of A225375.
Direct product of k groups: A033948 (k=1), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[200], A046072[#] == 2&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1,10^3, my(t=#(znstar(n)[2]));if(t==2,print1(n,", ")));

A272593 Numbers n such that the multiplicative group modulo n is the direct product of 3 cyclic groups.

Original entry on oeis.org

24, 40, 48, 56, 60, 72, 80, 84, 88, 96, 104, 105, 112, 132, 136, 140, 144, 152, 156, 160, 165, 176, 180, 184, 192, 195, 200, 204, 208, 210, 216, 220, 224, 228, 231, 232, 248, 252, 255, 260, 272, 273, 276, 285, 288, 296, 300, 304, 308, 315, 320, 328, 330, 340, 344, 345, 348, 352, 357, 364, 368, 372, 376, 380

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 3.

Cf. A046072.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[400], A046072[#] == 3&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 10^3, my(t=#(znstar(n)[2])); if(t==3, print1(n, ", ")));

A272594 Numbers n such that the multiplicative group modulo n is the direct product of 4 cyclic groups.

Original entry on oeis.org

120, 168, 240, 264, 280, 312, 336, 360, 408, 420, 440, 456, 480, 504, 520, 528, 552, 560, 600, 616, 624, 660, 672, 680, 696, 720, 728, 744, 760, 780, 792, 816, 880, 888, 912, 920, 924, 936, 952, 960, 984, 1008, 1020, 1032, 1040, 1056, 1064, 1080, 1092, 1104, 1120, 1128, 1140, 1144, 1155, 1160, 1176, 1200

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 4.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[1200], A046072[#] == 4&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 3*10^3, my(t=#(znstar(n)[2])); if(t==4, print1(n, ", ")));

A272596 Numbers n such that the multiplicative group modulo n is the direct product of 6 cyclic groups.

Original entry on oeis.org

9240, 10920, 14280, 15960, 17160, 18480, 19320, 21840, 22440, 24024, 24360, 25080, 26040, 26520, 27720, 28560, 29640, 30360, 31080, 31416, 31920, 32760, 34320, 34440, 35112, 35880, 36120, 36960, 37128, 38280, 38640, 38760, 39480, 40040, 40920, 41496, 42504, 42840, 43680, 44520, 44880, 45240, 46200

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 6.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272597 (k=7), A272598 (k=8), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[5*10^4], A046072[#] == 6&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 10^5, my(t=#(znstar(n)[2])); if(t==6, print1(n, ", ")));

A272597 Numbers n such that the multiplicative group modulo n is the direct product of 7 cyclic groups.

Original entry on oeis.org

120120, 157080, 175560, 185640, 207480, 212520, 240240, 251160, 267960, 271320, 286440, 291720, 314160, 316680, 326040, 328440, 338520, 341880, 351120, 360360, 367080, 371280, 378840, 394680, 397320, 404040, 408408, 414120, 414960, 425040, 426360, 434280, 442680, 447720, 456456, 462840, 469560, 471240

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 7.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272598 (k=8), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[5*10^5], A046072[#] == 7&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 10^6, my(t=#(znstar(n)[2])); if(t==7, print1(n, ", ")));

A272598 Numbers n such that the multiplicative group modulo n is the direct product of 8 cyclic groups.

Original entry on oeis.org

2042040, 2282280, 2762760, 2984520, 3483480, 3527160, 3612840, 3723720, 4037880, 4084080, 4269720, 4444440, 4555320, 4564560, 4772040, 4869480, 4924920, 5091240, 5165160, 5383560, 5442360, 5525520, 5542680, 5645640, 5754840, 5811960, 5969040, 6016920, 6126120, 6163080, 6240360, 6366360, 6431880, 6440280

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 8.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272599 (k=9).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && !Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[120, 120*10^5, 120], A046072[#] == 8&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 10^7, my(t=#(znstar(n)[2])); if(t==8, print1(n, ", ")));

A272599 Numbers n such that the multiplicative group modulo n is the direct product of 9 cyclic groups.

Original entry on oeis.org

38798760, 46966920, 52492440, 59219160, 63303240, 66186120, 68643960, 70750680, 75555480, 77597520, 80120040, 81124680, 83723640, 84444360, 85645560, 86551080, 87807720, 92520120, 93573480, 93933840, 95975880, 98138040, 102222120, 102287640, 104772360, 104984880, 107267160, 107987880, 108228120, 109341960, 110427240

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 9.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8).

A046072[n_] := Which[n == 1 || n == 2, 1,
     OddQ[n], PrimeNu[n],
     EvenQ[n] && !Divisible[n, 4], PrimeNu[n] - 1,
     Divisible[n, 4] && ! Divisible[n, 8], PrimeNu[n],
     Divisible[n, 8], PrimeNu[n] + 1];
Select[Range[840, 840*140000, 840], A046072[#] == 9&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 10^9, my(t=#(znstar(n)[2])); if(t==9, print1(n, ", ")));

A272590 a(n) is the smallest number m such that the multiplicative group modulo m is the direct product of n cyclic groups.

Original entry on oeis.org

2, 8, 24, 120, 840, 9240, 120120, 2042040, 38798760, 892371480, 25878772920, 802241960520, 29682952539240, 1217001054108840, 52331045326680120, 2459559130353965640, 130356633908760178920, 7691041400616850556280, 469153525437627883933080, 31433286204321068223516360

Offset: 1

Joerg Arndt, May 05 2016

nonn

Arguably a(1)=3, as the multiplicative group mod 2 has only one element, hence its factorization is the empty product. - Joerg Arndt, May 18 2018

For n >= 2, positions of records of A046072. - Joerg Arndt, May 18 2018

Cf. A002322, A102476, A058254.

Numbers n such that the multiplicative group modulo n is the direct product of k cyclic groups: A033948 (k=1), A272593 (k=2), A272593 (k=3), A272594 (k=4), A272595 (k=5), A272596 (k=6), A272597 (k=7), A272598 (k=8), A272599 (k=9).

a(n)=if(n==1,2,4*prod(k=1,n-1,prime(k)));

a(1) = 2, a(n) = 4 * prod(k=1..n-1, prime(k) ) for n >= 2.
a(n) = A102476(n) for n >= 2.
A002322(a(n)) = A058254(n).

cp's OEIS Frontend

A046072 Decompose multiplicative group of integers modulo n 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; then a(n) = m.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A272592 Numbers n such that the multiplicative group modulo n is the direct product of 2 cyclic groups.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A272593 Numbers n such that the multiplicative group modulo n is the direct product of 3 cyclic groups.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A272594 Numbers n such that the multiplicative group modulo n is the direct product of 4 cyclic groups.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A272596 Numbers n such that the multiplicative group modulo n is the direct product of 6 cyclic groups.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A272597 Numbers n such that the multiplicative group modulo n is the direct product of 7 cyclic groups.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A272598 Numbers n such that the multiplicative group modulo n is the direct product of 8 cyclic groups.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A272599 Numbers n such that the multiplicative group modulo n is the direct product of 9 cyclic groups.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A272590 a(n) is the smallest number m such that the multiplicative group modulo m is the direct product of n cyclic groups.

Views

Author

Keywords