A053760 -id:A053760 - cp's OEIS frontend

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

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

A112046 a(n) = the least k >= 1 for which the Jacobi symbol J(k,2n+1) is not +1 (thus is either 0 or -1).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 27 2005

nonn

If we instead list the least k >= 1, for which Jacobi symbol J(k,2n+1) is 0, we get A090368.

It is easy to see that every term is prime. Because the Jacobi symbol is multiplicative as J(ab,m) = J(a,m)*J(b,m) and if for every index i>=1 and < x, J(i,m)=1, then if J(x,m) is 0 or -1, x cannot be composite (say y*z, with both y and z less than x), as then either J(y,m) or J(z,m) would be non-one, which contradicts our assumption that x is the first index where non-one value appears. Thus x must be prime.

Indranil Ghosh and A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (first 1000 terms from Indranil Ghosh)

One more than A112050.
Bisections: A112047, A112048, and their difference: A112053.
Cf. A000040, A053760, A053761, A090368, A112049, A112060, A112070, A268829, A286465, A286466.

A112046(n) = for(i=1, (2*n), if((kronecker(i, (n+n+1)) < 1), return(i))); \\ Antti Karttunen, May 26 2017

from sympy import jacobi_symbol as J
def a(n):
    i=1
    while True:
        if J(i, 2*n + 1)!=1: return i
        else: i+=1
print([a(n) for n in range(1, 103)]) # Indranil Ghosh, May 11 2017

a(n) = A112050(n) + 1 = A000040(A112049(n)).

A020649 Least quadratic nonresidue modulo n (with n >= 3).

Original entry on oeis.org

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

Offset: 3

David W. Wilson

nonn

a(n) is the smallest q such that the congruence x^2 == q (mod n) has no solution 0 <= x < n, for n > 2. Note that a(n) is a prime. If n is an odd prime p, then a(p) is the smallest base b such that b^((p-1)/2) == -1 (mod p), see A053760. - Thomas Ordowski, Apr 24 2019

Amiram Eldar, Table of n, a(n) for n = 3..10000
Eric Weisstein's World of Mathematics, Quadratic Nonresidue

Cf. A053760.

a[n_] := Min @ Complement[Range[n - 1], Mod[Range[n/2]^2, n]]; Table[a[n], {n, 3, 110}] (* Amiram Eldar, Oct 29 2020 *)

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

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

A088192 Distance between prime(n) and the largest quadratic residue modulo prime(n).

Original entry on oeis.org

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

Offset: 1

Ferenc Adorjan (fadorjan(AT)freemail.hu), Sep 22 2003

a(n) = smallest m>0 such that -m is a quadratic residue modulo prime(n).
a(n) = smallest m>0 such that prime(n) either splits or ramifies in the imaginary quadratic field Q(sqrt(-m)). Equals -A220862(n) except when n = 1. Cf. A220861, A220863. - N. J. A. Sloane, Dec 26 2012
The values are 1 or a prime number (easily provable!). The maximum occurring prime values increase very slowly: up to 10^5 terms the largest prime is 43. The primes do not appear in order.

David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989, Cor. 5.17, p. 105. - From N. J. A. Sloane, Dec 26 2012

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Ferenc Adorjan, The sequence of largest quadratic residues modulo the primes.
J. A. Bergstra, I. Bethke, A negative result on algebraic specifications of the meadow of rational numbers, arXiv preprint arXiv:1507.00548 [math.RA], 2015-2016.

Records are (essentially) given by A147971.

Cf. A088190, A088191, A088193, A088194, A088195, A220861, A220862, A220863.

a[n_] := With[{p = Prime[n]}, If[JacobiSymbol[-1, p] > 0, 1, For[d = 2, True, d = NextPrime[d], If[JacobiSymbol[-d, p] >= 0, Return[d]]]]]; Array[a, 100] (* Jean-François Alcover, Feb 16 2018, after Charles R Greathouse IV *)

qrp_pm(fr,to)= {/* The distance of largest QR modulo the primes from the primes */ local(m,p,v=[]); for(i=fr,to,m=1; p=prime(i); j=2; while((j<=(p-1)/2)&&(m

do(p)=if(kronecker(-1,p)>0, 1, forprime(d=2, p, if(kronecker(-d, p) >= 0, return(d))))
apply(do, primes(100)) \\ Charles R Greathouse IV, Oct 31 2012

a(n) = A053760(n) unless -1 is a quadratic residue mod prime(n). - Charles R Greathouse IV, Oct 31 2012

Edited by Max Alekseyev, Oct 29 2012

A000229 a(n) is the least number m such that the n-th prime is the least quadratic nonresidue modulo m.

Original entry on oeis.org

3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 422231, 701399, 366791, 3818929, 9257329, 22000801, 36415991, 48473881, 175244281, 120293879, 427733329, 131486759, 3389934071, 2929911599, 7979490791, 36504256799, 23616331489, 89206899239, 121560956039

Offset: 1

N. J. A. Sloane

Note that a(n) is always a prime q > prime(n).
For n > 1, a(n) = prime(k), where k is the smallest number such that A053760(k) = prime(n).
One could make a case for setting a(1) = 2, but a(1) = 3 seems more in keeping with the spirit of the sequence.
a(n) is the smallest odd prime q such that prime(n)^((q-1)/2) == -1 (mod q) and b^((q-1)/2) == 1 (mod q) for every natural base b < prime(n). - Thomas Ordowski, May 02 2019

			a(2) = 7 because the second prime is 3 and 3 is the least quadratic nonresidue modulo 7, 14, 17, 31, 34, ... and 7 is the least of these.

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

N. J. A. Sloane, Table of n, a(n) for n = 1..38 (from the web page of Tomás Oliveira e Silva)
H. J. Godwin, On the least quadratic non-residue, Proc. Camb. Phil. Soc., 61 (3) (1965), 671-672.
A. J. Hanson, G. Ortiz, A. Sabry and Y.-T. Tai, Discrete Quantum Theories, arXiv preprint arXiv:1305.3292 [quant-ph], 2013.
A. J. Hanson, G. Ortiz, A. Sabry, Y.-T. Tai, Discrete quantum theories, (a different version). (To appear in J. Phys. A: Math. Theor., 2014).
Tomás Oliveira e Silva, Least primitive root of prime numbers
Hans Salié, Uber die kleinste Primzahl, die eine gegebene Primzahl als kleinsten positiven quadratischen Nichtrest hat, Math. Nachr. 29 (1965) 113-114.
Yu-Tsung Tai, Discrete Quantum Theories and Computing, Ph.D. thesis, Indiana University (2019).

Cf. A020649, A025021, A053760, A307809. For records see A133435.

Differs from A002223, A045535 at 12th term.

leastNonRes[p_] := For[q = 2, True, q = NextPrime[q], If[JacobiSymbol[q, p] != 1, Return[q]]]; a[1] = 3; a[n_] := For[pn = Prime[n]; k = 1, True, k++, an = Prime[k]; If[pn == leastNonRes[an], Print[n, " ", an];  Return[an]]]; Array[a, 20] (* Jean-François Alcover, Nov 28 2015 *)

Definition corrected by Melvin J. Knight (MELVIN.KNIGHT(AT)ITT.COM), Dec 08 2006

Name edited by Thomas Ordowski, May 02 2019

A098990 Decimal expansion of Sum_{n>=1} prime(n)/(2^n).

Original entry on oeis.org

3, 6, 7, 4, 6, 4, 3, 9, 6, 6, 0, 1, 1, 3, 2, 8, 7, 7, 8, 9, 9, 5, 6, 7, 6, 3, 0, 9, 0, 8, 4, 0, 2, 9, 4, 1, 1, 6, 7, 7, 7, 9, 7, 5, 8, 8, 7, 7, 9, 4, 3, 7, 3, 2, 8, 3, 1, 2, 2, 0, 5, 2, 2, 0, 1, 7, 6, 3, 7, 9, 8, 6, 7, 0, 4, 4, 8, 2, 8, 3, 6, 0, 4, 1, 7, 4, 5, 4, 7, 6, 4, 5, 7, 8, 8, 0, 1, 9, 0, 1, 1, 3, 7, 5, 2

Offset: 1

Joseph Biberstine (jrbibers(AT)indiana.edu), Nov 07 2004

Relates the growth of the n-th prime function A000040(n) to the base-2 exponential of n.

			3.6746439660113287789956763090840294116777975887794373283122052201763...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 2.2.1, p. 96.

Thomas Bloom, Is Sum p_n/2^n irrational? (Here p_n is the nth prime), Erdős Problems.
Peter J. Cho and Henry H. Kim, The average of the smallest prime in a conjugacy class, International Mathematics Research Notices, Vol. 2020, No. 6 (2020), pp. 1718-1747, arXiv preprint, arXiv:1601.03012 [math.NT], 2016.
Paul Erdős, Remarks on number theory. I., Mat. Lapok, Vol. 12 (1961), pp. 10-17; Math. Rev. 26 #2410.
Steven R. Finch, Average least nonresidues, December 4, 2013. [Cached copy, with permission of the author]
Paul Pollack, The average least quadratic nonresidue modulo m and other variations on a theme of Erdős, J. Number Theory, Vol. 132, No. 6 (2012), pp. 1185-1202, alternative link.
Terence Tao, Erdős problem database, see no. 251.

Cf. A000040, A053760, A098882.

f:=N->sum(ithprime(n)/2^n,n=1..N); evalf[106](f(500)); evalf[106](f(1000));

RealDigits[Sum[Prime[i]/2^i,{i,1000}],10,120][[1]] (* Harvey P. Dale, Apr 10 2012 *)

suminf(k=1, prime(k)/2^k) \\ Michel Marcus, Jan 13 2016

Equals Sum_{n>=1} prime(n)/2^n.
Equals 2 plus the constant in A098882. - R. J. Mathar, Sep 02 2008
Equals lim_{n->oo} (1/n) * Sum_{k=1..n} A053760(k). - Amiram Eldar, Oct 29 2020

A091382 Distance between the sequence of primes and the largest "mixed" quadratic residues modulo the primes (A091380).

Original entry on oeis.org

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

Offset: 1

Ferenc Adorjan (fadorjan(AT)freemail.hu)

Apart from the first term, it contains solely primes. Is every prime in there?

Apart from the first term and the definition, it is identical to the sequence A053760 by S. R. Finch.

Ferenc Adorjan, The sequence of largest quadratic residues modulo the primes

Cf. A091380, A091381, A091383, A091384, A091385, A088192, A088198.

{/* Distance of primes from the sequence of the largest "mixed" QR modulo the primes */ p_lqxr(to)=local(v=[1],k,r,q,p); for(i=2,to,p=prime(i);k=p-1;r=p%4-2; while(kronecker(k,p)<>r,k-=1); v=concat(v,p-k)); print(v) }

A306530 a(n) is the smallest prime q such that Kronecker(q, prime(n)) = 1.

Original entry on oeis.org

7, 7, 11, 2, 3, 3, 2, 5, 2, 5, 2, 3, 2, 11, 2, 7, 3, 3, 17, 2, 2, 2, 3, 2, 2, 5, 2, 3, 3, 2, 2, 3, 2, 5, 5, 2, 3, 41, 2, 13, 3, 3, 2, 2, 7, 2, 5, 2, 3, 3, 2, 2, 2, 3, 2, 2, 5, 2, 3, 2, 7, 17, 7, 2, 2, 7, 5, 2, 3, 3, 2, 2, 2, 3, 5, 2, 5, 3, 2, 2, 3, 3, 2, 2, 2, 3, 2

Offset: 1

Jianing Song, Feb 22 2019

nonn

For n >= 2, a(n) is the smallest prime quadratic residue modulo the n-th prime.
Also for n >= 2, a(n) is the smallest prime that decomposes in the quadratic field Q[sqrt((-1)^((p-1)/2)*p)], p = prime(n). Using this definition, a(1) should have been 5 because for p = 2, Q[sqrt((-1)^((p-1)/2)*p)] = Q[sqrt(2*i)] = Q[1+i] = Q[i], in which 5 decomposes.
For most n, a(n) is relatively small. Among [1, 10000], there are only 669 n's that violate a(n) < prime(n)/n and 97 n's > 1 that violate a(n) < prime(n)*log(log(n))/n. In fact, if we ignore the first three terms, the only terms among the first 10000 ones that seem unusually large are a(14) = 11, a(19) = 17, a(38) = 41, a(62) = 17, a(1137) = 29, a(1334) = 29, a(3935) = 37, a(7309) = 43, a(8783) = 37 and a(8916) = 41, with the corresponding primes 43, 67, 163, 293, 9173, 10987, 37123, 74093, 90787, 92333.
For every prime p there are infinitely many n such that a(n)=p. Indeed, using quadratic reciprocity, for each prime p_j <= p we can choose k_j coprime to p_j, such that p_j is a quadratic nonresidue (if p_j < p) or residue (if p_j = p) mod q for every prime q == k_j (mod p_j). Dirichlet's theorem on primes in arithmetic progressions implies there are infinitely many primes q with q == k_j (mod p_j) for all j. Then a(n) = p where q = prime(n). - Robert Israel, Mar 26 2019
a(n) is the smallest prime q such that the congruence x^2 == q (mod p) has a solution x, where p = prime(n). For n > 1, a(n) is the smallest prime q such that q^((p-1)/2) == 1 (mod p), where odd p = prime(n). - Thomas Ordowski, Apr 29 2019

			2, 3, 5, 7, ..., 37 are all quadratic nonresidues modulo prime(38) = 163, while 41 is a quadratic residue modulo 163, so a(38) = 41.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A053760 (smallest (prime) quadratic nonresidue modulo prime(n)).

Cf. A024704 (a(n)=2).

f:= proc(n) local q,p;
  q:= ithprime(n);
  p:= 1:
  do
    p:= nextprime(p);
    if numtheory:-jacobi(p,q)=1 then return p fi
  od;
end proc:
map(f, [$1..100]); # Robert Israel, Mar 26 2019

a[n_] := Module[{i = 1}, While[KroneckerSymbol[Prime[i], Prime[n]] != 1, i++]; Prime[i]];
Array[a, 100] (* Jean-François Alcover, Jun 08 2020, after PARI *)

a(n)=my(i=1);while(kronecker(prime(i),prime(n))!=1,i++);prime(i)

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Crossrefs

Formula

Extensions

A112046 a(n) = the least k >= 1 for which the Jacobi symbol J(k,2n+1) is not +1 (thus is either 0 or -1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Formula

A020649 Least quadratic nonresidue modulo n (with n >= 3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A088192 Distance between prime(n) and the largest quadratic residue modulo prime(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A000229 a(n) is the least number m such that the n-th prime is the least quadratic nonresidue modulo m.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A098990 Decimal expansion of Sum_{n>=1} prime(n)/(2^n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A091382 Distance between the sequence of primes and the largest "mixed" quadratic residues modulo the primes (A091380).

Views