login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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., (primes-1)/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: A076742 A036465 A265339 * A131469 A073078 A034799

Adjacent sequences:  A182862 A182863 A182864 * A182866 A182867 A182868

KEYWORD

nonn,easy

AUTHOR

Jean-Fran├ž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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 26 06:54 EDT 2017. Contains 292502 sequences.