|
| |
|
|
A001783
|
|
n-phi-torial, or phi-torial of n: Product k, 1 <= k <= n, k relatively prime to n.
(Formerly M0921 N0346)
|
|
36
|
|
|
|
1, 1, 2, 3, 24, 5, 720, 105, 2240, 189, 3628800, 385, 479001600, 19305, 896896, 2027025, 20922789888000, 85085, 6402373705728000, 8729721, 47297536000, 1249937325, 1124000727777607680000, 37182145, 41363226782215962624
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
In other words, a(1) = 1 and for n >= 2, a(n) = product of the phi(n) numbers < n and relatively prime to n.
From Gauss's generalization of Wilson's theorem (see Weisstein link) it follows that, for n>1, a(n) == -1 (mod n) if and only if there exists a primitive root modulo n (cf. the Hardy and Wright reference, Theorem 129. p. 102). - Vladimir Shevelev, May 11 2012
Islam & Manzoor prove that a(n) is an injection for n > 1, see links. In other words, if a(m) = a(n), and min(m, n) > 1, then m = n. - Muhammed Hedayet, May 25 2016
Cosgrave & Dilcher propose the name Gauss factorial. Indeed the sequence is the special case N = n of the Gauss factorial N_n! = Product_{1<=j<=N, gcd(j, n)=1} j (see A216919). - Peter Luschny, Feb 07 2018
|
|
|
REFERENCES
|
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth ed., Clarendon Press, Oxford, 2003, Theorem 129, p. 102.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 1..200
J. B. Cosgrave and K. Dilcher, Extensions of the Gauss-Wilson Theorem, Integers: Electronic Journal of Combinatorial Number Theory, 8 (2008)
J. B. Cosgrave, K. Dilcher, The multiplicative orders of certain Gauss factorials, Intl. J. Number Theory 7 (1) (2011) 145-171.
S. W. Golomb and William Small, Problem E1045, Amer. Math. Monthly, 60 (1953), 422.
Muhammed H. Islam and Shahriar Manzoor, φ1 and phitorial are injections, for any positive integer N, where N > 1
Laszlo Toth, Weighted gcd-sum functions, J. Integer Sequences, 14 (2011), Article 11.7.7
Eric Weisstein's World of Mathematics, Wilson's Theorem
|
|
|
FORMULA
|
a(n) = n^phi(n)*Product_{d|n} (d!/d^d)^mu(n/d); phi=A000010 is the Euler totient function and mu=A008683 the Moebius function (Tom M. Apostol, Introduction to Analytic Number Theory, New York 1984, p. 48). - Franz Vrabec, Jul 08 2005
a(n) = n!/A066570(n). - R. J. Mathar, Mar 10 2011
A001221(a(n)) = A000720(n) - A001221(n) = A048865(n).
A006530(a(n)) = A136548(n). - Enrique Pérez Herrero, Jul 23 2011
a(n) = A124441(n)*A124442(n). - M. F. Hasler, Jul 23 2011
a(n) == (-1)^A211487(n) (mod n). - Vladimir Shevelev, May 13 2012
|
|
|
MAPLE
|
A001783 := proc(n) local i, t1; t1 := 1; for i from 1 to n do if gcd(i, n)=1 then t1 := t1*i; fi; od; t1; end;
A001783 := proc(n) local i; mul(i, i=select(k->igcd(n, k)=1, [$1..n])) end; # Peter Luschny, Oct 30 2010
|
|
|
MATHEMATICA
|
A001783[n_]:=Times@@Select[Range[n], CoprimeQ[n, #]&];
Array[A001783, 20] (* Enrique Pérez Herrero, Jul 23 2011 *)
|
|
|
PROG
|
(PARI) A001783(n)=prod(k=2, n-1, k^(gcd(k, n)==1)) \\ M. F. Hasler, Jul 23 2011
(PARI) a(n)=my(f=factor(n), t=n^eulerphi(f)); fordiv(f, d, t*=(d!/d^d)^moebius(n/d)); t \\ Charles R Greathouse IV, Nov 05 2015
(Haskell)
a001783 = product . a038566_row
-- Reinhard Zumkeller, Mar 04 2012, Aug 26 2011
(Sage)
def Gauss_factorial(N, n): return mul(j for j in (1..N) if gcd(j, n) == 1)
def A001783(n): return Gauss_factorial(n, n)
[A001783(n) for n in (1..25)] # Peter Luschny, Oct 01 2012
|
|
|
CROSSREFS
|
Cf. A023896, A066570, A038566, A124441, A216919.
Sequence in context: A030418 A329456 A037277 * A095996 A308943 A061098
Adjacent sequences: A001780 A001781 A001782 * A001784 A001785 A001786
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
EXTENSIONS
|
More terms from James A. Sellers, Dec 23 1999
|
|
|
STATUS
|
approved
|
| |
|
|
