|
|
A336416
|
|
Number of perfect-power divisors of n!.
|
|
16
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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 version for distinct prime exponents is A336414.
Prime power divisors are counted by A022559.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|