A033948 -id:A033948 - cp's OEIS frontend

A306252 Least primitive root mod A033948(n).

0, 1, 2, 3, 2, 5, 3, 2, 3, 2, 2, 3, 3, 5, 2, 7, 5, 2, 7, 2, 2, 3, 3, 2, 3, 6, 3, 5, 5, 3, 3, 2, 5, 3, 2, 2, 3, 2, 7, 5, 5, 3, 2, 7, 2, 3, 3, 5, 5, 3, 2, 5, 3, 2, 6, 3, 11, 2, 7, 2, 3, 2, 7, 3, 2, 7, 5, 2, 6, 5, 3, 5, 2, 5, 5, 2, 2, 3, 2, 2, 19, 5, 5, 2, 3, 3, 5

Offset: 1

Charles Paul, Feb 01 2019

nonn

Let U(k) denote the multiplicative group mod k. a(n) = smallest generator for U(A033948(n)). - N. J. A. Sloane, Mar 10 2019

			For n=2, A033948(2) = 2, U(2) is generated by 1.
For n=14, A033948(14) = 18, and U(18) is generated by both 5 and 11; here we select the smallest generator, 5, so a(14) = 5.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A033948 (numbers that have a primitive root), A306253, A081888 (positions of records), A081889 (record values). First column of A046147.

0,op(subs(FAIL=NULL, map(numtheory:-primroot,[$2..1000]))); # Robert Israel, Mar 10 2019

Array[Take[PrimitiveRootList@ #, UpTo[1]] &, 210] // Flatten (* Michael De Vlieger, Feb 02 2019 *)

from math import gcd
roots = [0]
for n in range(2,140):
    # find U(n)
    un = [i for i in range(1,n) if gcd(i,n) == 1]
    # for each element in U(n), check if it's a generator
    order = len(un)
    is_cyclic = False
    for cand in un:
        is_gen = True
        run = 1
        # If it cand^x = 1 for some x < order, it's not a generator
        for _ in range(order-1):
            run = (run * cand) % n
            if run == 1:
                is_gen = False
                break
        if is_gen:
            roots.append(cand)
            is_cyclic = True
            break
print(roots)

More terms from Michael De Vlieger, Feb 02 2019
Edited by N. J. A. Sloane, Mar 10 2019
Edited by Robert Israel, Mar 10 2019

A306253 Largest primitive root mod A033948(n).

Original entry on oeis.org

0, 1, 2, 3, 3, 5, 5, 5, 7, 8, 11, 5, 14, 11, 15, 19, 21, 23, 19, 23, 27, 24, 31, 35, 33, 35, 34, 43, 45, 47, 47, 51, 47, 55, 56, 59, 55, 63, 69, 68, 69, 77, 77, 75, 80, 77, 86, 91, 92, 89, 99, 101, 103, 104, 103, 110, 115, 117, 115, 123, 118, 128, 117, 134, 135

Offset: 1

Charles Paul, Feb 01 2019

nonn

Let U(k) denote the multiplicative group mod k. a(n) = largest generator for U(A033948(n)). - N. J. A. Sloane, Mar 10 2019

			For n=2, U(n) is generated by 1.
For n=14, A033948(14) = 18, and, U(n) is generated by both 5 and 11; here we select the largest generator, 11, so a(14) = 11.

Robert Israel, Table of n, a(n) for n = 1..10000

See A306252 for smallest roots and A033948 for the sequence of numbers that have a primitive root.

f:= proc(b) local x, t;
  t:= numtheory:-phi(b);
  for x from b-1 by -1 do if igcd(x,b) = 1 and numtheory:-order(x,b)=t then return x fi od
end proc:
f(1):= 0:
cands:= select(t -> t=1 or numtheory:-primroot(t) <> FAIL, [$1..1000]):
map(f, cands); # Robert Israel, Mar 10 2019

Join[{0}, Last /@ DeleteCases[PrimitiveRootList[Range[1000]], {}]] (* Jean-François Alcover, Jun 18 2020 *)

def gcd(x, y):
    # Euclid's Algorithm
    while(y):
        x, y = y, x % y
    return x
roots = [0]
for n in range(2, 140):
    # find U(n)
    un = [i for i in range(n, 0, -1) if (gcd(i, n) == 1)]
    # for each element in U(n), check if it's a generator
    order = len(un)
    is_cyclic = False
    for cand in un:
        is_gen = True
        run = 1
        # If it cand^x = 1 for some x < order, it's not a generator
        for _ in range(order-1):
            run = (run * cand) % n
            if run == 1:
                is_gen = False
                break
        if is_gen:
            roots.append(cand)
            is_cyclic = True
            break
print("roots:", roots)

Edited by N. J. A. Sloane, Mar 10 2019.

A255979 a(n) = smallest nonnegative integer solution z to the system of congruences: z == 0 (mod n), z == 1 (mod A038610(n)) if n is in A033948; or z == 0 (mod n), z == -1 (mod A038610(n)) if n is in A033949.

Original entry on oeis.org

0, 0, 1, 1, 5, 1, 43, 13, 249, 19, 2291, 32, 6397, 1379, 3737, 36599, 423953, 4727, 2579419, 436486, 1935539, 1262563, 30364247, 1549256, 1028011945, 94055426, 2754232963, 230491358, 77544004469, 7188548, 1277242663471, 4089553744057, 235736847903

Offset: 1

Bruno Berselli, Mar 12 2015 - proposed by Umberto Cerruti (Department of Mathematics "Giuseppe Peano", University of Turin, Italy)

Umberto Cerruti, Il Teorema Cinese dei Resti (in Italian), 2015. The sequence is on page 26.

Cf. A033948, A033949, A038610.

v[n_] := Module[{s}, s = Select[Range[n], CoprimeQ[n, #] == True &]; LCM @@ s]; g1[n_] := If[n == 1, 0, If[IntegerQ[PrimitiveRoot[n]], PowerMod[n, -1, v[n]], PowerMod[-n, -1, v[n]]]]; Table[g1[k], {k, 1, 40}]

A377402 Least k such that the ratio of the number of residues mod k coprime to k and the number of primitive roots mod k is greater than or equal to n for k such that at least one primitive root mod k exists. Equivalently, k such that floor(phi(k)/phi(phi(k)) is a record value for those k belonging to A033948.

Original entry on oeis.org

1, 3, 7, 211, 43891, 300690391

Offset: 1

Miles Englezou, Oct 26 2024

These are the numbers k with the least proportion of primitive roots mod k to residues mod k coprime to k, of all m < k.
Let U(k) be the group of units of the ring Z/kZ, and Gen(k) the set of distinct single element generators of U(k). Then a(n) is equivalently those k for which floor(|U(k)|/|Gen(k)|) is a record value for those k with cyclic U(k).
Some data:
---------------------------------------------------------------------------------
n   a(n)        log(a(n))   phi(a(n))                max prime(r)#|phi(a(n))   r
---------------------------------------------------------------------------------
1   1           0           1                        0                         0
2   3           1.10...     2                        2                         1
3   7           1.96...     2*3                      6                         2
4   211         5.35...     2*3*5*7                  210                       4
5   43891       10.69...    2*3*5*7*11*19            2310                      5
6   300690391   19.52...    2*3*5*7*11*13*17*19*31   9699690                   8
---------------------------------------------------------------------------------
For n > 1, is a(n) necessarily prime? Furthermore, is a(n) necessarily a prime such that phi(a(n)) is squarefree? Lastly, is every phi(a(n)) divisible by a maximal primorial prime(r)# of length r <= omega(phi(a(n))), such that if a maximal prime(s)# divides phi(a(m)) and n < m, then r < s?
Based on the behavior of log(a(n)), we may expect a(7) to be found in the vicinity of floor(exp(40)) = 235385266837019985.

			There are 2 residues mod 3 coprime to 3, and only 1 is a primitive root. 3 is the least k for which the floor of the ratio is 2, and so a(2) = 3.
There are 210 residues mod 211 coprime to 211, and 48 are primitive roots. Floor(210/48) = 4, and 211 is the least k for which the floor of the ratio is 4, and so a(4) = 211.

Cf. A000010, A010554, A033948, A046144.

S=[1]; for(n=1,100000, if(#znstar(n).cyc>1,next); f=eulerphi; if(floor(f(n)/f(f(n)))>floor(f(S[length(S)])/f(f(S[length(S)]))), S=concat(S,n))); print(S)

Numbers k for which floor(A000010(A033948(k))/A046144(A033948(k)) is a record value.

A060594 Number of solutions to x^2 == 1 (mod n), that is, square roots of unity modulo n.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 2, 4, 4, 2, 2, 2, 4, 4, 2, 2, 8, 2, 2, 2, 4, 2, 4, 2, 4, 4, 2, 4, 4, 2, 2, 4, 8, 2, 4, 2, 4, 4, 2, 2, 8, 2, 2, 4, 4, 2, 2, 4, 8, 4, 2, 2, 8, 2, 2, 4, 4, 4, 4, 2, 4, 4, 4, 2, 8, 2, 2, 4, 4, 4, 4, 2, 8, 2, 2, 2, 8, 4, 2, 4, 8, 2, 4, 4, 4, 4, 2, 4, 8, 2, 2, 4, 4, 2, 4, 2

Offset: 1

Jud McCranie, Apr 11 2001

Sum_{k=1..n} a(k) appears to be asymptotic to C*n*log(n) with C = 0.6... - Benoit Cloitre, Aug 19 2002
a(q) is the number of real characters modulo q. - Benoit Cloitre, Feb 02 2003
Also number of real Dirichlet characters modulo n and Sum_{k=1..n}a(k) is asymptotic to (6/Pi^2)*n*log(n). - Steven Finch, Feb 16 2006
Let P(n) be the product of the numbers less than and coprime to n. By theorem 59 in Nagell (which is Gauss's generalization of Wilson's theorem): for n > 2, P == (-1)^(a(n)/2) (mod n). - T. D. Noe, May 22 2009
Shadow transform of A005563. - Michel Marcus, Jun 06 2013
For n > 2, a(n) = 2 iff n is in A033948. - Max Alekseyev, Jan 07 2015
For n > 1, number of square numbers on the main diagonal of an (n-1) X (n-1) square array whose elements are the numbers from 1..n^2, listed in increasing order by rows. - Wesley Ivan Hurt, May 19 2021
a(n) is the number of linear Alexander quandles (Z/nZ, k) that are kei (equivalently, that have good involutions); see Ta, Prop. 5.6 and cf. A387317. - Luc Ta, Aug 26 2025

			The four numbers 1^2, 3^2, 5^2 and 7^2 are congruent to 1 modulo 8, so a(8) = 4.

Trygve Nagell, Introduction to Number Theory, AMS Chelsea, 1981, p. 100. [From T. D. Noe, May 22 2009]
Gérald Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, Cours spécialisé, 1995, Collection SMF, p. 260.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, pp. 196-197.

T. D. Noe, Table of n, a(n) for n = 1..1000
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
Keith Matthews, Solving the congruence x^2=a(mod m).
Emilia Mezzetti and Rosa Maria Miró-Roig, Togliatti systems and Galois coverings, arXiv preprint arXiv:1611.05620 [math.AG], 2016-2018. See Lemma 6.1.
John S. Rutherford, Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type, Acta Cryst. (2009). A65, 156-163. [See Table 4].
N. J. A. Sloane, Transforms.
Lực Ta, Good involutions of twisted conjugation subquandles and Alexander quandles, arXiv:2508.16772 [math.GT], 2025.
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.

Cf. A000010, A005087, A033948, A046073, A073103 (x^4 == 1 (mod n)).
Cf. A001620, A306016.
Cf. A387317.

A060594 := proc(n)
   option remember;
   local a,b,c;
   if type(n,even) then
     a:= padic:-ordp(n,2);
     b:= 2^a;
     c:= n/b;
     min(b/2, 4) * procname(c)
   else
     2^nops(numtheory:-factorset(n))
   fi
end proc:
map(A060594, [$1 .. 100]); # Robert Israel, Jan 05 2015

a[n_] := Sum[ Boole[ Mod[k^2 , n] == 1], {k, 1, n}]; a[1] = 1; Table[a[n], {n, 1, 103}] (* Jean-François Alcover, Oct 21 2011 *)
a[n_] := Switch[Mod[n, 8], 2|6, 2^(PrimeNu[n]-1), 1|3|4|5|7, 2^PrimeNu[n], 0, 2^(PrimeNu[n]+1)]; Array[a, 103] (* Jean-François Alcover, Apr 09 2016 *)

PARI
```
a(n)=sum(i=1,n,if((i^2-1)%n,0,1))
```

a(n)=my(o=valuation(n,2));2^(omega(n>>o)+max(min(o-1,2),0)) \\ Charles R Greathouse IV, Jun 06 2013

a(n)=if(n<=2, 1, 2^#znstar(n)[3] ); \\ Joerg Arndt, Jan 06 2015

from sympy import primefactors
def a007814(n): return 1 + bin(n - 1).count('1') - bin(n).count('1')
def a(n):
    if n%2==0:
        A=a007814(n)
        b=2**A
        c=n//b
        return min(b//2, 4)*a(c)
    else: return 2**len(primefactors(n))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jul 18 2017, after the Maple program

from sympy import primefactors
def A060594(n): return (1<>(s:=(~n & n-1).bit_length()))))*(1 if n&1 else 1<Chai Wah Wu, Oct 26 2022

print([len(Integers(n).square_roots_of_one()) for n in range(1,100)]) # Ralf Stephan, Mar 30 2014

If n == 0 (mod 8), a(n) = 2^(A005087(n) + 2); if n == 4 (mod 8), a(n) = 2^(A005087(n) + 1); otherwise a(n) = 2^(A005087(n)). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 29 2001
a(n) = 2^omega(n)/2 if n == +/-2 (mod 8), a(n) = 2^omega(n) if n== +/-1, +/-3, 4 (mod 8), a(n) = 2*2^omega(n) if n == 0 (mod 8), where omega(n) = A001221(n). - Benoit Cloitre, Feb 02 2003
For n >= 2 A046073(n) * a(n) = A000010(n) = phi(n). This gives a formula for A046073(n) using the one in A060594(n). - Sharon Sela (sharonsela(AT)hotmail.com), Mar 09 2002
Multiplicative with a(2) = 1; a(2^2) = 2; a(2^e) = 4 for e > 2; a(q^e) = 2 for q an odd prime. - Eric M. Schmidt, Jul 09 2013
a(n) = 2^A046072(n) for n>2, in accordance with the above formulas by Ahmed Fares. - Geoffrey Critzer, Jan 05 2015
a(n) = Sum_{k=1..n} floor(sqrt(1+n*(k-1)))-floor(sqrt(n*(k-1))). - Wesley Ivan Hurt, May 19 2021
From Amiram Eldar, Dec 30 2022: (Start)
Dirichlet g.f.: (1-1/2^s+2/4^s)*zeta(s)^2/zeta(2*s).
Sum_{k=1..n} a(k) ~ (6/Pi^2)*n*(log(n) + 2*gamma - 1 - log(2)/2 - 2*zeta'(2)/zeta(2)), where gamma is Euler's constant (A001620). (End)

A061345 Powers of odd primes. Alternatively, 1 and the odd prime powers (p^k, p an odd prime, k >= 1).

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 13, 17, 19, 23, 25, 27, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239

Offset: 0

N. J. A. Sloane, Jun 08 2001

Let a(n)=p^e, then tau(a(n)^2) = tau(p^(2*e)) = 2*e+1 = 2*(e+1)-1 = tau(2*a(n))-1 where tau=A000005. - Juri-Stepan Gerasimov, Jul 14 2011

For n > 0, also the allowed indices of a Cossidente-Penttila graph. - Eric W. Weisstein, Feb 24 2025

Robert Israel, Table of n, a(n) for n = 0..10000
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]
Eric Weisstein's World of Mathematics, Odd Prime Power.

Cf. A061346, A000961, A005408, A061344, A075109, A075110.

[1] cat [n: n in [3..300 by 2] | IsPrimePower(n)]; // Bruno Berselli, Feb 25 2016

select(t -> nops(ifactors(t)[2])<=1, [seq(2*i+1,i=0..1000)]); # Robert Israel, Jun 11 2014
# alternative:
A061345 := proc(n)
    option remember;
    local k ;
    if n = 0 then
        1;
    else
        for k from procname(n-1)+2 by 2 do
            if nops(numtheory[factorset](k)) = 1 then
                return k ;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, Jun 25 2016
isOddPrimepower := n -> type(n, 'primepower') and not type(n, 'even'):
A061345List := up_to -> select(isOddPrimepower, [`$`(1..up_to)]):
A061345List(240); # Peter Luschny, Feb 02 2023

t={1};k=0;Do[If[k==1,AppendTo[t,a1]];k=0;Do[c=Sqrt[a^2+b^2];If[IntegerQ[c]&&GCD[a,b,c]==1,k++;a1=a;b1=b;c1=c;],{b,4,a^2/2,2}],{a,3,260,2}];t (* Vladimir Joseph Stephan Orlovsky, Jan 29 2012 *)
Select[2 Range@ 130 - 1, PrimeNu@# < 2 &] (* Robert G. Wilson v, Jun 12 2014 *)
Join[{1}, Select[Range[1, 200, 2], PrimePowerQ]] (* Eric W. Weisstein, Feb 23 2025 *)

is(n)=my(p); if(isprimepower(n,&p), p>2, n==1) \\ Charles R Greathouse IV, Jun 08 2016

from sympy import primepi, integer_nthroot
def A061345(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-sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length())))
    return bisection(f,n+1,n+1) # Chai Wah Wu, Feb 03 2025

a(n) = A061344(n)-1.

Intersection of A000961 (prime powers) and A005408 (odd numbers). - Robert Israel, Jun 11 2014

More terms from Larry Reeves (larryr(AT)acm.org), Jun 12 2001

A033949 Positive integers that do not have a primitive root.

Original entry on oeis.org

8, 12, 15, 16, 20, 21, 24, 28, 30, 32, 33, 35, 36, 39, 40, 42, 44, 45, 48, 51, 52, 55, 56, 57, 60, 63, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 84, 85, 87, 88, 90, 91, 92, 93, 95, 96, 99, 100, 102, 104, 105, 108, 110, 111, 112, 114, 115, 116, 117, 119, 120, 123

Offset: 1

Calculated by Jud McCranie

nonn

Numbers k such that the cyclotomic polynomial Phi(k,x) is reducible over Zp for all primes p. Harrison shows that this is equivalent to k > 2 and the discriminant of Phi(k,x), A004124(k), being a square. - T. D. Noe, Nov 06 2007
The multiplicative group modulo k is non-cyclic; the complement A033948. - Wolfdieter Lang, Mar 14 2012. See A281854 for the groups. - Wolfdieter Lang, Feb 04 2017
Numbers k with the property that there exists a positive integer m with 1 < m < k-1 and m^2 == 1 (mod k). - Reinhard Muehlfeld, May 27 2014
Also, numbers k for which A000010(k) > A002322(k), or equivalently A034380(k) > 1. - Ivan Neretin, Mar 28 2015
Numbers k of the form a + b + 2*sqrt(a*b + 1) for positive integers a,b such that a*b + 1 is a square. Proof: If 1 < m < k - 1 and m^2 == 1 (mod k), take a = (m^2 - 1)/k and b = ((k - m)^2 - 1)/k. Conversely, if k = a + b + 2*sqrt(a*b + 1), take m = a + sqrt(a*b + 1). - Tor Gunston, Apr 24 2021
Seems to be A050275 without the duplicates. - Charles R Greathouse IV, Feb 09 2025

I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers, 4th edition, page 62, Theorem 2.25.

T. D. Noe, Table of n, a(n) for n = 1..10000
Brett A. Harrison, On the reducibility of cyclotomic polynomials over finite fields, Amer. Math. Monthly, Vol 114, No. 9 (2007), 813-818.
Eldar Sultanow, Christian Koch, and Sean Cox, Collatz Sequences in the Light of Graph Theory, Universität Potsdam (Germany, 2020).
Wikipedia, Primitive root modulo n

Cf. A000010, A002322, A033948 (complement), A193305 (composites with primitive root).

Column k=1 of A277915, A281854.

a033949 n = a033949_list !! (n-1)
a033949_list = filter
               (\x -> any ((== 1) . (`mod` x) . (^ 2)) [2 .. x-2]) [1..]
-- Reinhard Zumkeller, Dec 10 2014

m := proc(n) local k, r; r := 1; if n = 2 then return false fi;
for k from 1 to n do if igcd(n,k) = 1 then r := modp(r*k,n) fi od; r end:
select(n -> m(n) = 1, [$1..123]); # Peter Luschny, May 25 2017

Select[Range[2,130],!IntegerQ[PrimitiveRoot[#]]&] (* Harvey P. Dale, Oct 25 2011 *)
a[n_] := Module[{j, l = {}}, While[Length[l] CarmichaelLambda[j], AppendTo[l, j]; Break[]]]]; l[[n]]]; Array[a, 100] (* Jean-François Alcover, May 29 2018, after Alois P. Heinz's Maple code for A277915 *)

is(n)=n>7 && (!isprimepower(if(n%2,n,n/2)) || n>>valuation(n,2)==1) \\ Charles R Greathouse IV, Oct 08 2016

from itertools import count, islice
from sympy.ntheory import sqrt_mod_iter
def A033949_gen(): # generator of terms
    return filter(lambda n:max(filter(lambda k:k 1,count(3))
A033949_list = list(islice(A033949_gen(),30)) # Chai Wah Wu, Oct 26 2022

from sympy import primepi, integer_nthroot
def A033949(n):
    def f(x): return int(n+1+(x>=2)+(x>=4)+sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length()))+sum(primepi(integer_nthroot(x>>1,k)[0])-1 for k in range(1,x.bit_length()-1)))
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Feb 24 2025

[n for n in range(1,100) if not Integers(n).multiplicative_group_is_cyclic()]
# Ralf Stephan, Mar 30 2014

Positive integers except 1, 2, 4 and numbers of the form p^i and 2p^i, where p is an odd prime and i >= 1.

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.

Original entry on oeis.org

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

A167791 Numbers with primitive root 2.

Original entry on oeis.org

3, 5, 9, 11, 13, 19, 25, 27, 29, 37, 53, 59, 61, 67, 81, 83, 101, 107, 121, 125, 131, 139, 149, 163, 169, 173, 179, 181, 197, 211, 227, 243, 269, 293, 317, 347, 349, 361, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619

Offset: 1

T. D. Noe, Nov 12 2009

nonn

Numbers k such that the binary expansion of 1/k has period phi(k). For example 1/27 has a period of 18 bits.
All entries are odd. An odd composite number n can have a primitive root if and only if it is a prime power (see A033948). - V. Raman, Oct 04 2012
It is unknown whether there is a prime p such that p is in this sequence while p^2 is not. - Jianing Song, Jan 27 2019

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Vincenzo Librandi)

Cf. A000010, A001122 (primes with primitive root 2), A033948.

[n: n in [3..619] | IsPrimitive(2, n)]; // Arkadiusz Wesolowski, Dec 22 2020

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

for(n=3,200,if(n%2==1&&znorder(Mod(2,n))==eulerphi(n),printf(n","))) \\ V. Raman, Oct 04 2012

is(n)=n%2 && isprimepower(n) && znorder(Mod(2,n))==eulerphi(n-1) \\ Charles R Greathouse IV, Jul 05 2013

A034380 Ratio of totient to Carmichael's lambda function: a(n) = A000010(n) / A002322(n).

Original entry on oeis.org

1, 1, 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, 6, 2, 4, 2, 1, 2, 2, 2, 1, 4, 1, 1, 2, 2, 2, 2, 1, 8, 1, 1, 1, 4, 4, 1, 2, 4, 1, 2, 6, 2, 2, 1, 2, 4, 1, 1, 2, 2, 1, 2, 1, 4, 4

Offset: 1

Alex Fink

nonn

a(n)=1 if and only if the multiplicative group modulo n is cyclic (that is, if n is either 1, 2, 4, or of the form p^k or 2*p^k where p is an odd prime). In other words: a(n)=1 if n is a term of A033948, otherwise a(n) > 1 (and n is a term of A033949). - Joerg Arndt, Jul 14 2012

T. D. Noe, Table of n, a(n) for n = 1..10000
W. D. Banks and F. Luca, On integers with a special divisibility property, Archivum Mathematicum (BRNO) 42 (2006) pp 31-42.

Cf. A000010, A002322, A033948, A033949, A062373-A062377, A080400, A289624.

a034380 n = a000010 n `div` a002322 n
-- Reinhard Zumkeller, Sep 02 2014

[1] cat [EulerPhi(n) div CarmichaelLambda(n): n in [2..100]]; // Vincenzo Librandi, Jul 18 2017

Maple
```
A034380 := n-> phi(n) / lambda(n);
```

Table[EulerPhi[n]/CarmichaelLambda[n], {n, 1, 200}] (* Geoffrey Critzer, Dec 23 2014 *)

eulerphi(n)/lcm(znstar(n)[2]) \\ Charles R Greathouse IV, Feb 01 2013

a(n) = A000010(n) / A002322(n).
a(A033948(n)) = 1 [Banks & Luca]. - R. J. Mathar, Jul 29 2007
A002322(n)/A007947(a(n)) = A289624(n). - Antti Karttunen, Jul 17 2017

cp's OEIS Frontend

A306252 Least primitive root mod A033948(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A306253 Largest primitive root mod A033948(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A255979 a(n) = smallest nonnegative integer solution z to the system of congruences: z == 0 (mod n), z == 1 (mod A038610(n)) if n is in A033948; or z == 0 (mod n), z == -1 (mod A038610(n)) if n is in A033949.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A060594 Number of solutions to x^2 == 1 (mod n), that is, square roots of unity modulo n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Sage

Formula

A061345 Powers of odd primes. Alternatively, 1 and the odd prime powers (p^k, p an odd prime, k >= 1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A033949 Positive integers that do not have a primitive root.

Views