A000229 -id:A000229 - cp's OEIS frontend

A053760 Smallest positive quadratic nonresidue modulo p, where p is the n-th prime.

2, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 2, 5, 2, 2, 2, 7, 5, 2, 3, 2, 3, 2, 2, 3, 7, 7, 2, 3, 5, 2, 3, 2, 3, 2, 2, 2, 11, 5, 2, 2, 5, 2, 2, 3, 7, 3, 2, 2, 5, 2, 2, 3, 7, 2, 2, 7, 5, 3, 2, 3, 5, 2, 3, 2, 13, 3, 2, 2, 5, 2, 3, 2, 2, 2, 2, 2

Offset: 1

Steven Finch, Apr 05 2000

nonn

Assuming the Generalized Riemann Hypothesis, Montgomery proved a(n) << (log p(n))^2, meaning that there is a constant c such that |a(n)| <= c*(log p(n))^2. - Jonathan Vos Post, Jan 06 2007
a(n) < 1 + sqrt(p), where p is the n-th prime (Theorem 3.9 in Niven, Zuckerman, and Montgomery). - Jonathan Sondow, May 13 2010
Treviño proves that a(n) < 1.1 p^(1/4) log p for n > 2 where p is the n-th prime. - Charles R Greathouse IV, Dec 06 2012
a(n) is always a prime, because if x*y is a nonresidue, then x or y must also be a nonresidue. - Jonathan Sondow, May 02 2013
a(n) is the smallest prime q such that the congruence x^2 == q (mod p) has no solution 0 < x < p, where p = prime(n). For n > 1, a(n) is the smallest base b such that b^((p-1)/2) == -1 (mod p), where odd p = prime(n). - Thomas Ordowski, Apr 24 2019

			The 5th prime is 11, and the positive quadratic residues mod 11 are 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 5 and 5^2 = 3. Since 2 is missing, a(5) = 2.
The only positive quadratic redidue mod 2 is 1, so a(1)=2.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 94-98.
Hugh L. Montgomery, Topics in Multiplicative Number Theory, 3rd ed., Lecture Notes in Mathematics, Vol. 227 (1971), MR 49:2616.
Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory Of Numbers, Fifth Edition, John Wiley and Sons, Inc., NY 1991, p. 147.
Paulo Ribenboim, The New Book of Prime Number Records, 3rd ed., Springer-Verlag 1996; Math. Rev. 96k:11112.

T. D. Noe, Table of n, a(n) for n = 1..10000
Robert Baillie and Samuel S. Wagstaff, Lucas pseudoprimes, Mathematics of Computation, Vol. 35, No. 152 (1980), pp. 1391-1417, Math. Rev. 81j:10005, alternative link.
Paul Erdős, Remarks on number theory. I., Mat. Lapok, Vol. 12 (1961), pp. 10-17; Math. Rev. 26 #2410.
Steven R. Finch, Quadratic Residues [Broken link]
Steven R. Finch, Quadratic Residues [From the Wayback machine]
Keith Matthews, Finding n(p), the least quadratic non-residue (mod p)
Enrique Treviño, The least k-th power non-residue, Journal of Number Theory, Vol. 149 (2015),pp. 201-224, alternative link.
Eric Weisstein's World of Mathematics, Quadratic Nonresidue.

Cf. A000229, A020649, A098990.

Table[ p = Prime[n]; First[ Select[ Range[p], JacobiSymbol[#, p] != 1 &]], {n, 1, 100}] (* Jonathan Sondow, Mar 03 2013 *)

residue(n,m)={local(r);r=0;for(i=0,floor(m/2),if(i^2%m==n,r=1));r}
A053760(n)={local(r,m);r=0;m=0;while(r==0,m=m+1;if(!residue(m,prime(n)),r=1));m} \\ Michael B. Porter, May 02 2010

qnr(p)=my(m);while(1,if(!issquare(Mod(m++,p)),return(m)))
a(n)=if(n>1,qnr(prime(n)),2) \\ Charles R Greathouse IV, Feb 27 2013

a(n) = A020649(prime(n)) for n > 1. - Thomas Ordowski, Apr 24 2019

Asymptotic mean: lim_{n->oo} (1/n) * Sum_{k=1..n} a(k) = A098990 (Erdős, 1961). - Amiram Eldar, Oct 29 2020

More terms from James Sellers, Apr 08 2000

A147971 Indices of the records in the sequence of smallest positive quadratic nonresidues (A053760).

Original entry on oeis.org

1, 4, 9, 20, 64, 92, 246, 752, 1289, 2084, 3383, 31284, 271259, 618525, 1389315, 2228197, 2914847, 6857528, 7457772, 141236709, 366883983, 1034128714, 3690981956, 4965932454, 7863515482, 19824941433, 195348751601, 292557888940, 2296552237422

Offset: 1

Max Alekseyev, Nov 18 2008

nonn

The corresponding primes are listed in A147970.

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

Positive integer n is in this sequence iff A053760(k) < A053760(n) for every k

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

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

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

A196941 a(n) is the minimum prime (or 1) needed to write integer n into the form n = a + b such that all prime factors of a and b are smaller or equal to a(n).

Original entry on oeis.org

1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 5, 2, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 5, 5, 2, 3, 3, 3, 3, 5, 3, 3, 3, 3, 3, 3, 3, 5, 3, 3, 2, 2, 2, 3, 2, 5, 3, 7, 2, 3, 3, 3, 3, 5, 3, 5, 2, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 2

Lei Zhou, Oct 07 2011

Any integer n that is greater than 1 can be written into the sum of two other positive integers, such that n = a + b.  There are IntegerPart[n / 2] ways to do this assuming a <= b.  For each of the ways, we can have a set of prime factor of a and b, defined as sa = FactorSet[a] and sb = FactorSet[b], quoting the function in the Mathematica program.  Then we can define a union set s=Union[sa, sb], which is a list of prime factors that can factor either a or b.  In this way we obtain IntegerPart[n / 2] of possible set s.  Define p_i is the largest prime number in each of set s_i, i = 1,2...IntegerPart[n / 2], a(n) = the smallest s_i.
Though 2 =  1 + 1 and 1 is not a prime number, a(2) can still be defined as 1.
The Mathematica program generates up to term 88.
The first occurrence of a(n)=k forms sequence A000229. - Lei Zhou, Feb 06 2014

			n = 3, 3 = 1 + 2, the largest prime factor of 1 and 2 is 2, so a[3] = 2;
n = 4, 4 = 2 + 2, the largest prime factor of 2 and 2 is 2, so a[4] = 2;
[in 4 = 1 + 3, the largest prime factor of 1 and 3 is 3, which is larger than a[4] = 2]
...
n = 23, 23 = 3 + 20 = 3 + 2^2 * 5, the largest prime factor of 3 and 20 is 5, so a[23] = 5;

T. D. Noe, Table of n, a(n) for n = 2..10000

Cf. A173786 (n for which a(n)=2), A196526, A000229.

FactorSet[seed_] := Module[{fset2, a, l, i}, a = FactorInteger[seed]; l = Length[a]; fset2 = {}; Do[fset2 = Union[fset2, {a[[i]][[1]]}], {i, 1, l}]; fset2]; Table[min = n; Do[r = n - k; s = Union[FactorSet[k], FactorSet[r]]; If[a = s[[Length[s]]]; a < min, min = a], {k, 1, IntegerPart[n/2]}]; min, {n, 2, 88}]
LPF[n_] := FactorInteger[n][[-1,1]]; Table[Min[Table[Max[{LPF[i], LPF[n-i]}], {i, Floor[n/2]}]], {n, 2, 100}] (* T. D. Noe, Oct 07 2011 *)

A307809 Smallest "non-residue" pseudoprime to base prime(n).

Original entry on oeis.org

3277, 3281, 121463, 491209, 11530801, 512330281, 15656266201

Offset: 1

Amiram Eldar and Thomas Ordowski, Apr 30 2019

a(n) is the smallest odd composite k, with q = A020649(k) = prime(n), such that q^((k-1)/2) == -1 (mod k).

a(8) <= 139309114031, a(9) <= 7947339136801, a(10) <= 72054898434289, a(11) <= 334152420730129, a(12) <= 17676352761153241, a(13) <= 172138573277896681. - Daniel Suteu, Apr 30 2019

Cf. A000229, A020649, A307767 (the "non-residue" pseudoprimes).

residueQ[n_, m_] := Module[{ans = 0}, Do[If[Mod[k^2, m] == n, ans = True; Break[]], {k, 0, Floor[m/2]}]; ans]; A020649[n_] := Module[{m = 0}, While[ residueQ[m, n], m++]; m]; a[n_] := Module[{p = Prime[n], k = 3}, While[PrimeQ[k] || PowerMod[p, (k-1)/2, k] != k-1 || A020649[k] != p , k+=2]; k]; Array[a, 6]

a(7) from Daniel Suteu, Apr 30 2019

A307965 a(n) is the least prime p = prime(k) > prime(n) such that A306530(k) = prime(n).

Original entry on oeis.org

7, 11, 19, 53, 43, 173, 67, 2477, 8803, 9173, 32323, 37123, 163, 74093, 170957, 360293, 679733, 2404147, 2004917, 69009533, 51599563, 155757067, 96295483, 146161723, 1408126003, 3519879677, 2050312613, 3341091163, 78864114883, 65315700413, 1728061733, 9447241877

Offset: 1

Amiram Eldar and Thomas Ordowski, May 08 2019

nonn

This sequence is analogous to A000229, but for least prime quadratic residue modulo p.

Note that a(n) is the least odd number m > prime(n) such that prime(n)^((m-1)/2) == 1 (mod m) and q^((m-1)/2) == -1 (mod m) for every prime q < prime(n). Such m is always an odd prime.

Cf. A000229, A306530.

f[n_] := Module[{p = Prime[n], q = 2}, While[JacobiSymbol[q, p] != 1, q = NextPrime[q]]; q]; a[n_] := Module[{p = Prime[n], k = n + 1}, While[f[k] != p, k++]; Prime[k]]; Array[a, 20]

f(n) = my(i=1, p = prime(n)); while(kronecker(prime(i), p)! = 1, i++); prime(i); \\ A306530
a(n) = my(p=prime(n), iq = p+1, q=nextprime(iq)); while(f(iq)!= p, iq++); prime(iq); \\ Michel Marcus, May 12 2019

A309284 a(n) is the smallest odd composite k such that prime(n)^((k-1)/2) == -1 (mod k) and b^((k-1)/2) == 1 (mod k) for every natural b < prime(n).

Original entry on oeis.org

3277, 5173601, 2329584217, 188985961, 5113747913401, 30990302851201, 2528509579568281, 5189206896360728641, 12155831039329417441

Offset: 1

Thomas Ordowski, Jul 21 2019

a(n) is an Euler pseudoprime to base 2, so it is also a Fermat pseudoprime to base 2.
This sequence is analogous to the sequence A000229 of primes.
Conjecture: the smallest quadratic non-residue modulo a(n) is prime(n), i.e., A020649(a(n)) = prime(n).
a(10) <= 41154189126635405260441. - Daniel Suteu, Jul 22 2019

Cf. A000229, A001567, A006970, A307767, A309285.

isok(n,k) = (k%2==1) && !isprime(k) && Mod(prime(n), k)^((k-1)/2) == Mod(-1, k) && !for(b=2, prime(n)-1, if(Mod(b, k)^((k-1)/2) != Mod(1, k), return(0)));
a(n) = for(k=9, oo, if(isok(n, k), return(k))); \\ Daniel Suteu, Jul 22 2019

According to the data, b^((a(n)-1)/2) == (b / a(n)) (mod a(n)) for every natural b <= prime(n), where (x / y) is the Jacobi symbol.

a(5)-a(9) from Amiram Eldar, Jul 21 2019

Showing 1-10 of 11 results. Next

cp's OEIS Frontend

A133435 Records in A000229.

Views

Author

Keywords

Links

A053760 Smallest positive quadratic nonresidue modulo p, where p is the n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A147971 Indices of the records in the sequence of smallest positive quadratic nonresidues (A053760).

Views

Author

Keywords

Comments

Crossrefs

Formula

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

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

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A196941 a(n) is the minimum prime (or 1) needed to write integer n into the form n = a + b such that all prime factors of a and b are smaller or equal to a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A307809 Smallest "non-residue" pseudoprime to base prime(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A307965 a(n) is the least prime p = prime(k) > prime(n) such that A306530(k) = prime(n).

Views

Author

Keywords

Comments