login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A196330 Smallest number k such that the number of distinct residues of x^k (mod k) equals n. 0
1, 2, 3, 6, 5, 10, 7, 14, 21, 68, 11, 22, 13, 26, 15, 114, 17, 34, 19, 38, 57, 164, 23, 46, 2525, 776, 657, 212, 29, 58, 31, 62, 33, 4112, 35, 102, 37, 74, 111, 380, 41, 82, 43, 86, 105, 356, 47, 94, 301, 388, 51, 404, 53, 106, 6275, 182, 1467, 452, 59, 118 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

The values of x can be taken to be 1 to n.

Properties of the sequence: if n prime, a(n) = n and a(n+1) = 2n because x^n == 0,1,2,3,...,n-1 (mod n) and x^(2n) == 0, 1^2, 2^2, 3^2,...,(n-1)^2, n (mod 2n) with n+1 distinct residues.

There exists prime numbers, for example n = 7, 19, 37,... with the property: a(n) = n, a(n+1) = 2n, and a(n+2) = 3n.

There exists composite numbers, for example n = 15, 33, 35, 51,... with the property a(n) = n.

LINKS

Table of n, a(n) for n=1..60.

I. M. Vinogradov, On a general theorem concerning the distribution of the residues and non-residues of powers, Trans. American Math. Soc., 29 (1927), 209-217.

FORMULA

a(n) such that A195637(a(n)) = n.

EXAMPLE

a(6) = 10 because x^10 == 0, 1, 4, 5, 6, 9  (mod 10) => 6 distinct residues.

MAPLE

a:= nops ({seq (k&^n mod n, k=0..n-1)}):for i from 1 to 60 do:id:=0:for j from 1 to 10000 while(id=0) do:if a(j)=i then id:=1:printf ( "%d %d \n", i, j):else fi:od:od:

MATHEMATICA

nn = 10000; t = Table[Length[Union[PowerMod[Range[n], n, n]]], {n, nn}]; lim = Complement[Range[nn], Union[t]][[1]] - 1; Table[Position[t, n, 1, 1][[1, 1]], {n, lim}] (* T. D. Noe, Oct 03 2011 *)

CROSSREFS

Cf. A195637.

Sequence in context: A064919 A064923 A064924 * A332462 A256662 A055944

Adjacent sequences:  A196327 A196328 A196329 * A196331 A196332 A196333

KEYWORD

nonn

AUTHOR

Michel Lagneau, Oct 01 2011

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 25 17:48 EDT 2022. Contains 354071 sequences. (Running on oeis4.)