|
| |
|
|
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, Ueber die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), 21-29.
I. Schur, Einige Bemerkungen zu der vorstehenden Arbeit des Herrn G. Polya: Ueber die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), 30-36.
I. M. Vinogradov, Ueber 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 * A017828 A140087 A174329
Adjacent sequences: A177862 A177863 A177864 * A177866 A177867 A177868
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
Jonathan Sondow, May 17 2010
|
|
|
STATUS
|
approved
|
| |
|
|
