

A248222


Maximal gap between quadratic residues mod n.


2



1, 1, 2, 3, 3, 2, 3, 4, 3, 3, 4, 5, 5, 3, 5, 7, 4, 3, 5, 7, 6, 4, 5, 8, 3, 5, 3, 7, 4, 5, 5, 8, 6, 4, 5, 9, 5, 5, 6, 11, 6, 6, 6, 8, 6, 5, 5, 12, 4, 3, 6, 8, 7, 3, 8, 9, 7, 4, 6, 11, 7, 5, 9, 8, 9, 6, 7, 13, 7, 5, 7, 12, 5, 5, 7, 8, 11, 6, 7, 15, 3, 6, 8, 12, 13, 6, 11, 16, 7, 6
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

"Maximal gap between squares mod n" would be a less ambiguous definition.
The definition of quadratic residue modulo a nonprime varies from author to author. Sometimes, even when n is a prime, 0 is not counted as a quadratic residue. In this entry, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n.
See A248376 for the variant with the additional restriction that the residue be coprime to the modulus.  M. F. Hasler, Oct 08 2014


REFERENCES

K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
F. J. MacWilliams and N. J. A. Sloane, The Theory of ErrorCorrecting Codes, ElsevierNorth Holland, 1978, p. 45.
G. B. Mathews, Theory of Numbers, 2nd edition. Chelsea, NY, p. 32. [Does not require gcd(q,n)=1.]
Ivan Niven and Herbert S. Zuckerman, An Introduction to the Theory of Numbers, New York: John Wiley, 2nd ed., 1966, p. 69. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGrawHill, NY, 1939, p. 270. [Does not require gcd(q,n)=1.]


LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Quadratic Residue
Wikipedia, Quadratic residue


EXAMPLE

For n=7, the quadratic residues are all numbers congruent to 0, 1, 2, or 4 (mod 7), so the largest gap of 3 occurs for example between 4 = 2^2 (mod 7) and 7 = 0^2 (mod 7).
For n=16, the quadratic residues are the numbers congruent to 0, 1, 4 or 9 (mod 16), so the largest gap occurs between, e.g., 9 = 3^2 (mod 16) and 16 = 0^2 (mod 16).


PROG

(PARI) (DD(v)=vecextract(v, "^1")vecextract(v, "^1")); a(n)=vecmax(DD(select(f>issquare(Mod(f, n)), vector(n*2, i, i))))


CROSSREFS

Cf. A063987, A130290, A088190, A088191, A088192.
Sequence in context: A286104 A137779 A191246 * A107918 A242392 A002963
Adjacent sequences: A248219 A248220 A248221 * A248223 A248224 A248225


KEYWORD

nonn,changed


AUTHOR

David W. Wilson and M. F. Hasler, Oct 04 2014


EXTENSIONS

Comments and references added by N. J. A. Sloane, Oct 04 2014


STATUS

approved



