A272592 -id:A272592 - 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

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, ", ")));

A272595 Numbers n such that the multiplicative group modulo n is the direct product of 5 cyclic groups.

Original entry on oeis.org

840, 1320, 1560, 1680, 1848, 2040, 2184, 2280, 2520, 2640, 2760, 2856, 3080, 3120, 3192, 3360, 3432, 3480, 3640, 3696, 3720, 3864, 3960, 4080, 4200, 4368, 4440, 4488, 4560, 4620, 4680, 4760, 4872, 4920, 5016, 5040, 5160, 5208, 5280, 5304, 5320, 5460, 5520, 5544, 5640, 5712, 5720, 5880, 5928, 6072, 6120

Offset: 1

Joerg Arndt, May 05 2016

nonn

Numbers n such that A046072(n) = 5.

Direct product of k groups: A033948 (k=1), A272592 (k=2), A272593 (k=3), A272594 (k=4), 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[10^4], A046072[#] == 5&] (* Jean-François Alcover, Dec 22 2021, after Geoffrey Critzer in A046072 *)

for(n=1, 10^4, my(t=#(znstar(n)[2])); if(t==5, 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, ", ")));

A157230 Number of primitive inequivalent sublattices of square lattice having mirrors parallel to the diagonals of the unit cell of the parent lattice of index n.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 4, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 4, 1, 2, 1, 2, 2, 1, 1, 4, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 4, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 4, 1, 1, 2, 2, 2, 2, 1, 4, 1, 1, 1, 4, 2, 1, 2

Offset: 1

N. J. A. Sloane, Feb 25 2009

nonn

After a(2), this matches A034380 except for n = 63, 65, 80, 85, ... - R. J. Mathar, Feb 27 2009 [Updated by Andrey Zabolotskiy, May 09 2018]

Andrey Zabolotskiy, Table of n, a(n) for n = 1..5000
J. S. Rutherford, Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type, Act. Cryst. A65 (2009) 156-163, Table 5 symmetry *mm2.

Cf. A145393 (all sublattices of the square lattice), A019590, A157228, A157226, A157231, A304182, A060594, A046072, A033948, A272592.

a[n_] := If[n <= 2, 0, Sum[Boole[Mod[k^2, n] == 1], {k, 1, n}]/2];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Apr 12 2023 *)

From Andrey Zabolotskiy, Sep 30 2018: (Start)
a(n) = (A060594(n) - A019590(n))/2.
a(n) = 2^(A046072(n)-1) for n>2. Thus a(n) = 1 if n>2 is in A033948, a(n) = 2 if n is in A272592, etc. (End)

New name and more terms from Andrey Zabolotskiy, May 09 2018

A225375 Odd numbers with exactly 2 distinct prime factors.

Original entry on oeis.org

15, 21, 33, 35, 39, 45, 51, 55, 57, 63, 65, 69, 75, 77, 85, 87, 91, 93, 95, 99, 111, 115, 117, 119, 123, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 171, 175, 177, 183, 185, 187, 189, 201, 203, 205, 207, 209, 213, 215, 217, 219, 221, 225, 235, 237

Offset: 1

R. J. Mathar, Oct 13 2008

nonn

Numbers of the form p^i*q^j where p, q are distinct odd primes and i>=1, j>=1.

Subset of A098905 (which contains in addition A046390 and numbers like 255255, 285285, 345345, 373065 etc.).

Subsequence of A272592. A046388 is a subsequence.
Cf. A046315, A046390, A046404, A024556, A056913.
Different from A046388, A098905.

isA225375 := proc(n) RETURN( (n mod 2 = 1) and (A001221(n) = 2) ); end proc:
for n from 1 to 840 do if isA225375(n) then printf("%d,",n) ; end if; end do:

Select[2 Range[200] + 1, PrimeNu[#] == 2&] (* Jean-François Alcover, Apr 04 2020 *)

is_A046388(n)={ bittest(n,0) & omega(n)==2 } \\ M. F. Hasler, Feb 13 2012

Entry created by N. J. A. Sloane, May 09 2013 in order to restore the original definition of A046388.

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

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

A272595 Numbers n such that the multiplicative group modulo n is the direct product of 5 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

A157230 Number of primitive inequivalent sublattices of square lattice having mirrors parallel to the diagonals of the unit cell of the parent lattice of index n.

Views

Author

Keywords