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.
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
Offset: 2
Examples
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.
References
- I. M. Vinogradov, Über eine asymptotische Formel aus der Theorie der binaeren quadratischen Formen, J. Soc. Phys. Math. Univ. Permi, Vol. 1 (1918), pp. 18-28.
- I. M. Vinogradov, Elements of Number Theory, 5th revised ed., Dover, 1954, p. 200.
Links
- PlanetMath, Polya Vinogradov Inequality.
- 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), pp. 30-36.
- Eric Weisstein's World of Mathematics, Polya-Vinogradov Inequality.
- Wikipedia, Character Sum.
- Wikipedia, Legendre symbol.
- Wikipedia, Quadratic residue.
Crossrefs
Programs
-
Mathematica
Table[Max[ Table[Abs[Sum[JacobiSymbol[i, Prime[n]], {i, 1, k}]], {k, 1, Prime[n] - 1}]], {n, 2, 100}] -
PARI
a(n) = my(p=prime(n)); vecmax(vector(p-1, k, vecsum(vector(k, i, issquare(Mod(i, p)))) - vecsum(vector(k, i, !issquare(Mod(i, p)))))); \\ Michel Marcus, Mar 03 2023
Formula
a(n) = max_{01, and L(i/p) is the Legendre symbol.
Comments