A046145 -id:A046145 - cp's OEIS frontend

A103335 Numbers whose smallest primitive root (A046145) is not prime.

1, 2, 41, 109, 151, 229, 251, 271, 313, 337, 362, 367, 409, 439, 542, 626, 674, 733, 761, 818, 878, 971, 991, 1021, 1031, 1069, 1289, 1297, 1303, 1429, 1471, 1489, 1681, 1759, 1783, 1789, 1811, 1871, 1873, 1879, 2062, 2137, 2342, 2411, 2441, 2551, 2594

Offset: 1

Harry J. Smith, Jan 31 2005

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A046146, A103309, A103310, A103336, A103337, A103338.

filter:= proc(n)
  local r;
  r:= numtheory:-primroot(n);
  r <> FAIL and not isprime(r)
end proc:
filter(1):= true:
select(filter, [$1..3000]); Robert Israel, Sep 08 2020

L = {}; Do[ If[!PrimeQ[ Min[ Select[ Range[n], CoprimeQ[#, n] && MultiplicativeOrder[#, n] == CarmichaelLambda[n] &]]],
L = Append[L, n]], {n, 1, 3000}]; L (* Jonathan Sondow, May 17 2017 *)

Offset changed by Robert Israel, Sep 08 2020

A285513 Numbers k such that A285512(k) < A046145(k).

Original entry on oeis.org

26, 41, 82, 103, 109, 151, 157, 191, 229, 251, 271, 277, 302, 311, 313, 337, 338, 362, 367, 382, 397, 409, 439, 457, 499, 542, 622, 626, 643, 674, 683, 733, 761, 769, 818, 842, 878, 911, 914, 919, 967, 971, 991, 998, 1021, 1031

Offset: 1

Max Alekseyev, Apr 20 2017

nonn

If A046145(k) > 0, we have A285512(k) <= A046145(k). This sequence lists the values of k that produce a strict inequality (cf. A285514).

Cf. A046145 A285512, A285514.

A285514 Numbers k such that A285512(k) = A046145(k).

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 27, 29, 31, 34, 37, 38, 43, 46, 47, 49, 50, 53, 54, 58, 59, 61, 62, 67, 71, 73, 74, 79, 81, 83, 86, 89, 94, 97, 98, 101, 106, 107, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 142, 146, 149, 158, 162, 163, 166, 167, 169, 173, 178, 179

Offset: 1

Max Alekseyev, Apr 20 2017

nonn

If A046145(k) > 0, we have A285512(k) <= A046145(k). This sequence lists the values of k that produce an equality.

Cf. A046145, A285512, A285513.

A046144 Number of primitive roots modulo n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0, 0, 0, 0, 24, 0, 18, 16, 40, 0, 0, 12, 0, 0, 40, 0, 0

Offset: 1

Eric W. Weisstein

nonn

T. D. Noe, Table of n, a(n) for n = 1..10000
S. R. Finch, Idempotents and Nilpotents Modulo n, arXiv:math/0605019 [math.NT], 2006-2017.
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A010554, A033949, A046145, A046146, A008330, A002233, A071894, A219027.

A046144 := proc(n)
    local a,eulphi,m;
    if n = 1 then
        return 1;
    end if;
    eulphi := numtheory[phi](n) ;
    a := 0 ;
    for m from 0 to n-1 do
        if numtheory[order](m,n) = eulphi then
            a := a + 1 ;
        end if;
    end do:
    a;
end proc: # R. J. Mathar, Jan 12 2016

Prepend[ Table[ If[ IntegerQ[ PrimitiveRoot[n]] , EulerPhi[ EulerPhi[n]], 0], {n, 2, 91}],1] (* Jean-François Alcover, Sep 13 2011 *)

for(i=1, 100, p=0; for(q=1, i, if(gcd(q,i)==1 && znorder(Mod(q,i)) == eulerphi(i), p++)); print1(p, ", ")) /* V. Raman, Nov 22 2012 */

a(n) = my(s=znstar(n)); if(#(s.cyc)>1, 0, eulerphi(s.no)) \\ Jeppe Stig Nielsen, Oct 18 2019

use ntheory ":all"; my @A = map { !defined znprimroot($) ? 0 : euler_phi(euler_phi($)); } 0..10000; say "$ $A[$]" for 1..$#A; # Dana Jacobsen, Apr 28 2017

a(n) is equal to A010554(n) unless n is a term of A033949, in which case a(n)=0.

A046146 Largest primitive root modulo n, or 0 if no root exists.

Original entry on oeis.org

0, 0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, 5, 0, 0, 14, 11, 15, 0, 0, 19, 21, 0, 23, 19, 23, 0, 27, 0, 24, 0, 0, 31, 0, 0, 35, 33, 0, 0, 35, 0, 34, 0, 0, 43, 45, 0, 47, 47, 0, 0, 51, 47, 0, 0, 0, 55, 56, 0, 59, 55, 0, 0, 0, 0, 63, 0, 0, 0, 69, 0, 68, 69, 0, 0, 0, 0, 77, 0, 77, 75, 80, 0, 0

Offset: 0

Eric W. Weisstein

nonn

The value 0 at index 0 says 0 has no primitive roots, but the 0 at index 1 says 1 has a primitive root of 0, the only real 0 in the sequence. - Initial terms corrected by Harry J. Smith, Jan 27 2005

a(n) is nonzero if and only if n is 2, 4, or of the form p^k, or 2*p^k where p is an odd prime and k>0. - Tom Edgar, Jun 02 2014

T. D. Noe, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A002233, A071894, A219027, A008330, A010554.

f[n_] := Block[{pr = PrimitiveRootList[n]}, If[pr == {}, 0, pr[[-1]]]]; Array[f, 86, 0] (* Robert G. Wilson v, Nov 03 2014 *)

for(i=0,100,p=0;for(q=1,i-1,if(gcd(q,i)==1&&znorder(Mod(q,i))==eulerphi(i),p=q));print1(p",")) /* V. Raman, Nov 22 2012 */

Initial terms corrected by Harry J. Smith, Jan 27 2005

A055578 "Non-generous primes": primes p whose least positive primitive root is not a primitive root of p^2.

Original entry on oeis.org

2, 40487, 6692367337

Offset: 1

Bernard Leak (bernard(AT)brenda-arkle.demon.co.uk), Aug 24 2000

For r a primitive root of a prime p, r + qp is a primitive root of p: but r + qp is also a primitive root of p^2, except for q in some unique residue class modulo p. In the exceptional case, r + qp has order p-1 modulo p^2 (Burton, section 8.3).
No other terms below 10^12 (Paszkiewicz, 2009).
Each term p is a Wieferich prime to base A046145(p). For example, a(2) and a(3) are base-5 Wieferich (see A123692). - Jeppe Stig Nielsen, Mar 06 2020

David Burton, Elementary Number Theory, Allyn and Bacon, Boston, 1976, first edition (cf. Section 8.3).

Joerg Arndt, Matters Computational (The Fxtbook), section 39.7.2, p.780.
Stephen Glasby, Three questions about the density of certain primes, Posting to Number Theory List (NMBRTHRY(AT)LISTSERV.NODAK.EDU), Apr 22, 2001.
Bryce Kerr, Kevin McGown, Tim Trudgian, The least primitive root modulo p^2, arXiv:1908.11497 [math.NT], 2019.
A. Paszkiewicz, A new prime for which the least primitive root (mod p) and the least primitive root (mod p^2) are not equal, Math. Comp. 78 (2009), 1193-1195.

Cf. A060503, A060504.

Select[Prime@Range[7!], ! PrimitiveRoot[#] == PrimitiveRoot[#^2] &] (* Arkadiusz Wesolowski, Sep 06 2012 *)

Prime A000040(n) is in this sequence iff A001918(n)^(A000040(n)-1) == 1 (mod A000040(n)^2).

Prime A000040(n) is in this sequence iff A001918(n) differs from A127807(n).

a(3) from Stephen Glasby (Stephen.Glasby(AT)cwu.EDU), Apr 22 2001

Edited by Max Alekseyev, Nov 10 2011

A111076 Smallest positive number of maximal order mod n.

Original entry on oeis.org

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

Offset: 1

Franklin T. Adams-Watters, Oct 10 2005

			a(6)=5 because order of 1 is 1 and 2 through 4 are not relatively prime to 6, but 5 has order 2, which is the maximum possible.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A002322 (orders); same as A046145 for n with primitive roots; see also A001918 (for primes), A229708.

Table[Min[
  Select[Range[n],
   CoprimeQ[#, n] &&
     MultiplicativeOrder[#, n] == CarmichaelLambda[n] &]], {n, 1, 100}]
(* Geoffrey Critzer, Jan 04 2015 *)

a(n)=if(n==1, return(1)); if(n<5,return(n-1)); my(o=lcm(znstar(n)[2]),k=1); while(gcd(k++,n)>1 || znorder(Mod(k,n))Charles R Greathouse IV, Jul 31 2013

a(n) = A229708(n) if and only if a(n) is prime. - Jonathan Sondow, May 17 2017

A046147 Triangle read by rows in which row n lists the primitive roots mod n (omitting numbers n without a primitive root).

Original entry on oeis.org

1, 2, 3, 2, 3, 5, 3, 5, 2, 5, 3, 7, 2, 6, 7, 8, 2, 6, 7, 11, 3, 5, 3, 5, 6, 7, 10, 11, 12, 14, 5, 11, 2, 3, 10, 13, 14, 15, 7, 13, 17, 19, 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 2, 3, 8, 12, 13, 17, 22, 23, 7, 11, 15, 19, 2, 5, 11, 14, 20, 23, 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26

Offset: 2

Eric W. Weisstein

			n followed by primitive roots, if any:
1 -
2 1
3 2
4 3
5 2 3
6 5
7 3 5
8 -
9 2 5
10 3 7
11 2 6 7 8
12 -
13 2 6 7 11
...

T. D. Noe, Table of n, a(n) for n = 2..3119 (first 99 nonempty rows of triangle, flattened)
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144 (row lengths), A046145, A046146.

Cf. A060749, A306252 (1st column), A306253 (last/maximum element)

f:= proc(n) local p,k,m,R;
     p:= numtheory:-primroot(n);
     if p = FAIL then return NULL fi;
     m:= numtheory:-phi(n);
     k:= select(i -> igcd(i,m) = 1, [$1..m-1]);
     op(sort(map(t -> p&^t mod n, k)))
end proc:
f(2):= 1:
map(f, [$2..50]); # Robert Israel, Apr 28 2017

a[n_] := Select[Range[n-1], GCD[#, n] == 1 && MultiplicativeOrder[#, n] == EulerPhi[n]& ]; Table[a[n], {n, 1, 30}] // Flatten (* Jean-François Alcover, Oct 23 2012 *)
PrimitiveRootList[Range[Prime[10]]]//Flatten (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Sep 10 2016 *)

a_row(r) = my(v=[], phi=eulerphi(r)); for(i=1, r-1, if(1 == gcd(r, i) && phi == znorder(Mod(i, r)), v=concat(v, i))); v \\ Ruud H.G. van Tol, Oct 23 2023

Edited by Robert Israel, Apr 28 2017

A103309 Smallest prime primitive root of n that is less than n, or 0 if none exists.

Original entry on oeis.org

0, 0, 0, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 7, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 5, 0, 0, 5, 3, 0, 0, 2, 0, 5, 0

Offset: 0

Harry J. Smith, Jan 29 2005

Differs from A046145 only for indices n = 2, 41, 109, 151, 229, ...; see A103335. - Jeppe Stig Nielsen, Mar 06 2020

Robert Israel, Table of n, a(n) for n = 0..10000
G. Martin, The Least Prime Primitive Root and the Shifted Sieve, Acta Arith. 80 (1997), no. 3, 277-288; arXiv:math/9807104 [math.NT], 1998.
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A046146, A103310, A103335.

F:= proc(n)
  local r;
  r:= numtheory:-primroot(n);
  while r::integer and not isprime(r) do
    r:= numtheory:-primroot(r,n);
  od:
  if r = FAIL then 0 else r fi
end proc:
seq(F(n),n=0..200); # Robert Israel, May 18 2015

a[n_] := SelectFirst[PrimitiveRootList[n], PrimeQ[#] && # < n&] /. Missing["NotFound"] -> 0;
Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Nov 15 2017 *)

A103310 Largest prime primitive root of n that is less than n, or 0 if none exists.

Original entry on oeis.org

0, 0, 0, 2, 3, 3, 5, 5, 0, 5, 7, 7, 0, 11, 5, 0, 0, 11, 11, 13, 0, 0, 19, 19, 0, 23, 19, 23, 0, 19, 0, 17, 0, 0, 31, 0, 0, 19, 29, 0, 0, 29, 0, 29, 0, 0, 43, 43, 0, 47, 47, 0, 0, 41, 47, 0, 0, 0, 47, 47, 0, 59, 53, 0, 0, 0, 0, 61, 0, 0, 0, 67, 0, 59, 61, 0, 0, 0, 0, 59, 0, 59, 71, 79, 0, 0, 73

Offset: 0

Harry J. Smith, Jan 29 2005

Robert Israel, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046145, A046146, A103309.

hasproot:= proc(n)
  if n::odd then nops(numtheory:-factorset(n))=1
  else padic:-ordp(n,2)=1 and nops(numtheory:-factorset(n/2))=1
  fi
end proc;
hasproot(2):= true: hasproot(4):= true:
f:= proc(n) local p,t;
  if not hasproot(n) then return 0 fi;
  t:= numtheory:-phi(n);
  p:= prevprime(n);
  while not numtheory:-order(p,n)=t do
    if p = 2 then return 0 fi;
    p:= prevprime(p);
  od;
  p
end proc:
f(0):= 0: f(1):= 0: f(2):= 0:
map(f, [$0..100]); # Robert Israel, Sep 08 2020

a[n_] := Module[{R = PrimitiveRootList[n], s}, s = Select[R, # < n && PrimeQ[#]&]; If[s == {}, 0, s[[-1]]]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 01 2023 *)

cp's OEIS Frontend

A103335 Numbers whose smallest primitive root (A046145) is not prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A285513 Numbers k such that A285512(k) < A046145(k).

Views

Author

Keywords

Comments

Crossrefs

A285514 Numbers k such that A285512(k) = A046145(k).

Views

Author

Keywords

Comments

Crossrefs

A046144 Number of primitive roots modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Perl

Formula

A046146 Largest primitive root modulo n, or 0 if no root exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A055578 "Non-generous primes": primes p whose least positive primitive root is not a primitive root of p^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A111076 Smallest positive number of maximal order mod n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A046147 Triangle read by rows in which row n lists the primitive roots mod n (omitting numbers n without a primitive root).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica