A002223 -id:A002223 - cp's OEIS frontend

A002229 Primitive roots that go with the primes in A002230.

1, 2, 3, 5, 6, 7, 19, 21, 23, 31, 37, 38, 44, 69, 73, 94, 97, 101, 107, 111, 113, 127, 137, 151, 164, 179, 194, 197, 227, 229, 263, 281, 293, 335, 347, 359, 401, 417

Offset: 1

N. J. A. Sloane

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

R. K. Guy and N. J. A. Sloane, Correspondence, 1988.
Kevin J. McGown and Jonathan P. Sorenson, Computation of the least primitive root, arXiv:2206.14193 [math.NT], 2022.
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]

Cf. A002230.

s = {1}; rm = 1; Do[p = Prime[k]; r = PrimitiveRoot[p]; If[r > rm, Print[r]; AppendTo[s, r]; rm = r], {k, 10^6}]; s (* Jean-François Alcover, Apr 05 2011 *)

from sympy import isprime, primitive_root
from itertools import count, islice
def f(n): return 0 if not isprime(n) or (r:=primitive_root(n))==None else r
def agen(r=0): yield from ((m, r:=f(m))[1] for m in count(1) if f(m) > r)
print(list(islice(agen(), 15))) # Michael S. Branicky, Feb 13 2023

More terms from Scott Lindhurst (ScottL(AT)alumni.princeton.edu)

a(35)-a(38), from McGown and Sorenson, added by Michel Marcus, Jun 29 2022

A060363 Smallest prime p such that first n primes (p_1=2, ..., p_n) are 13th power residues mod p.

Original entry on oeis.org

4421, 44851, 1194961, 2367691, 138609979, 820015717, 72942989237, 72942989237

Offset: 1

N. J. A. Sloane, Apr 03 2001

nonn

No more terms through 10^11. - Don Reble, Oct 12 2001

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

Cf. A002223-A002228, A060364.

More terms from Don Reble, Oct 12 2001

A060364 Smallest prime p such that first n primes (p_1=2, ..., p_n) are 17th power residues mod p.

Original entry on oeis.org

1429, 6563, 1458601, 55981069, 250844317, 4926746609, 225578509837, 1118584849397, 4143277702703

Offset: 1

N. J. A. Sloane, Apr 03 2001

nonn

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

Cf. A002223-A002228, A060363.

More terms from Don Reble, Oct 12 2001. Search limit 10^11. Corrected Nov 14 2006

a(7)-a(9) from Sergey Paramonov, Apr 14 2024

A147969 Smallest prime p modulo which numbers 1,2,...,n are quadratic residues.

Original entry on oeis.org

2, 7, 23, 23, 71, 71, 311, 311, 311, 311, 479, 479, 1559, 1559, 1559, 1559, 5711, 5711, 10559, 10559, 10559, 10559, 18191, 18191, 18191, 18191, 18191, 18191, 31391, 31391, 366791, 366791, 366791, 366791, 366791, 366791, 366791, 366791, 366791

Offset: 1

Max Alekseyev, Nov 18 2008

nonn

The same primes without repetitions are listed in A147970.

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

Cf. A000229, A002223, A002224, A045535, A053760, A133435, A147970, A147971.

a(n)=forprime(p=2,default(primelimit),forprime(i=2,n, if(kronecker(i,p)<1,next(2)));return(p)) \\ Charles R Greathouse IV, Apr 06 2012

A147970 Primes corresponding to the records in the sequence of smallest positive quadratic nonresidues (A053760).

Original entry on oeis.org

2, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 3818929, 9257329, 22000801, 36415991, 48473881, 120293879, 131486759, 2929911599, 7979490791, 23616331489, 89206899239, 121560956039, 196265095009, 513928659191, 5528920734431, 8402847753431, 70864718555231

Offset: 1

Max Alekseyev, Nov 18 2008

nonn

Cf. A000229, A002223, A002224, A045535, A053760, A133435, A147969, A147971.

Prime p=A000040(n) is in this sequence iff A053760(k) < A053760(n) for every kA000040(A147971(n))

a(20)-a(29) from Charles R Greathouse IV, Apr 06 2012

A124882 Maximum number of distinct squares in arithmetic progression modulo prime(n).

Original entry on oeis.org

2, 2, 3, 3, 3, 4, 5, 4, 5, 4, 4, 4, 5, 5, 5, 6, 5, 6, 6, 7, 9, 6, 7, 6, 9, 7, 7, 6, 10, 5, 7, 8, 6, 5, 6, 7, 6, 6, 6, 6, 6, 6, 7, 9, 7, 6, 7, 7, 7, 6, 7, 7, 13, 7, 6, 7, 9, 7, 10, 7, 9, 9, 7, 11, 9, 7, 8, 9, 8, 6, 8, 8, 9, 6, 8, 8, 8, 8, 9, 13, 8, 12, 7, 9, 10, 8, 9, 9, 8, 8, 11, 13, 8, 8, 10, 8, 9, 8, 10, 10

Offset: 1

T. D. Noe, Nov 13 2006

nonn

For the natural numbers, it is well known that four squares cannot be in AP. Brown shows that this is not the case for modular arithmetic. There is no limit to the number of squares in AP modulo a prime: for the n-th prime pseudosquare A002223(n), the numbers 0,1,2,...,prime(n+1)-1 are squares in AP mod A002223(n).
From Travis Scott, May 28 2022: (Start)
Consider that a quadratic residue coloring of Z/pZ by R,N is essentially a binary string in a necklace of p strings in a chord of phi(p) necklaces.
Our exhaustive search for APs of distinct squares, as described by the original Mathematica program, fixes two of the R (say r1,r2) and permutes an equivalent string x -> Ax+b (with A = r2-r1 and b = r1) to count the first run of R on that string. We can reduce our search space by two symmetries:
I. R * color(x) = color(x) and N * color(x) = color^-1(x) implies that each Ax+b maps every cyclic k-term AP to a k-AP of the same color if A is a residue or to a k-AP of the opposite color if A is a nonresidue--we don't need to count runs in both colors for more than one A (or in one color for more than two A if those A transverse R,N).
II. p == +-1 (mod 4) induces color(-x) = color^+-1(x) implies that every k-AP running counterclockwise from 0 maps to a k-AP of the same or opposite color running clockwise from 0--we also don't need to count both colors in both halves of the same necklace. (Note, however, that for +1 the first and last k-APs counted from 0 in either direction overlap the mirrors at 0 and p/2 by k-1 and k.)
By I and II then, to certify a(n) for all differences on Z/pZ* and from all starting points on Z/pZ, it suffices to count the runs of R and N on the unpermuted coloring over the interval [0, p/2), weighting the first and last counts to 2k-1 and 2k if p == 1 (mod 4). (End)

			Consider numbers modulo 13, the 6th prime. The squares mod 13 are 0,1,3,4,9,10,12. Exhaustive search finds that the four numbers 1,9,17,25 are in AP and are also distinct squares modulo 13. Hence a(6)=4. There are two other APs of squares having the same length: 4,10,16,22 and 10,12,14,16.
From _Travis Scott_, May 28 2022: (Start)
Taking the same example on Z/13Z but with no information other than the residues < 13/2 (0,1,3,4) and the polarity of 13 (+) we find that the string RRNRRNN adjusted to (2k-1)RRR N RR NNNN(2k) has no longer run in any color than NNNN so a(6)=4. We can also use the N values of that run to show a maximal AP of squares mod 13 starting from every residue:
   2 * 5,6,7,8 = 10,12, 1, 3 = 10,12,14,16
   5 * 5,6,7,8 = 12, 4, 9, 1 = 12,17,22,27
   6 * 5,6,7,8 =  4,10, 3, 9 =  4,10,16,22
   7 * 5,6,7,8 =  9, 3,10, 4 =  9,16,23,30
   8 * 5,6,7,8 =  1, 9, 4,12 =  1, 9,17,25
  11 * 5,6,7,8 =  3, 1,12,10 =  3,14,25,36. (End)

K. S. Brown, Squares in Arithmetic Progression (mod p)
Pablo Saez, X. Vidaux, and M. Vsemirnov, Optimal bounds for Buchi's problem in modular arithmetic, Journal of Number Theory Volume 149, April 2015, Pages 368-403.

t=Table[p=Prime[n]; sqs=Sort[Mod[Range[0,(p-1)/2]^2,p]]; kMx=0; Do[If[i!=j, df=sqs[[j]]-sqs[[i]]; k=2; While[MemberQ[sqs, Mod[sqs[[i]]+k*df,p]], k++ ]; k--; If[k>kMx, kMx=k]], {i,Length[sqs]}, {j,Length[sqs]}]; kMx+1, {n,2,PrimePi[617]}]; Join[{2},t]
(* alternate program *)
Qres1C=Compile[{{x,_Integer,1},{q,_Integer,0}},Module[{s=0,z=0,i=2},While[x[[i]]==x[[i-1]],i++];z=2i-1;s=i;While[i"C",RuntimeAttributes->{Listable},Parallelization->True];
QresIC=Compile[{{x,_Integer,1},{q,_Integer,0}},Module[{s=2,z=2},Do[If[x[[i]]==x[[i-1]],s++,If[s>z,z=s];s=1],{i,2,q}];If[s>z,z=s];z],CompilationTarget->"C",RuntimeAttributes->{Listable},Parallelization->True];
{2}~Join~Table[If[Mod[p,4]==1,Qres1C[#,(p+1)/2],QresIC[#,(p-1)/2]]&@Unitize[PowerMod[Range[(p-1)/2],(p-1)/2,p]-1],{p,Prime@Range[2,6543]}]
(* Travis Scott, May 28 2022 Accelerated by symmetry per comment. *)

a(n) = max(A048280(n), A002308(n)).

A147972 Smallest prime p modulo which the first n primes are nonzero quadratic residues.

Original entry on oeis.org

7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 366791, 366791, 3818929, 9257329, 22000801, 36415991, 48473881, 120293879, 120293879, 131486759, 131486759, 2929911599, 2929911599, 7979490791, 23616331489, 23616331489, 89206899239, 121560956039, 196265095009, 196265095009, 513928659191, 5528920734431, 8402847753431, 8402847753431, 8402847753431, 70864718555231

Offset: 1

Max Alekseyev, Nov 18 2008

nonn

The same primes without repetitions are listed in A147970.
a(n) <= min{A002223(n), A002224(n)}. What is the smallest n for which this inequality is strict?
By definition, a(n) == 1, 7 (mod 8), so a(n) = min{A002223(n), A002224(n)}. - Jianing Song, Feb 18 2019

Cf. A000229, A002189, A002223, A002224, A045535, A053760, A133435, A147969, A147970, A147971.

Smallest prime p such that each of the first n primes has q q-th roots mod p: this sequence (q=2), A002225 (q=3), A002226 (q=5), A002227 (q=7), A002228 (q=11), A060363 (q=13), A060364 (q=17).

(*version 7.0*)m=1;P=7;Lst={p};While[m<25,m++;S=Prime[Range[m]];While[MemberQ[JacobiSymbol[S,p],-1],p=NextPrime[p]];Lst=Append[Lst,P]];Lst (* Emmanuel Vantieghem, Jan 31 2012 *)

t=2;forprime(p=2,1e9,forprime(q=2,t,if(kronecker(q,p)<1,next(2)));print1(p", ");t=nextprime(t+1);p--) \\ Charles R Greathouse IV, Jan 31 2012

a(n) >= min{A002189(n-1), A045535(n-1)}. - Jianing Song, Feb 18 2019

a(23)-a(25) from Emmanuel Vantieghem, Jan 31 2012

a(26)-a(37) from Max Alekseyev, Aug 21 2015

A029932 Primes with record values of the least positive prime primitive root.

Original entry on oeis.org

3, 7, 23, 41, 109, 191, 271, 2791, 11971, 31771, 190321, 2080597, 3545281, 4022911, 73189117, 137568061, 443571241, 565822531, 1160260711, 1622723341, 31552100581, 81651092041, 96736641541, 1867622877121, 5000346134911

Offset: 1

Scott Lindhurst (ScottL(AT)alumni.princeton.edu)

Other terms in the sequence: 39227234631271, 66597722601061 and 84054326426071 -Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 19 2008

Subsequence of A002230, considering only prime primitive roots. - M. F. Hasler, Jun 01 2018

R. Osborn, Tables of All Primitive Roots of Odd Primes Less Than 1000, Univ. Texas Press, 1961.
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. XLV.

Tomás Oliveira e Silva, Counts of least primitive roots of prime numbers (Artin's conjecture)
Tomás Oliveira e Silva, Least prime primitive roots
A. Paszkiewicz and A. Schinzel, On the least prime primitive root modulo a prime, Math. Comp. 71 (2002), no. 239, 1307-1321.
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]
Index entries for primes by primitive root

Cf. A060749, A002230, A084735.

(* This program is not suitable for computing more than a dozen terms. *) max = 10^8; pprQ[r_, p_] := Union[Table[PowerMod[r, i, p], {i, 1, p+1}]] == coprimes; ppr[p_] := With[{spr = PrimitiveRoot[p]}, If[PrimeQ[spr], spr, coprimes = Select[Range[p-1], CoprimeQ[#, p]&]; For[r = NextPrime[ spr], True, r = NextPrime[r], If[pprQ[r, p], Return[r]]]]]; Reap[ For[ record=1; p=3, p record, record = ppr1; Print["p = ", p, " ppr = ", record]; Sow[p]]]][[2, 1]] (* Jean-François Alcover, Feb 25 2016 *)

Corrected by Jud McCranie, Jan 04 2001

2 more terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 19 2008

A002231 Primitive roots that go with the primes in A029932.

Original entry on oeis.org

2, 3, 5, 7, 11, 19, 43, 53, 79, 107, 149, 151, 163, 211, 223, 263, 277, 307, 347, 349, 367, 383, 461, 479, 503

Offset: 1

N. J. A. Sloane

Other known terms in the sequence: 541, 547, 617. - Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 18 2008

R. Osborn, Tables of All Primitive Roots of Odd Primes Less Than 1000, Univ. Texas Press, 1961.
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. XLV.

R. K. Guy and N. J. A. Sloane, Correspondence, 1988.
Tomás Oliveira e Silva, Counts of least primitive roots of prime numbers (Artin's conjecture)
Tomás Oliveira e Silva, Least prime primitive roots
A. Paszkiewicz and A. Schinzel, On the least prime primitive root modulo a prime, Math. Comp. 71 (2002), no. 239, 1307-1321.
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]

Cf. A029932.

More terms from Scott Lindhurst (ScottL(AT)alumni.princeton.edu)

2 more terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 18 2008

cp's OEIS Frontend

A002229 Primitive roots that go with the primes in A002230.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A060363 Smallest prime p such that first n primes (p_1=2, ..., p_n) are 13th power residues mod p.

Views

Author

Keywords

Comments

References

Crossrefs

Extensions

A060364 Smallest prime p such that first n primes (p_1=2, ..., p_n) are 17th power residues mod p.

Views

Author

Keywords

References

Crossrefs

Extensions

A147969 Smallest prime p modulo which numbers 1,2,...,n are quadratic residues.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A147970 Primes corresponding to the records in the sequence of smallest positive quadratic nonresidues (A053760).

Views

Author

Keywords

Crossrefs

Formula

Extensions

A124882 Maximum number of distinct squares in arithmetic progression modulo prime(n).

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula

A147972 Smallest prime p modulo which the first n primes are nonzero quadratic residues.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A029932 Primes with record values of the least positive prime primitive root.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A002231 Primitive roots that go with the primes in A029932.

Views

Author

Keywords

Comments