A046146 -id:A046146 - cp's OEIS frontend

A103336 Numbers whose largest primitive root (A046146) is not prime.

1, 2, 11, 17, 19, 23, 29, 31, 37, 38, 41, 43, 47, 53, 58, 59, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 101, 107, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 146, 149, 151, 157, 158, 162, 163, 167, 173, 178, 179, 191, 193, 194, 197, 211, 218, 223

Offset: 1

Harry J. Smith, Jan 31 2005

nonn

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

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

Select[Range[250], #==1 || ((p = PrimitiveRootList[#]) != {} && ! PrimeQ[Max @ p]) &] (* Amiram Eldar, Sep 25 2021 *)

Offset corrected by Amiram Eldar, Sep 25 2021

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.

A046145 Smallest primitive root modulo n, or 0 if no root exists.

Original entry on oeis.org

0, 0, 1, 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, 6, 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

Offset: 0

Eric W. Weisstein

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.

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
Pēteris K. Siliņš, Cross ratios for finite field geometries, Bachelor's Thesis, Univ. Groningen (Netherlands, 2024). See p. 17.
Eric Weisstein's World of Mathematics, Primitive Root.

Cf. A001918, A046144, A046146, A002233, A071894, A219027, A008330, A010554, A111076, A285512, A285513, A285514.

A046145 := proc(n)
  if n <=1 then
    0;
  else
    pr := numtheory[primroot](n) ;
    if pr = FAIL then
       return 0 ;
    else
       return pr ;
    end if;
  end if;
end proc:
seq(A046145(n),n=0..110) ;  # R. J. Mathar, Jul 08 2010

smallestPrimitiveRoot[n_ /; n <= 1] = 0; smallestPrimitiveRoot[n_] := Block[{pr = PrimitiveRoot[n], g}, If[! NumericQ[pr], g = 0, g = 1; While[g <= pr, If[ CoprimeQ[g, n] && MultiplicativeOrder[g, n] == EulerPhi[n], Break[]]; g++]]; g]; smallestPrimitiveRoot /@ Range[0, 100] (* Jean-François Alcover, Feb 15 2012 *)
f[n_] := Block[{pr = PrimitiveRootList[n]}, If[pr == {}, 0, pr[[1]]]]; Array[f, 105, 0] (* v10.0 Robert G. Wilson v, Nov 04 2014 *)

{ A046145(n) = for(q=1,n-1, if(gcd(q,n)==1 && znorder(Mod(q,n))==eulerphi(n), return(q);)); 0; } /* V. Raman, Nov 22 2012, edited by Max Alekseyev, Apr 20 2017 */

use ntheory ":all"; say "$ ", znprimroot($) || 0  for 0..100; # Dana Jacobsen, Mar 16 2017

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

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 *)

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

Original entry on oeis.org

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

A103337 Smallest primitive root of numbers in sequence A103335.

Original entry on oeis.org

0, 1, 6, 6, 6, 6, 6, 6, 10, 10, 21, 6, 21, 15, 15, 15, 15, 6, 6, 21, 15, 6, 6, 10, 14, 6, 6, 10, 6, 6, 6, 14, 6, 6, 10, 6, 6, 14, 10, 6, 21, 10, 35, 6, 6, 6, 15, 6, 6, 10, 21, 14, 6, 33, 6, 6, 10, 6, 6, 6, 10, 6, 22, 15, 15, 6, 10, 12, 6, 15, 15, 10, 14, 21, 6, 15, 6, 6, 6, 6, 6, 6, 6, 10, 10, 6

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, A103335, A103336, A103338.

# given list A103335 as at that sequence
[0,seq(numtheory:-primroot(A103335[i]),i=2..nops(A103335))]; # Robert Israel, Sep 08 2020

Offset changed by Robert Israel, Sep 08 2020

A103338 Largest primitive root of numbers in sequence A103336.

Original entry on oeis.org

0, 1, 8, 14, 15, 21, 27, 24, 35, 33, 35, 34, 45, 51, 55, 56, 55, 63, 69, 68, 69, 77, 77, 75, 80, 77, 86, 91, 92, 99, 104, 110, 115, 117, 115, 123, 118, 128, 117, 134, 135, 141, 147, 146, 152, 153, 155, 159, 165, 171, 175, 176, 189, 188, 189, 195, 207, 207, 214

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, A103335, A103336, A103337.

f:= proc(n) local m; uses NumberTheory;
  if n::odd then
    if NumberOfPrimeFactors(n,distinct) > 1 then return NULL fi;
  elif n mod 4 = 0 or NumberOfPrimeFactors(n,distinct) > 2 then return NULL
  fi;
  m:= PrimitiveRoot(n, ith=Totient(Totient(n)));
  if isprime(m) then NULL else m fi
end proc:
f(1):= 0:map(f, [$1..300]); # Robert Israel, Dec 01 2024

Offset changed by Robert Israel, Dec 01 2024

A247176 Largest number of maximal order mod n.

Original entry on oeis.org

0, 1, 2, 3, 3, 5, 5, 7, 5, 7, 8, 11, 11, 5, 13, 13, 14, 11, 15, 17, 19, 19, 21, 23, 23, 19, 23, 23, 27, 23, 24, 29, 29, 31, 33, 31, 35, 33, 37, 37, 35, 31, 34, 41, 43, 43, 45, 43, 47, 47, 46, 45, 51, 47, 53, 53, 53, 55, 56, 53, 59, 55, 61, 61, 63, 61, 63, 65, 67, 67, 69, 67

Offset: 1

Eric Chen, Nov 29 2014

			a(18) = 11 because the largest possible order mod 18 is 6, and because 16, 15, 14, and 12 are not coprime to 18, and the orders of 17 and 13 to mod 18 are 2 and 3, not the largest possible order, and the order of 11 to mod 18 is 6, so a(18) = 11.

Eric Chen, Table of n, a(n) for n = 1..1000

Cf. A002322 (orders), same as A046146 for n with primitive roots, A071894 (for primes).

Cf. A111076, A111725, A046145, A046144, A001918, A008330.

prms={}; f[n_] = Block[If[MultiplicativeOrder[p, n]=CarmichaelLambda[n], Join[prms, p]]; prms[-1]]; Array[f, 128]

carmichaellambda(n)=lcm(znstar(n)[2]);
for(i=1, 128, p=0; for(q=1, i-1, if(gcd(q, i)==1&&znorder(Mod(q, i))==carmichaellambda(i), p=q)); print1(p", "))

a(68) corrected by Eric Chen, Jun 01 2015

cp's OEIS Frontend

A103336 Numbers whose largest primitive root (A046146) is not prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A046144 Number of primitive roots modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Perl

Formula

A046145 Smallest primitive root modulo n, or 0 if no root exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Perl

Extensions

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

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A103337 Smallest primitive root of numbers in sequence A103335.

Views

Author