login
A048855
Number of integers up to n! relatively prime to n!.
21
1, 1, 1, 2, 8, 32, 192, 1152, 9216, 82944, 829440, 8294400, 99532800, 1194393600, 16721510400, 250822656000, 4013162496000, 64210599936000, 1155790798848000, 20804234379264000, 416084687585280000, 8737778439290880000, 192231125664399360000
OFFSET
0,4
COMMENTS
Rephrasing the Quet formula: Begin with 1. Then, if n + 1 is prime subtract 1 and multiply. If n+1 is not prime, multiply. Continue writing each product. Thus the sequence would begin 1, 2, 8, . . . . The first product is 1*(2 - 1), second is 1*(3 - 1), and third is 2*4. - Enoch Haga, May 06 2009
REFERENCES
Ronald L. Graham, D. E. Knuth and Oren Patashnik, "Concrete Mathematics, A Foundation for Computer Science," Addison-Wesley Publ. Co., Reading, MA, 1989, page 134.
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 0..450
FORMULA
a(n) = phi(n!) = A000010(n!).
If n is composite, then a(n) = a(n-1)*n. If n is prime, then a(n) = a(n-1)*(n-1). - Leroy Quet, May 24 2007
Under the Riemann Hypothesis, a(n) = n! / (e^gamma * log n) * (1 + O(log n/sqrt(n))). - Charles R Greathouse IV, May 12 2011
MAPLE
with(numtheory):a:=n->phi(n!): seq(a(n), n=0..20); # Zerinvary Lajos, Oct 07 2007
MATHEMATICA
Table[ EulerPhi[ n! ], {n, 0, 21}] (* Robert G. Wilson v, Nov 21 2003 *)
PROG
(Sage) [euler_phi(factorial(n)) for n in range(0, 21)] # Zerinvary Lajos, Jun 06 2009
(PARI) a(n)=eulerphi(n!) \\ Charles R Greathouse IV, May 12 2011
(Python)
from math import factorial, prod
from sympy import primerange
from fractions import Fraction
def A048855(n): return (factorial(n)*prod(Fraction(p-1, p) for p in primerange(n+1))).numerator # Chai Wah Wu, Jul 06 2022
CROSSREFS
KEYWORD
easy,nonn
EXTENSIONS
Name changed by Daniel Forgues, Aug 01 2011
STATUS
approved