%I
%S 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,
%T 7,15,17,15,8,18,19,18,10,20,21,21,11,20,23,23,9,24,24,24,13,26,26,25,
%U 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
%N 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.
%C Up to n=3600, a(n) is equal to floor(n/2) 1262 times (about 35% of the cases).
%C Sometimes the ratio a(n)/n is unexpectedly low:
%C a(100)/100 = 24/100 = 0.24
%C a(144)/144 = 23/144 = 0.159722...
%C a(3600)/3600 = 539/3600 = 0.149722...
%H Vincenzo Librandi, <a href="/A182865/b182865.txt">Table of n, a(n) for n = 2..1000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>
%e For n = 100, one gets a(100) = 24 (far less than the expected floor(100/2) = 50).
%t q[n_, k_] := Cases[Union[Mod[Range[k]^2, n]],_?Positive];
%t a[n_] := (r = q[n, Floor[n/2]]; k = 0; While[r != q[n, ++k]]; k); Table[a[n], {n, 2, 100}]
%Y It should be noticed that, when n is prime, the corresponding sublist is A005097, i.e., (primes1)/2.
%Y Cf. A096008.
%Y Sequence A105612 (number of nonzero quadratic residues mod n) is different from this sequence at positions such as 9, 15, 18, 21, and 24.
%K nonn,easy
%O 2,4
%A _JeanFrançois Alcover_, Feb 01 2011
%E Formula and sequence corrected to eliminate zeros from lists of quadratic residues. Anyway, mod computed with or without offset 1 gives the same list.
