

A182865


Minimal number of quadratic residues: a(n) is the least integer m such that any nonzero square is congruent (mod n) to one of the squares from 1 to m^2.


1



1, 1, 1, 2, 3, 3, 2, 4, 5, 5, 3, 6, 7, 6, 3, 8, 8, 9, 5, 9, 11, 11, 6, 12, 13, 13, 7, 14, 15, 15, 7, 15, 17, 15, 8, 18, 19, 18, 10, 20, 21, 21, 11, 20, 23, 23, 9, 24, 24, 24, 13, 26, 26, 25, 14, 27, 29, 29, 15, 30, 31, 28, 15, 30, 33, 33, 17, 33, 35, 35, 16, 36, 37, 36, 19, 35, 39, 39, 15, 40, 41, 41, 21, 40, 43, 42, 22, 44, 40, 42, 23, 45, 47, 45, 21, 48, 48, 44, 24
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,4


COMMENTS

Up to n=3600, a(n) is equal to floor(n/2) 1262 times (about 35% of the cases).
Sometimes the ratio a(n)/n is unexpectedly low:
a(100)/100 = 24/100 = 0.24
a(144)/144 = 23/144 = 0.159722...
a(3600)/3600 = 539/3600 = 0.149722...


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 2..1000
Eric Weisstein's World of Mathematics, Quadratic Residue


EXAMPLE

For n = 100, one gets a(100) = 24 (far less than the expected floor(100/2) = 50).


MATHEMATICA

q[n_, k_] := Cases[Union[Mod[Range[k]^2, n]], _?Positive];
a[n_] := (r = q[n, Floor[n/2]]; k = 0; While[r != q[n, ++k]]; k); Table[a[n], {n, 2, 100}]


CROSSREFS

It should be noticed that, when n is prime, the corresponding sublist is A005097, i.e., (primes1)/2.
Cf. A096008.
Sequence A105612 (number of nonzero quadratic residues mod n) is different from this sequence at positions such as 9, 15, 18, 21, and 24.
Sequence in context: A308284 A036465 A265339 * A131469 A309076 A343326
Adjacent sequences: A182862 A182863 A182864 * A182866 A182867 A182868


KEYWORD

nonn,easy


AUTHOR

JeanFrançois Alcover, Feb 01 2011


EXTENSIONS

Formula and sequence corrected to eliminate zeros from lists of quadratic residues. Anyway, mod computed with or without offset 1 gives the same list.


STATUS

approved



