A210184 Number of distinct residues of all factorials mod prime(n).

2, 3, 4, 5, 6, 10, 12, 12, 17, 19, 21, 26, 29, 26, 31, 35, 37, 41, 42, 39, 44, 49, 55, 59, 59, 65, 71, 75, 63, 73, 80, 82, 90, 90, 104, 86, 103, 104, 107, 111, 113, 114, 120, 125, 120, 115, 139, 149, 132, 141, 147, 150, 147, 164, 166, 172, 172, 170, 172, 180

Offset: 1

Author

Vladimir Shevelev, Mar 18 2012

Keywords

• nonn

Comments

Conjecture: a(n)/p_n > 1/2.

The standard (folklore?) conjecture is that a(n)/prime(n) = 1 - 1/e = 0.63212.... - Charles R Greathouse IV, May 11 2015

Examples

			Let n=4, p_4=7. We have modulo 7: 1!==1, 2!==2, 3!==6, 4!==3, 5!==1, 6!==6 and for m>=7, m!==0, such that we have 5 distinct residues 0,1,2,3,6. Therefore a(4) = 5.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1...1000 from Alois P. Heinz)
• Yong-Gao Chen and Li-Xia Dai, Congruences with factorials modulo p, INTEGERS 6 (2006), #A21.

Crossrefs

Cf. A000040, A000142.

Programs

Maple

a:= proc(n) local p, m, i, s;
      p:= ithprime(n);
      m:= 1;
      s:= {};
      for i to p do m:= m*i mod p; s:=s union {m} od;
      nops(s)
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Mar 19 2012

Mathematica

Table[Length[Union[Mod[Range[Prime[n]]!, Prime[n]]]], {n, 100}] (* T. D. Noe, Mar 18 2012 *)

PARI

apply(p->#Set(vector(p,n,n!)%p), primes(100)) \\ Charles R Greathouse IV, May 11 2015

PARI

a(n,p=prime(n))=my(t=1); #Set(vector(p,n,t=(t*n)%p)) \\ Charles R Greathouse IV, May 11 2015