|
%I #16 Nov 20 2020 09:10:21
%S 1,2,3,6,5,10,7,14,21,68,11,22,13,26,15,114,17,34,19,38,57,164,23,46,
%T 2525,776,657,212,29,58,31,62,33,4112,35,102,37,74,111,380,41,82,43,
%U 86,105,356,47,94,301,388,51,404,53,106,6275,182,1467,452,59,118
%N Smallest number k such that the number of distinct residues of x^k (mod k) equals n.
%C The values of x can be taken to be 1 to n.
%C 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.
%C 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.
%C There exists composite numbers, for example n = 15, 33, 35, 51,... with the property a(n) = n.
%H I. M. Vinogradov, <a href="https://doi.org/10.1090/S0002-9947-1927-1501384-3">On a general theorem concerning the distribution of the residues and non-residues of powers</a>, Trans. American Math. Soc., 29 (1927), 209-217.
%F a(n) such that A195637(a(n)) = n.
%e a(6) = 10 because x^10 == 0, 1, 4, 5, 6, 9 (mod 10) => 6 distinct residues.
%p 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:
%t 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 *)
%Y Cf. A195637.
%K nonn
%O 1,2
%A _Michel Lagneau_, Oct 01 2011
|
