A038203 Number of distinct values of factorials mod n.

1, 2, 3, 3, 4, 3, 5, 4, 5, 5, 6, 4, 10, 6, 5, 5, 12, 5, 12, 5, 6, 7, 17, 4, 8, 11, 8, 7, 19, 5, 21, 6, 8, 13, 7, 6, 26, 13, 11, 5, 29, 6, 26, 8, 6, 18, 31, 5, 11, 8, 13, 12, 35, 8, 9, 7, 14, 20, 37, 5, 41, 22, 7, 8, 13, 8, 42, 14, 18, 7, 39, 6, 44, 27, 8, 15, 11, 11, 49, 6, 9, 30, 55, 7

Offset: 1

Author

David W. Wilson

Keywords

• nonn

Comments

Assuming k! mod n is uniformly distributed mod n up to k = A002034(n), the first k! == 0 (mod n). This gives a(n) ~= (1-(1-1/n)^k)*n, which empirically appears to be a good estimate. For prime p, A002034(p) = p, so we would expect a(p) ~= (1-(1-1/p)^p)*p ~= (1-1/e)*p = 0.63212 p for large primes p. - David W. Wilson, Aug 01 2016

Examples

			a(15)=5 since factorials are 1, 2, 6, 24, 120, etc. which mod 15 are 1, 2, 6, 9, 0, etc. and so there are 5 distinct values.
		

Links

• David W. Wilson, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A038204, A062169.

Programs

Mathematica

nn=90;With[{frls=Range[nn]!},Table[Length[Union[Mod[#,n]&/@frls]],{n,nn}]] (* Harvey P. Dale, Oct 05 2011 *)

PARI

a(n)=my(t=1); #Set(vector(n,k,t=t*k%n)) \\ Charles R Greathouse IV, Aug 03 2016