A048855 Number of integers up to n! relatively prime to n!.

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

Author

Paul Max Payton

Keywords

• easy
• nonn

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, Donald 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
• Jean-Marie De Koninck and William Verreault, Arithmetic functions at factorial arguments, Publications de l'Institut Mathématique, Vol. 115, No. 129 (2024), pp. 45-76.

Crossrefs

Cf. A000010, A000142, A014197.

Cf. A001620, A080130.

Programs

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

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

Sage

[euler_phi(factorial(n)) for n in range(0,21)] # Zerinvary Lajos, Jun 06 2009

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

Sum_{k=1..n} a(k) = exp(-gamma) * (n!/log(n)) * (1 + O(1/log(n)^3)), where gamma is Euler's constant (A001620) (De Koninck and Verreault, 2024, p. 56, eq. (4.12)). - Amiram Eldar, Dec 10 2024

Extensions

Name changed by Daniel Forgues, Aug 01 2011