A055597 Exponent of the highest power of 2 dividing phi(n!).

0, 0, 1, 3, 5, 6, 7, 10, 10, 11, 12, 14, 16, 17, 17, 21, 25, 26, 27, 29, 29, 30, 31, 34, 34, 35, 35, 37, 39, 40, 41, 46, 46, 47, 47, 49, 51, 52, 52, 55, 58, 59, 60, 62, 62, 63, 64, 68, 68, 69, 69, 71, 73, 74, 74, 77, 77, 78, 79, 81, 83, 84, 84, 90, 90, 91, 92, 94, 94, 95, 96

Offset: 1

Author

Labos Elemer, Jul 11 2000

Keywords

• nonn

Examples

			For n=8, 8! = 40320 = 128*315, phi(40320) = 9216 = 9*1024, so a(8)=10, while the exponent of 2 in 8! is only 7. Exponents of 2 are larger in phi(n!) than in n!.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A000720, A007814, A011371, A048855.

Programs

Mathematica

a[n_] := IntegerExponent[EulerPhi[n!], 2]; Array[a, 100] (* Amiram Eldar, Jul 12 2024 *)

PARI

a(n) = valuation(eulerphi(n!), 2); \\ Amiram Eldar, Jul 12 2024

Python

from math import factorial, prod
from sympy import primerange
from fractions import Fraction
def A055597(n): return (~(m:=(factorial(n)*prod(Fraction(p-1,p) for p in primerange(n+1))).numerator)&m-1).bit_length() # Chai Wah Wu, Jul 06 2022

Formula

a(n) = A007814(A048855(n)) = A007814(A000010(n!)).

Extensions

Name clarified by Amiram Eldar, Jul 12 2024