

A038203


Number of distinct values of factorials mod n.


4



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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(11/n)^k)*n, which empirically appears to be a good estimate. For prime p, A002034(p) = p, so we would expect a(p) ~= (1(11/p)^p)*p ~= (11/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: A053475 A140605 A049878 * A255239 A316339 A186971
Adjacent sequences: A038200 A038201 A038202 * A038204 A038205 A038206


KEYWORD

nonn


AUTHOR

David W. Wilson


STATUS

approved



