login
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
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.
Named after the Hungarian mathematician George Pólya (1887-1985) and the Soviet mathematician Ivan Matveevich Vinogradov (1891-1983). - Amiram Eldar, Jun 22 2021
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.
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}]
PROG
(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
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]).
Sequence in context: A096258 A049879 A053812 * A307835 A341651 A017828
KEYWORD
easy,nonn
AUTHOR
Jonathan Sondow, May 17 2010
STATUS
approved