login
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

%I #36 Dec 14 2014 02:18:36

%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., (primes-1)/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 _Jean-Franç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.