cp's OEIS Frontend

A336416 Number of perfect-power divisors of n!.

%I A336416 #36 Sep 05 2020 20:34:42
%S A336416 1,1,1,1,3,3,7,7,11,18,36,36,47,47,84,122,166,166,221,221,346,416,717,
%T A336416 717,1001,1360,2513,2942,4652,4652,5675,5675,6507,6980,13892,17212,
%U A336416 20408,20408,39869,45329,51018,51018,68758,68758,105573,138617,284718,284718,338126,421126
%N A336416 Number of perfect-power divisors of n!.
%C A336416 A number is a perfect power iff it is 1 or its prime exponents (signature) are not relatively prime.
%H A336416 David A. Corneth, <a href="/A336416/b336416.txt">Table of n, a(n) for n = 0..9999</a>
%F A336416 a(p) = a(p-1) for prime p. - _David A. Corneth_, Aug 19 2020
%e A336416 The a(1) = 0 through a(9) = 18 divisors:
%e A336416        1: 1
%e A336416        2: 1
%e A336416        6: 1
%e A336416       24: 1,4,8
%e A336416      120: 1,4,8
%e A336416      720: 1,4,8,9,16,36,144
%e A336416     5040: 1,4,8,9,16,36,144
%e A336416    40320: 1,4,8,9,16,32,36,64,128,144,576
%e A336416   362880: 1,4,8,9,16,27,32,36,64,81,128,144,216,324,576,1296,1728,5184
%t A336416 perpouQ[n_]:=Or[n==1,GCD@@FactorInteger[n][[All,2]]>1];
%t A336416 Table[Length[Select[Divisors[n!],perpouQ]],{n,0,15}]
%o A336416 (PARI) a(n) = sumdiv(n!, d, (d==1) || ispower(d)); \\ _Michel Marcus_, Aug 19 2020
%o A336416 (PARI) addhelp(val, "exponent of prime p in n!")
%o A336416 val(n, p) = my(r=0); while(n, r+=n\=p);r
%o A336416 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
%Y A336416 The maximum among these divisors is A090630, with quotient A251753.
%Y A336416 The version for distinct prime exponents is A336414.
%Y A336416 The uniform version is A336415.
%Y A336416 Replacing factorials with Chernoff numbers (A006939) gives A336417.
%Y A336416 Prime powers are A000961.
%Y A336416 Perfect powers are A001597, with complement A007916.
%Y A336416 Prime power divisors are counted by A022559.
%Y A336416 Cf. A000005, A001221, A001222, A011371, A032741, A118914, A124010, A130091, A327527.
%Y A336416 Factorial numbers: A000142, A007489, A027423, A048656, A071626, A181796, A325272, A325273, A325617.
%K A336416 nonn
%O A336416 0,5
%A A336416 _Gus Wiseman_, Jul 22 2020
%E A336416 a(26)-a(34) from _Jinyuan Wang_, Aug 19 2020
%E A336416 a(35)-a(49) from _David A. Corneth_, Aug 19 2020