login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A048855 Number of integers up to n! relatively prime to n!. 21

%I #52 Oct 12 2022 12:15:24

%S 1,1,1,2,8,32,192,1152,9216,82944,829440,8294400,99532800,1194393600,

%T 16721510400,250822656000,4013162496000,64210599936000,

%U 1155790798848000,20804234379264000,416084687585280000,8737778439290880000,192231125664399360000

%N Number of integers up to n! relatively prime to n!.

%C 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

%D 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.

%H Charles R Greathouse IV, <a href="/A048855/b048855.txt">Table of n, a(n) for n = 0..450</a>

%F a(n) = phi(n!) = A000010(n!).

%F 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

%F Under the Riemann Hypothesis, a(n) = n! / (e^gamma * log n) * (1 + O(log n/sqrt(n))). - _Charles R Greathouse IV_, May 12 2011

%p with(numtheory):a:=n->phi(n!): seq(a(n), n=0..20); # _Zerinvary Lajos_, Oct 07 2007

%t Table[ EulerPhi[ n! ], {n, 0, 21}] (* _Robert G. Wilson v_, Nov 21 2003 *)

%o (Sage) [euler_phi(factorial(n)) for n in range(0,21)] # _Zerinvary Lajos_, Jun 06 2009

%o (PARI) a(n)=eulerphi(n!) \\ _Charles R Greathouse IV_, May 12 2011

%o (Python)

%o from math import factorial, prod

%o from sympy import primerange

%o from fractions import Fraction

%o def A048855(n): return (factorial(n)*prod(Fraction(p-1,p) for p in primerange(n+1))).numerator # _Chai Wah Wu_, Jul 06 2022

%Y Cf. A000010, A000142, A014197.

%K easy,nonn

%O 0,4

%A _Paul Max Payton_

%E Name changed by _Daniel Forgues_, Aug 01 2011

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 14:38 EDT 2024. Contains 371254 sequences. (Running on oeis4.)