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

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

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.

Example

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.

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 *)

Prog

(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

Crossrefs

Cf. A000040, A000142.

Sequence in context: A102570 A113007 A113325 * A015853 A018642 A116998

Adjacent sequences: A210181 A210182 A210183 * A210185 A210186 A210187

Keyword

nonn

Author

Vladimir Shevelev, Mar 18 2012

Status

approved