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,2

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

Links

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

Example

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.

Mathematica

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

Prog

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

Crossrefs

Cf. A038204, A062169.

Sequence in context: A350064 A351085 A049878 * A255239 A316339 A186971

Adjacent sequences: A038200 A038201 A038202 * A038204 A038205 A038206

Keyword

nonn

Author

David W. Wilson

Status

approved