A336416 Number of perfect-power divisors of n!.

1, 1, 1, 1, 3, 3, 7, 7, 11, 18, 36, 36, 47, 47, 84, 122, 166, 166, 221, 221, 346, 416, 717, 717, 1001, 1360, 2513, 2942, 4652, 4652, 5675, 5675, 6507, 6980, 13892, 17212, 20408, 20408, 39869, 45329, 51018, 51018, 68758, 68758, 105573, 138617, 284718, 284718, 338126, 421126

Offset: 0

Author

Gus Wiseman, Jul 22 2020

Keywords

• nonn

Comments

A number is a perfect power iff it is 1 or its prime exponents (signature) are not relatively prime.

Examples

			The a(1) = 0 through a(9) = 18 divisors:
       1: 1
       2: 1
       6: 1
      24: 1,4,8
     120: 1,4,8
     720: 1,4,8,9,16,36,144
    5040: 1,4,8,9,16,36,144
   40320: 1,4,8,9,16,32,36,64,128,144,576
  362880: 1,4,8,9,16,27,32,36,64,81,128,144,216,324,576,1296,1728,5184
		

Links

• David A. Corneth, Table of n, a(n) for n = 0..9999

Crossrefs

The maximum among these divisors is A090630, with quotient A251753.

The version for distinct prime exponents is A336414.

The uniform version is A336415.

Replacing factorials with Chernoff numbers (A006939) gives A336417.

Prime powers are A000961.

Perfect powers are A001597, with complement A007916.

Prime power divisors are counted by A022559.

Cf. A000005, A001221, A001222, A011371, A032741, A118914, A124010, A130091, A327527.

Factorial numbers: A000142, A007489, A027423, A048656, A071626, A181796, A325272, A325273, A325617.

Programs

Mathematica

perpouQ[n_]:=Or[n==1,GCD@@FactorInteger[n][[All,2]]>1];
Table[Length[Select[Divisors[n!],perpouQ]],{n,0,15}]

PARI

a(n) = sumdiv(n!, d, (d==1) || ispower(d)); \\ Michel Marcus, Aug 19 2020

PARI

addhelp(val, "exponent of prime p in n!")
val(n, p) = my(r=0); while(n, r+=n\=p);r
a(n) = {if(n<=3, return(1)); my(pr = primes(primepi(n\2)), v = vector(#pr, i, val(n, pr[i])), res = 1, cv); for(i = 2, v[1], if(issquarefree(i), cv = v\i; res-=(prod(i = 1, #cv, cv[i]+1)-1)*(-1)^omega(i) ) ); res } \\ David A. Corneth, Aug 19 2020

Formula

a(p) = a(p-1) for prime p. - David A. Corneth, Aug 19 2020

Extensions

a(26)-a(34) from Jinyuan Wang, Aug 19 2020

a(35)-a(49) from David A. Corneth, Aug 19 2020