

A177865


PolyaVinogradov 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 nth 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 nth prime.


REFERENCES

G. Polya, Über die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), 2129.
I. Schur, Einige Bemerkungen zu der vorstehenden Arbeit des Herrn G. Polya: Über die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), 3036.
I. M. Vinogradov, Über eine asymptotische Formel aus der Theorie der binaeren quadratischen Formen, J. Soc. Phys. Math. Univ. Permi, 1 (1918), 1828.
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 nth 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 nonresidues [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



