A046073 -id:A046073 - cp's OEIS frontend

A294342 Numbers k at which the ratio (number of squares in the multiplicative group modulo k)/k reaches a new minimum.

1, 2, 3, 4, 6, 8, 12, 24, 60, 120, 420, 840, 4620, 9240, 60060, 120120, 1021020, 2042040, 19399380, 38798760, 446185740, 892371480

Offset: 1

Jon E. Schoenfield, Oct 28 2017

I.e., numbers k such that A046073(k)/k < A046073(j)/j for all j < k.

Appears to be just the union of 2*A002110, 4*A002110, and {1,3,6}. - Don Reble, Nov 26 2017

			     k    A046073(k)              A046073(k)/k
  ======= ========== ========================================
        1       1       1/1       =   1      = 1.000000000
        2       1       1/2       =  1/2     = 0.500000000
        3       1       1/3       =  1/3     = 0.333333333...
        4       1       1/4       =  1/4     = 0.250000000
        6       1       1/6       =  1/6     = 0.166666666...
        8       1       1/8       =  1/8     = 0.125000000
       12       1       1/12      =  1/12    = 0.083333333...
       24       1       1/24      =  1/24    = 0.041666666...
       60       2       2/60      =  1/30    = 0.033333333...
      120       2       2/120     =  1/60    = 0.016666666...
      420       6       6/420     =  1/70    = 0.014285714...
      840       6       6/840     =  1/140   = 0.007142857...
     4620      30      30/4620    =  1/154   = 0.006493506...
     9240      30      30/9240    =  1/308   = 0.003246753...
    60060     180     180/60060   =  3/1001  = 0.002997002...
   120120     180     180/120120  =  3/2002  = 0.001498501...
  1021020    1440    1440/1021020 = 24/17017 = 0.001410354...
  2042040    1440    1440/2042040 = 12/17017 = 0.000705177...

Cf. A046073.

m=oo;for(k=1,oo, m > A046073(k)/k||next;print1(k",");m=A046073(k)/k) \\ M. F. Hasler, Nov 27 2017

Terms a(19) .. a(22) from Joerg Arndt, Dec 28 2017

A368042 Moduli k for which the number of quadratic residues mod k coprime to k is phi(k)/2^r for positive r = (phi(k)/lambda(k)) - x, x > 0, where lambda is Carmichael's function. Complement of A366935.

Original entry on oeis.org

2, 24, 40, 48, 56, 60, 63, 65, 72, 80, 84, 85, 88, 91, 96, 104, 105, 112, 117, 120, 126, 130, 132, 133, 136, 140, 144, 145, 152, 156, 160, 165, 168, 170, 171, 176, 180, 182, 184, 185, 189, 192, 195, 200, 204, 205, 208, 210, 216, 217

Offset: 1

Miles Englezou, Dec 09 2023

An empirical observation, verified for 2 <= k <= 10^5: The number of quadratic residues mod k coprime to k is |Q_k| = phi(k)/2^r, r = A046072(k) <= phi(k)/lambda(k). Up to 10^5, the equality holds for 37758 moduli, and the inequality holds for 62241.

			k = 2 is a term: |Q_2| = phi(2)/2^0 = 1, and r = 0 < phi(2)/lambda(2) = 1.

D. Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993, page 95.

Cf. A366935, A000010, A002322, A046073, A034380, A033948, A046072.

isok(n) = my(z=znstar(n).cyc); #z < eulerphi(n)/lcm(z)

cp's OEIS Frontend

A294342 Numbers k at which the ratio (number of squares in the multiplicative group modulo k)/k reaches a new minimum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions