A048855 -id:A048855 - cp's OEIS frontend

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

Labos Elemer, Jul 11 2000

nonn

			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!.

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

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

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

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

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

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

Name clarified by Amiram Eldar, Jul 12 2024

A055656 Excess in exponents of powers of 2 in Euler phi of n! compared to that of n!.

Original entry on oeis.org

0, -1, 0, 0, 2, 2, 3, 3, 3, 3, 4, 4, 6, 6, 6, 6, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 14, 14, 15, 15, 15, 15, 15, 15, 17, 17, 17, 17, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 24, 24, 24, 24, 24, 24, 25, 25, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 29, 29, 32, 32

Offset: 1

Labos Elemer, Jul 11 2000

sign

The exponents of 2 is larger in phi(n!) than in n! if n > 4.

			For n = 8, 8! = 40320 = 128*315, phi(40320) = 9216 = 9*1024. The exponent of 2 in 8! is only 7, and in phi(8!) it is 10, so a(8) = 10-7 = 3.

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

Cf. A000142, A000010, A048855, A007814, A011371.

eep2[n_]:=Module[{f=n!},IntegerExponent[EulerPhi[f],2]-IntegerExponent[f,2]]; Array[ eep2,80] (* Harvey P. Dale, Mar 18 2023 *)

a(n) = {my(f = n!); valuation(eulerphi(f), 2) - valuation(f, 2);} \\ Amiram Eldar, Jul 15 2024

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

a(n) = A007814(A048855(n))-A007814(n!) = A007814(A048855(n))-A011371(A000142(n)).

A055679 Number of distinct prime factors of phi(n!).

Original entry on oeis.org

0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14

Offset: 1

Labos Elemer, Jul 11 2000

Number of distinct prime factors of n! and phi(n!) are respectively pi(n) and pi(floor(n/2)).

G. C. Greubel, Table of n, a(n) for n = 1..5000

Cf. A000010, A000142, A000720, A001221, A055718.

PrimeNu[EulerPhi[Range[90]!]] (* Harvey P. Dale, Sep 27 2011 *)

for(n=1,50, print1(omega(eulerphi(n!)), ", ")) \\ G. C. Greubel, May 19 2017

a(n) = primepi(n\2); \\ Michel Marcus, Aug 13 2024

a(n) = A001221(A000010(A000142(n))) = A001221(A048855(n)).

a(n) = pi(floor(n/2)).

A067393 Number of nonprimes among the numbers in {1,2,3,...,n!} which are relatively prime to n!.

Original entry on oeis.org

1, 1, 1, 1, 1, 5, 67, 481, 4989, 51979, 570755, 5865449, 74226518, 904772855, 13111019601, 202135743076, 3307158697867, 53256981940267, 974755766640247, 17629139875485487, 357191085875727470, 7585952737111971220, 168542590546266903340, 3718034609300727209976

Offset: 0

Labos Elemer, Jan 22 2002

nonn

			For n = 5, n! = 120, a(5) = phi(120) - pi(120) + pi(5) = 32 - 30 + 3 = 5; the 5 nonprimes are 1, 49, 77, 91, 119.

Amiram Eldar, Table of n, a(n) for n = 0..25 (calculated using the b-file at A003604)

Cf. A000010, A000142, A000720, A003604, A048855.

a[n_] := EulerPhi[ n! ]-PrimePi[ n! ]+PrimePi[n]

a(n) = phi(n!) - pi(n!) + pi(n) = A000010(n!) - A000720(n!) + A000720(n).

a(18)-a(19) from Donovan Johnson, Mar 24 2011

a(20)-a(23) from Giovanni Resta, Oct 29 2019

A104354 Euler's totient of A104350(n).

Original entry on oeis.org

1, 1, 2, 4, 16, 48, 288, 576, 1728, 8640, 86400, 259200, 3110400, 21772800, 108864000, 217728000, 3483648000, 10450944000, 188116992000, 940584960000, 6584094720000, 72425041920000, 1593350922240000, 4780052766720000, 23900263833600000, 310703429836800000

Offset: 1

Reinhard Zumkeller, Mar 06 2005

nonn

Amiram Eldar, Table of n, a(n) for n = 1..640
Reinhard Zumkeller, Products of largest prime factors of numbers <= n.

Cf. A000010, A048855, A104350.

EulerPhi[FoldList[Times, Array[FactorInteger[#][[-1, 1]] &, 30]]] (* Amiram Eldar, Apr 08 2024 *)

gpf(n) = my(f=factor(n)[, 1]); f[#f];
a(n) = eulerphi(prod(i=2, n, gpf(i))); \\ Michel Marcus, Nov 12 2023

a(n) = A000010(A104350(n)).

a(1) prepended by Michel Marcus, Nov 12 2023

A129335 a(n) = phi(n!!) where phi is the Euler totient function. In other words, a(n) = A000010(A006882(n)).

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 48, 128, 432, 1024, 4320, 12288, 51840, 147456, 777600, 2359296, 12441600, 42467328, 223948800, 849346560, 4702924800, 16986931200, 103464345600, 407686348800, 2586608640000, 9784472371200, 69838433280000

Offset: 1

Leroy Quet, May 26 2007

nonn

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

Cf. A000010, A006882, A048855.

Table[EulerPhi[n!! ], {n, 1, 30}] (* Stefan Steinerberger, May 30 2007 *)

If n>2 is prime, a(n) = (n-1)*a(n-2). If n=2*p, where p is odd prime, a(n)=(n-2)*a(n-2). Otherwise, a(n) = n*a(n-2). - Max Alekseyev, May 26 2007

More terms from Stefan Steinerberger, May 30 2007

A273060 a(n) = phi(n!)/phi(n).

Original entry on oeis.org

1, 1, 1, 4, 8, 96, 192, 2304, 13824, 207360, 829440, 24883200, 99532800, 2786918400, 31352832000, 501645312000, 4013162496000, 192631799808000, 1155790798848000, 52010585948160000, 728148203274240000, 19223112566439936000, 192231125664399360000

Offset: 1

Alexander R. Povolotsky, Oct 29 2016

nonn

Robert Israel, Table of n, a(n) for n = 1..450

Cf. A000010, A048855.

[EulerPhi(Factorial(n)) div EulerPhi(n): n in [1..25]]; // Vincenzo Librandi, Oct 30 2016

seq(numtheory:-phi(n!)/numtheory:-phi(n), n=1..50); # Robert Israel, Nov 13 2016

Table[EulerPhi[n!]/EulerPhi[n], {n,1,25}] (* G. C. Greubel, Oct 30 2016 *)

a(n) = eulerphi(n!)/eulerphi(n); \\ Michel Marcus, Oct 30 2016

a(n) = A048855(n)/A000010(n). - Michel Marcus, Oct 30 2016

A276000 Least k such that n! divides phi(k!) (k > 0).

Original entry on oeis.org

1, 3, 6, 6, 10, 10, 14, 14, 14, 14, 22, 22, 26, 26, 26, 26, 34, 34, 38, 38, 38, 38, 46, 46, 46, 46, 46, 46, 58, 58, 62, 62, 62, 62, 62, 62, 74, 74, 74, 74, 82, 82, 86, 86, 86, 86, 94, 94, 94, 94, 94, 94, 106, 106, 106, 106, 106, 106, 118, 118, 122, 122, 122, 122

Offset: 1

Altug Alkan, Aug 16 2016

nonn

			a(2) = 3 because phi(3!) is divisible by 2!.

Robert Israel, Table of n, a(n) for n = 1..5000

Cf. A048855, A007917.

N:= 100: # for a(1)..a(N)
V:= Vector(N): n:= 0:
for k from 1 while n < N do
  r:= numtheory:-phi(k!);
  for i from n+1 to N while r mod (i!) = 0 do
    V[i]:= k; n:= i;
  od;
od:
convert(V,list);# Robert Israel, Apr 24 2020

Array[Block[{k = 1}, While[Mod[EulerPhi[k!], #!] != 0, k++]; k] &, 64] (* Michael De Vlieger, Apr 24 2020 *)

a(n) = {my(k = 1); while(eulerphi(k!) % n!, k++); k; }

a(n) = 2*A007917(n) for n>2. - Andrey Zabolotskiy, Aug 16 2016

A291597 Numbers n such that cototient(n) does not divide phi(n!).

Original entry on oeis.org

5865, 10005, 15045, 28815, 37995, 45645, 50235, 170085, 310845, 347565, 521985, 613785, 627555, 707115, 791265, 797385, 830415, 873885, 994755, 1014645, 1066665, 1078815, 1202835, 1323705, 1366545, 1542495, 1689465, 1730865, 1819605, 2001495, 2013735, 2246295, 2264655

Offset: 1

Altug Alkan, Aug 27 2017

nonn

Terms are 3*5*17*23, 3*5*23*29, 3*5*17*59, 3*5*17*113, ...

Terms are not prime powers as cototient(p^k) = p^(k-1) which divides phi(n!). - Chai Wah Wu, Aug 30 2017

			5865 is a term because 5865 - phi(5865) = 3049 and phi(5865!) is not divisible by 3049.
45645 is a term because 45645 - phi(45645) = 22861 and phi(45645!) is not divisible by 22861.

Chai Wah Wu, Table of n, a(n) for n = 1..45

Cf. A000010, A048855, A051953.

valp(n, p)=my(s); while(n\=p, s+=n); s
is(n)=my(m=n-eulerphi(n), t, u); forprime(p=2, n, t=valp(n, p)-1; if(t && (u=valuation(m,p)), m/=p^min(t,u); if(m==1, return(0))); t=gcd(m,p-1); if(t>1, m/=t; if(m==1, return(0)))); m>1 \\ Charles R Greathouse IV, Aug 27 2017

a(8)-a(22) from Charles R Greathouse IV, Aug 27 2017
a(23)-a(29) from Chai Wah Wu, Aug 29 2017
a(30)-a(33) from Chai Wah Wu, Aug 30 2017

A067562 Odd values of k such that phi(k)! divides phi(k!) where phi(k) = A000010(k).

Original entry on oeis.org

1, 3, 15, 63, 75, 105, 165, 195, 231, 255, 285, 315, 495, 525, 585, 735, 825, 945, 975, 1155, 1275, 1365, 1485, 1575, 1755, 1785, 1815, 1995, 2145, 2205, 2415, 2475, 2535, 2625, 2805, 2835, 2925, 3003, 3045, 3135, 3255, 3315, 3465, 3675, 3705, 3795, 3885, 3927

Offset: 1

Benoit Cloitre, Jan 29 2002; corrected Jun 03 2003

nonn

a(n) == 0 (mod 3) for any n > 1.

k cannot be divisible by 5 for k = 1, 3, 63, 231, 3003, 3927, 4389, 4641, 5187, 5313, 9009, 11781, 13167, 13923, 15561, 15939, 21021, 27027, 27489, 30723, ... - Jinyuan Wang, Apr 05 2020

Cf. A000010, A048855.

is(k) = (k%6==3 && eulerphi(k!)%eulerphi(k)!==0) || k==1; \\ Jinyuan Wang, Apr 05 2020

More terms from Jinyuan Wang, Apr 05 2020

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A055656 Excess in exponents of powers of 2 in Euler phi of n! compared to that of n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A055679 Number of distinct prime factors of phi(n!).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A067393 Number of nonprimes among the numbers in {1,2,3,...,n!} which are relatively prime to n!.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A104354 Euler's totient of A104350(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A129335 a(n) = phi(n!!) where phi is the Euler totient function. In other words, a(n) = A000010(A006882(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A273060 a(n) = phi(n!)/phi(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple