login
A336416
Number of perfect-power divisors of n!.
25
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,5
COMMENTS
A number is a perfect power iff it is 1 or its prime exponents (signature) are not relatively prime.
LINKS
FORMULA
a(p) = a(p-1) for prime p. - David A. Corneth, Aug 19 2020
EXAMPLE
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
MATHEMATICA
perpouQ[n_]:=Or[n==1, GCD@@FactorInteger[n][[All, 2]]>1];
Table[Length[Select[Divisors[n!], perpouQ]], {n, 0, 15}]
PROG
(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
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.
Sequence in context: A109580 A168269 A326936 * A128508 A083743 A126990
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 22 2020
EXTENSIONS
a(26)-a(34) from Jinyuan Wang, Aug 19 2020
a(35)-a(49) from David A. Corneth, Aug 19 2020
STATUS
approved