A033948 -id:A033948 - cp's OEIS frontend

A070667 Smallest m in range 2..n-1 such that m^2 == 1 mod n, or 1 if no such number exists.

1, 1, 2, 3, 4, 5, 6, 3, 8, 9, 10, 5, 12, 13, 4, 7, 16, 17, 18, 9, 8, 21, 22, 5, 24, 25, 26, 13, 28, 11, 30, 15, 10, 33, 6, 17, 36, 37, 14, 9, 40, 13, 42, 21, 19, 45, 46, 7, 48, 49, 16, 25, 52, 53, 21, 13, 20, 57, 58, 11, 60, 61, 8, 31, 14, 23, 66, 33, 22, 29

Offset: 1

N. J. A. Sloane, May 08 2002

nonn

If n has a primitive root (i.e. if n is in A033948(n)) then a(n)=n-1, if not (i.e. if n is in A033949(n)), a(n)A000961(m), then a(n)=n/2-1. Questions : for which n does the equation A070667(x)=x-n have at least one solution, does always A070667(x)=x-p have at least one solution when p is prime =>5? - Benoit Cloitre, May 12 2002

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A033948, A033949, A000961.

a:= proc(n) local k; for k from 2 do if 1=k*k mod n
      then return k elif k>=n then return 1 fi od
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Oct 30 2016

Join[{1,1},Flatten[Table[Select[Range[2,n-1],PowerMod[#,2,n]==1&,1],{n,70}]]] (* Harvey P. Dale, May 01 2012 *)

A001751 Primes together with primes multiplied by 2.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 10, 11, 13, 14, 17, 19, 22, 23, 26, 29, 31, 34, 37, 38, 41, 43, 46, 47, 53, 58, 59, 61, 62, 67, 71, 73, 74, 79, 82, 83, 86, 89, 94, 97, 101, 103, 106, 107, 109, 113, 118, 122, 127, 131, 134, 137, 139, 142, 146, 149, 151, 157, 158, 163, 166

Offset: 1

N. J. A. Sloane

For n > 1, a(n) is position of primes in A026741.
For n > 1, a(n) is the position of the ones in A046079. - Ant King, Jan 29 2011
A251561(a(n)) != a(n). - Reinhard Zumkeller, Dec 27 2014
Number of terms <= n is pi(n) + pi(n/2). - Robert G. Wilson v, Aug 04 2017
Number of terms <=10^k: 7, 40, 263, 1898, 14725, 120036, 1013092, 8762589, 77203401, 690006734, 6237709391, 56916048160, 523357198488, 4843865515369, ..., . - Robert G. Wilson v, Aug 04 2017
Complement of A264828. - Chai Wah Wu, Oct 17 2024

T. D. Noe, Table of n, a(n) for n = 1..10000

Union of A001747 and A000040.
Subsequence of A039698 and of A033948.
Cf. A026741, A046079, A178156, A251561, A264828.

a001751 n = a001751_list !! (n-1)
a001751_list = 2 : filter (\n -> (a010051 $ div n $ gcd 2 n) == 1) [1..]
-- Reinhard Zumkeller, Jun 20 2011 (corrected, improved), Dec 17 2010

Select[Range[163], Or[PrimeQ[#], PrimeQ[1/2 #]] &] (* Ant King, Jan 29 2011 *)
upto=200;With[{pr=Prime[Range[PrimePi[upto]]]},Select[Sort[Join[pr,2pr]],# <= upto&]] (* Harvey P. Dale, Sep 23 2014 *)

isA001751(n)=isprime(n/gcd(n,2)) || n==2

list(lim)=vecsort(concat(primes(primepi(lim)), 2* primes(primepi(lim\2)))) \\ Charles R Greathouse IV, Oct 31 2012

from sympy import primepi
def A001751(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+x-primepi(x)-primepi(x>>1))
    return bisection(f,n,n) # Chai Wah Wu, Oct 17 2024

A167794 Numbers with primitive root 6.

Original entry on oeis.org

11, 13, 17, 41, 59, 61, 79, 83, 89, 103, 107, 109, 113, 121, 127, 131, 137, 151, 157, 169, 179, 199, 223, 227, 229, 233, 251, 257, 271, 277, 289, 347, 367, 373, 397, 401, 419, 443, 449, 467, 487, 491, 521, 563, 569, 587, 593, 613, 641, 659, 661, 683, 709, 733

Offset: 1

T. D. Noe, Nov 12 2009

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A019336 (primes with primitive root 6). Subsequence of A033948.

A167794 := proc(n)
    option remember;
    if n =1 then
        11;
    else
        for a from procname(n-1)+1 do
            if numtheory[order](6,a) = numtheory[phi](a) then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A167794(n),n=1..80) ; # R. J. Mathar, Sep 15 2021

pr=6; Select[Range[2,2000], MultiplicativeOrder[pr,# ] == EulerPhi[ # ] &]

is(n)=if(gcd(n, 6)>1, return(0)); my(p=eulerphi(n)); znorder(Mod(6, n), p)==p \\ Charles R Greathouse IV, Jan 04 2025

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

Original entry on oeis.org

1, 1, 4, 4, 16, 4, 64, 36, 64, 16, 1024, 36, 4096, 64, 144, 144, 65536, 64, 262144, 144, 576, 1024, 4194304, 900, 1048576, 4096, 262144, 576, 268435456, 144, 1073741824, 2304, 9216, 65536, 36864, 576, 68719476736, 262144, 36864, 3600, 1099511627776, 576, 4398046511104, 9216, 36864, 4194304, 70368744177664, 3600, 4398046511104, 1048576, 589824, 36864

Offset: 1

Antti Karttunen, Jul 17 2017

nonn

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}.

			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.
For n=8, the multiplicative group modulo 8 is isomorphic to C_2 x C_2, thus a(8) = 2^2 * 3^2 = 36.
For n=15, the multiplicative group modulo 15 is isomorphic to C_4 x C_2, thus a(15) = 2^4 * 3^2 = 144.

Antti Karttunen, Table of n, a(n) for n = 1..1024
The PARI group, Catalogue of GP/PARI Functions: Arithmetic functions, function znstar
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
Wikipedia, Multiplicative group of integers modulo n

Cf. A000010, A002322, A046072.
Cf. A033948 (positions of terms that are powers of 2).
Cf. A289626 (rgs-transform of this sequence).

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); };

A005361(a(n)) = A000010(n).
A072411(a(n)) = A002322(n).
A007814(a(n)) = A002322(n) for n > 2.
A001221(a(n)) = A046072(n) for n > 2.

A062373 Ratio of totient to Carmichael's lambda function is 2.

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, 64, 66, 68, 69, 70, 75, 76, 77, 78, 87, 90, 92, 93, 95, 99, 100, 102, 108, 110, 111, 114, 115, 116, 119, 123, 124, 128, 129, 135, 138, 141, 143, 147, 148, 150, 153, 154, 155, 159, 161

Offset: 1

Vladeta Jovovic, Jun 17 2001

Numbers k such that the highest order of elements in (Z/kZ)* is phi(n)/2, (Z/kZ)* = the multiplicative group of integers modulo k. Also numbers k such that (Z/kZ)* = C_2 X C_(2r). - Jianing Song, Jul 28 2018

Contains the powers of 2 greater than 4, 4 times primes, and semiprimes pq where (p-1)/2 and (q-1)/2 are coprime. If n is odd and in this sequence then so is 2n. - Charlie Neder, May 27 2019

			From _Jianing Song_, Jul 28 2018: (Start)
(Z/8Z)* = C_2 X C_2, so 8 is a term.
(Z/21Z)* = C_2 X C_6, so 21 is a term.
(Z/35Z)* = C_2 X C_12, so 35 is a term. (End)

R. J. Mathar, Table of n, a(n) for n = 1..20000

Cf. A000010, A002322, A034380, A033948, A062374, A062375, A062376, A062377.

a062373 n = a062373_list !! (n-1)
a062373_list = filter ((== 2) . a034380) [1..]
-- Reinhard Zumkeller, Sep 02 2014

Reap[ For[ n = 1, n <= 161, n++, If[ EulerPhi[n] / CarmichaelLambda[n] == 2, Sow[n]]]][[2, 1]] (* Jean-François Alcover, Mar 26 2013 *)
Select[Range[200],EulerPhi[#]/CarmichaelLambda[#]==2&] (* Harvey P. Dale, Jun 27 2018 *)

isok(n) = eulerphi(n)/lcm(znstar(n)[2]) == 2; \\ Michel Marcus, Jul 28 2018

Solutions to phi(k)/lambda(k) = 2.

More terms from Reiner Martin, Dec 22 2001

A206551 Moduli n for which the multiplicative group Modd n is cyclic.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 31, 32, 33, 34, 35, 37, 38, 39, 41, 43, 45, 46, 47, 49, 50, 51, 53, 54, 55, 57, 58, 59, 61, 62, 64, 67, 69, 71, 73, 74, 75, 77, 79, 81, 82, 83, 86, 87, 89, 93, 94, 95, 97, 98, 99

Offset: 1

Wolfdieter Lang, Mar 27 2012

nonn

For Modd n (not to be confused with mod n) see a comment on A203571.
For n=1 one has the Modd 1 residue class [0], the integers. The group of order 1 is the cyclic group Z_1 with the unit element 0==1 (Modd 1). [Changed by Wolfdieter Lang, Apr 04 2012]
For the non-cyclic (acyclic) values see A206552.
For these numbers n, and only for these (only the n values < 100 are shown above), there exist primitive roots Modd n. See the nonzero values of A206550 for the smallest positive ones.
  For n=1 the primitive root is 0 == 1 (Modd 1), see above.
For n>=1 the multiplicative group Modd n is the Galois group Gal(Q(rho(n))/Q), with the algebraic number rho(n) := 2*cos(Pi/n) with minimal polynomial C(n,x), whose coefficients are given in A187360.

			a(2) = 2 for the multiplicative group Modd 2, with representative [1], and there is a primitive root, namely 1, because 1^1 = 1 == 1 (Modd 1). The cycle structure is [[1]], the group is Z_1.
a(3) = 3 for the multiplicative group Modd 3 which coincides with the one for Modd 2.
a(4) = 4 for the multiplicative group Modd 4 with representatives [1,3]. The smallest positive  primitive root is 3, because 3^2 == 1 (Modd 4). This group is cyclic, it is Z_2.

Cf. A206550, A033948 (mod n case).

A206550(a(n)) > 0, n>=1.

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

A278568 Twice odd prime powers.

Original entry on oeis.org

2, 6, 10, 14, 18, 22, 26, 34, 38, 46, 50, 54, 58, 62, 74, 82, 86, 94, 98, 106, 118, 122, 134, 142, 146, 158, 162, 166, 178, 194, 202, 206, 214, 218, 226, 242, 250, 254, 262, 274, 278, 298, 302, 314, 326, 334, 338, 346, 358, 362, 382, 386, 394, 398, 422, 446, 454, 458, 466, 478

Offset: 1

N. J. A. Sloane, Nov 26 2016

nonn

L. J. Corwin, Irreducible polynomials over the integers which factor mod p for every p, Unpublished Bell Labs Memo, Sep 07 1967 [Annotated scanned copy]

Twice A061345.

from sympy import primepi, integer_nthroot
def A278568(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+x-1-sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length())))
    return bisection(f,n,n)<<1 # Chai Wah Wu, Feb 03 2025

A062377 Euler phi(n) / Carmichael lambda(n) = 10.

Original entry on oeis.org

275, 341, 451, 550, 671, 682, 775, 781, 902, 1111, 1271, 1342, 1375, 1441, 1550, 1562, 1661, 1775, 1991, 2101, 2201, 2222, 2321, 2542, 2651, 2750, 2761, 2882, 2911, 2981, 3025, 3091, 3131, 3275, 3322, 3421, 3550, 3641, 3751, 3775, 3875, 3982, 4061

Offset: 1

Vladeta Jovovic, Jun 17 2001

Solutions to A000010(n)/A002322(n)=10.

R. J. Mathar, Table of n, a(n) for n = 1..7771

Cf. A000010, A002322, A034380, A033948, A062373, A062374, A062375, A062376.

Reap[ For[ n = 1, n <= 4061, n++, If[ EulerPhi[n] / CarmichaelLambda[n] == 10, Sow[n]]]][[2, 1]] (* Jean-François Alcover, Mar 26 2013 *)
Select[Range[4100],EulerPhi[#]/CarmichaelLambda[#]==10&] (* Harvey P. Dale, Dec 22 2022 *)

{cmf(f)=if( ((f[1]==2)&&(f[2]>2)),eulerphi(f[1]^f[2])/2, eulerphi(f[1]^f[2])) } {cl(f)= k=factor(f); l=1; for(x=1,omega(f),l=lcm(l,cmf([k[x,1], k[x,2]]))); l } {A062377(n)=eulerphi(n)/cl(n)} for(x=1,10001, if(A062377(x)==10,print1(x,",")))

More terms from Randall L Rathbun, Jan 12 2002

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

cp's OEIS Frontend

A070667 Smallest m in range 2..n-1 such that m^2 == 1 mod n, or 1 if no such number exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A001751 Primes together with primes multiplied by 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

A167794 Numbers with primitive root 6.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A062373 Ratio of totient to Carmichael's lambda function is 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A206551 Moduli n for which the multiplicative group Modd n is cyclic.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

A278568 Twice odd prime powers.

Views

Author

Keywords