A002233 a(1) = 1; for n > 1, a(n) = least positive prime primitive root of n-th prime.

1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 7, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 11, 3, 3, 2, 3, 2, 2, 7, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 7, 3, 7, 7, 11, 3, 5, 2, 43, 5, 3, 3, 2, 5, 17, 17, 2, 3, 19, 2, 2, 3, 7, 11, 2, 2, 5, 2, 5, 3, 29, 2, 2, 7, 5, 17, 2, 3, 13, 2, 3, 2, 13, 3, 2, 7, 5, 2, 3, 2, 2, 2

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

According to Section F9 in Guy's book "Unsolved Problems in Number Theory" (Springer, 2004), P. Erdős asked whether for any large prime p there is a prime q < p so that q is a primitive root modulo p. See also the comments on A223942 related to this sequence. - Zhi-Wei Sun, Mar 29 2013

For n >= 2 the Dirichlet characters modulo prime(n), {Chi_{prime n}{(r,m)}, for n >= 1, r=1..(prime(n)-1) and m = 2..prime(n)-1, are determined from those for m = a(n), i.e., Chi_{prime n}(r,a(n)) = exp(2*Pi*I*(r-1)/(prime(n)-1)) and the power sequence S(n) := {a(n)^k (mod prime(n)), k = 1..(prime(n)-2)} by the strong multiplicity of Chi as Chi_{prime n}(r,m) = (Chi_{prime n}(r,a(n)))^{pos(m,S(n))} where S(n){pos(m,S(n))} = m. For m=1 Chi is always 1. For m = prime(n) Chi is always 0. For n=1 (prime 2) the characters are 1, 0 for r = 1 and m = 1, 2, respectively. See the example for a(4) below. - _Wolfdieter Lang, Jan 19 2017

Examples

			n=4, a(4) = 3: Dirichlet characters for prime(4) = 7 from Chi_7(r,3) = exp(Pi*I*(r-1)/3) and the power sequence S(4) = [3, 2, 6, 4, 5]. Hence Chi_7(r,2) = Chi_7(r,3)^2 = exp(2*Pi*I*(r-1)/3), Chi_7(r,4) = Chi_7(r,3)^4, Chi_7(r,5) = Chi_7(r,3)^5, Chi_7(r,6) = Chi_7(r,3)^3. Chi_7(r,1) = 1 and Chi_7(r,7) = 0, for r=1..6. This produces the character modulo 7 table. See the Apostol reference, p. 139, with interchanged rows r = 2..6. - _Wolfdieter Lang_, Jan 19 2017
		

References

• T. M. Apostol, An Introduction to Analytic Number Theory, Springer-Verlag, NY, 1976, 1986, p. 139.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• A. E. Western and J. C. P. Miller, Tables of Indices and Primitive Roots. Royal Society Mathematical Tables, Vol. 9, Cambridge Univ. Press, 1968, p. 2.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• A. E. Western and J. C. P. Miller, Tables of Indices and Primitive Roots, Royal Society Mathematical Tables, Vol. 9, Cambridge Univ. Press, 1968 [Annotated scans of selected pages]

Crossrefs

See A122028 (least primitive root that is prime), A001918 (least positive primitive root), A223942.

Programs

Mathematica

a[1] = 1; a[n_] := (p = Prime[n]; Select[Range[p], PrimeQ[#] && MultiplicativeOrder[#, p] == EulerPhi[p] &, 1]) // First; Table[a[n], {n, 100}] (* Jean-François Alcover, Mar 30 2011 *)
a[1] = 1; a[n_] := SelectFirst[PrimitiveRootList[Prime[n]], PrimeQ]; Array[a, 101] (* Jean-François Alcover, Sep 28 2016 *)

PARI

leastroot(p)=forprime(q=2,p,if(znorder(Mod(q,p))+1==p,return(q)))
a(n)=if(n>1,leastroot(prime(n)),1) \\ Charles R Greathouse IV, Mar 20 2013

Formula

a(n) = A122028(n) for n>1. - Jonathan Sondow, May 18 2017