cp's OEIS Frontend

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.

%I A182865 #37 Feb 16 2025 08:33:13
%S A182865 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 A182865 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 A182865 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 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.
%C A182865 Up to n=3600, a(n) is equal to floor(n/2) 1262 times (about 35% of the cases).
%C A182865 Sometimes the ratio a(n)/n is unexpectedly low:
%C A182865 a(100)/100 = 24/100 = 0.24
%C A182865 a(144)/144 = 23/144 = 0.159722...
%C A182865 a(3600)/3600 = 539/3600 = 0.149722...
%H A182865 Vincenzo Librandi, <a href="/A182865/b182865.txt">Table of n, a(n) for n = 2..1000</a>
%H A182865 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>
%e A182865 For n = 100, one gets a(100) = 24 (far less than the expected floor(100/2) = 50).
%t A182865 q[n_, k_] := Cases[Union[Mod[Range[k]^2, n]],_?Positive];
%t A182865 a[n_] := (r = q[n, Floor[n/2]]; k = 0; While[r != q[n, ++k]]; k); Table[a[n], {n, 2, 100}]
%Y A182865 It should be noticed that, when n is prime, the corresponding sublist is A005097, i.e., (primes-1)/2.
%Y A182865 Cf. A096008.
%Y A182865 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 A182865 nonn,easy
%O A182865 2,4
%A A182865 _Jean-François Alcover_, Feb 01 2011
%E A182865 Formula and sequence corrected to eliminate zeros from lists of quadratic residues. Anyway, mod computed with or without offset 1 gives the same list.