login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A177865 Polya-Vinogradov numbers: a(n) is the maximum over all k > 0 of |#(quadratic residues modulo p up to k) - #(quadratic nonresidues modulo p up to k)| where p is the n-th prime and n > 1. 2
1, 1, 2, 3, 2, 2, 3, 5, 3, 6, 4, 4, 5, 8, 5, 9, 4, 6, 10, 5, 10, 9, 6, 6, 7, 10, 9, 6, 6, 10, 15, 7, 9, 7, 14, 8, 9, 18, 9, 15, 7, 19, 8, 11, 18, 12, 15, 15, 9, 10, 22, 8, 21, 10, 21, 11, 22, 14, 10, 13, 11, 14, 25, 11, 13, 14, 12, 17, 12, 12, 27, 19, 16, 15, 27, 12, 12, 12, 12, 27, 11, 30 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

COMMENTS

In 1918 Polya and Vinogradov (independently) proved an upper bound for a(n) and Schur proved a lower bound:

sqrt(p)/2*pi < a(n) < sqrt(p)*log(p), where p is the n-th prime.

REFERENCES

G. Polya, Über die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), 21-29.

I. Schur, Einige Bemerkungen zu der vorstehenden Arbeit des Herrn G. Polya: Über die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), 30-36.

I. M. Vinogradov, Über eine asymptotische Formel aus der Theorie der binaeren quadratischen Formen, J. Soc. Phys. Math. Univ. Permi, 1 (1918), 18-28.

I. M. Vinogradov, Elements of Number Theory, 5th revised ed., Dover, 1954, p. 200.

LINKS

Table of n, a(n) for n=2..83.

MathWorld, Polya Vinogradov Inequality

PlanetMath, Polya Vinogradov Inequality

Wikipedia, Quadratic residue

Wikipedia, Legendre symbol

Wikipedia, Character Sum

FORMULA

a(n) = max_{0<k<p} |sum_{i=1..k} L(i/p)|, where p is the n-th prime, n>1, and L(i/p) is the Legendre symbol.

EXAMPLE

The initial term is a(2) = 1 because the 2nd prime is 3 and L(1/3) = 1 and L(2/3) = -1, so |sum_{i=1..k} L(i/3)| = 1 and 0 for k = 1 and 2, resp., and so max = 1.

MATHEMATICA

Table[Max[ Table[Abs[Sum[JacobiSymbol[i, Prime[n]], {i, 1, k}]], {k, 1, Prime[n] - 1}]], {n, 2, 100}]

CROSSREFS

Cf. A055088 (Triangle of generalized Legendre symbols L(a/b), with 1's for quadratic residues and 0's for quadratic non-residues [replace the 0's with -1's]).

Cf. also A095102, A165580, A165977, A207291, A207292.

Sequence in context: A096258 A049879 A053812 * A307835 A017828 A140087

Adjacent sequences:  A177862 A177863 A177864 * A177866 A177867 A177868

KEYWORD

easy,nonn

AUTHOR

Jonathan Sondow, May 17 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 14 15:08 EST 2019. Contains 329979 sequences. (Running on oeis4.)