A088190 -id:A088190 - cp's OEIS frontend

A248376 Maximal gap between quadratic residues mod n; here quadratic residues must be coprime to n.

1, 2, 3, 4, 3, 6, 4, 8, 3, 8, 4, 12, 5, 8, 12, 8, 4, 6, 5, 12, 12, 8, 6, 24, 3, 8, 3, 16, 4, 18, 5, 8, 12, 8, 13, 12, 5, 10, 15, 32, 6, 24, 6, 16, 12, 12, 6, 24, 4, 8, 18, 20, 7, 6, 13, 32, 15, 10, 6, 48, 7, 10, 12, 8, 13, 24, 7, 16, 18, 20, 8, 24, 5, 10

Offset: 1

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

nonn

The definition of quadratic residue modulo a nonprime varies from author to author. Sometimes, quadratic residues are not required to be coprime to n, cf. A248222 for the corresponding variant of this sequence.

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 Error-Correcting Codes, Elsevier-North 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, McGraw-Hill, NY, 1939, p. 270. [Does not require gcd(q,n)=1.]

David W. Wilson, Table of n, a(n) for n = 1..10000
Eric W. Weisstein, MathWorld: Quadratic Residue
Wikipedia, Quadratic residue

Cf. A063987, A130290, A088190, A088191, A088192, A248222.

a(n)={L=m=1;for(i=2,n+1,gcd(i,n)>1&&next;issquare(Mod(i,n))||next;i-L>m&&m=i-L;L=i);m}

A140292 a(n) is a square mod a(n-1), a(n) > a(n-1) and a(n) semiprime.

Original entry on oeis.org

4, 9, 10, 14, 15, 21, 22, 25, 26, 35, 39, 49, 51, 55, 69, 82, 86, 87, 91, 95, 106, 115, 119, 121, 122, 123, 133, 134, 143, 146, 155, 159, 166, 169, 178, 183, 187, 202, 203, 219, 235, 249, 253, 254, 262, 265, 274, 278, 287, 289, 291, 295, 299, 302, 303, 309, 327

Offset: 1

Jonathan Vos Post, May 24 2008

Cf. A001358, A034794, A088190.

isqResid := proc(n,modp) local x ; for x from 1 to floor(modp/2) do if x^2 mod modp = n mod modp then RETURN(true) ; fi ; od: RETURN(false) ; end: isA001358 := proc(n) RETURN( numtheory[bigomega](n)= 2) ; end: A140292 := proc(n) option remember ; local a; if n = 1 then 4; else for a from A140292(n-1)+1 do if isA001358(a) and isqResid(a,A140292(n-1)) then RETURN(a) ; fi ; od ; fi ; end: seq(A140292(n),n=1..80) ; # R. J. Mathar, May 31 2008

quadResQ[n_, p_] := Module[{x}, For[x = 1, x <= Floor[p/2], x++, If[Mod[x^2, p] == Mod[n, p], Return[True]]]; Return[False]];
semiprimeQ[n_] := PrimeOmega[n] == 2;
a[n_] := a[n] = Module[{k}, If[n == 1, 4, For[k = a[n - 1] + 1, True, k++, If[semiprimeQ[k] && quadResQ[k, a[n - 1]], Return[k]]]]];
Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Jan 28 2024, after R. J. Mathar *)

Corrected and extended by R. J. Mathar, May 31 2008

cp's OEIS Frontend

A248376 Maximal gap between quadratic residues mod n; here quadratic residues must be coprime to n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

A140292 a(n) is a square mod a(n-1), a(n) > a(n-1) and a(n) semiprime.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Extensions